book

Extended STL, Volume 1: Collections and Iterators

Name: Extended STL, Volume 1: Collections and Iterators
Author: Matthew Wilson
ISBN: 9780321305503

by Matthew Wilson

June 2007

Intermediate to advanced

624 pages

15h 14m

English

Addison-Wesley Professional

Read now

Unlock full access

Copyright
Dedication
Praise for Extended STL, Volume 1
Preface
AimsSubject MatterStructurePart One: FoundationsPart Two: CollectionsPart Three: IteratorsVolume 2Supplementary MaterialCD-ROMOnline Resources
Acknowledgments
Parachutes: Coda
About the Author
Prologue
A Dichotomy of CharacterPrinciples of UNIX ProgrammingSeven Signs of Successful C++ Software LibrariesEfficiencyDiscoverability and TransparencyExpressivenessRobustnessFlexibilityModularityPortabilityBalancing the Signs: Satisfiction, Dialecticism, and Idioms Old and NewExample LibrariesSTLSoftSTLSoft SubprojectsBoostOpen-RJPantheiosrecls
Presentation Conventions
Fonts. . . versus . . .End Iterator PrecomputationNested Class Type QualificationNULLTemplate Parameter NamesMember and Namespace-Scope Type NamesCalling ConventionsEndpoint IteratorsNamespace for Standard C NamesClass Adaptors and Instance AdaptorsHeader File Names
One. Foundations
1. The Standard Template Library
1.1. Core Concepts1.2. Containers1.2.1. Sequence Containers1.2.2. Associative Containers1.2.3. Contiguity of Storage1.2.4. swap1.3. Iterators1.3.1. Input Iterators1.3.2. Output Iterators1.3.3. Forward Iterators1.3.4. Bidirectional Iterators1.3.5. Random Access Iterators1.3.6. Member Selection Operator1.3.7. Predefined Iterator Adaptors1.4. Algorithms1.5. Function Objects1.6. Allocators
2. Extended STL Concepts, or When STL Meets the Real World
2.1. Terminology2.2. Collections2.2.1. Mutability2.3. Iterators2.3.1. Mutability2.3.2. Traversal2.3.3. Compile-Time Characteristic Determination2.3.4. Element Reference Category2.3.5. State Sharing versus Independence2.3.6. Revising the Iterator Refinement Taxonomy?

3. Element Reference Categories
3.1. Introduction3.2. C++ References3.2.1. STL Container Element References3.3. A Taxonomy of Element Reference Categories3.3.1. Permanent3.3.2. Fixed3.3.3. Invalidatable3.3.4. Transient3.3.5. By-Value Temporary3.3.6. Void3.4. Using Element Reference Categories3.4.1. Detecting Category Flavors at Compile Time3.4.2. Using the Compiler to Avoid Undefined Iterator Behavior3.5. Defining operator ->()3.6. Element Reference Categories: Coda
4. The Curious Untemporary Reference
5. The DRY SPOT Principle
5.1. DRY SPOTs in C++5.1.1. Constants5.1.2. dimensionof()5.1.3. Creator Functions5.2. Not Quite DRY SPOTs in C++5.2.1. Parent Classes5.2.2. Function Return Types5.3. Closed Namespaces
6. The Law of Leaky Abstractions
7. Contract Programming
7.1. Enforcement Types7.2. Enforcement Mechanisms
8. Constraints
8.1. Type System Leverage8.2. Static Assertions
9. Shims
9.1. Introduction9.2. Primary Shims9.2.1. Attribute Shims9.2.2. Conversion Shims9.3. Composite Shims9.3.1. String Access Shims
10. Duck and Goose, or the Whimsical Bases of Partial Structural Conformance
10.1. Conformance10.1.1. Named Conformance10.1.2. Structural Conformance10.1.3. Duck and Goose10.2. Explicit Semantic Conformance10.2.1. Concepts10.2.2. Member Type Tagging10.2.3. Shims10.3. Intersecting Conformance
11. RAII
11.1. Mutability11.2. Resource Source
12. Template Tools
12.1. Traits12.1.1. base_type_traits12.1.2. sign_traits12.1.3. Type Characteristics: Mini-Traits12.1.4. is_integral_type12.1.5. is_signed_type12.1.6. is_fundamental_type12.1.7. is_same_type12.2. Type Generators12.2.1. stlsoft::allocator_selector12.3. True Typedefs
13. Inferred Interface Adaptation: Compile-Time Adaptation of Interface-Incomplete Types
13.1. Introduction13.2. Adapting Interface-Incomplete Types13.3. Adapting Immutable Collections13.4. Inferred Interface Adaptation13.4.1. Type Selection13.4.2. Type Detection13.4.3. Type Fixing13.5. Applying IIA to the Range
14. Henney’s Hypothesis, or When Templates Attack!
15. The Independent Autonomies of equal() Friends
15.1. Beware Nonmember Friend Function Abuse15.2. Collections and Their Iterators
16. Essential Components
16.1. Introduction16.2. auto_buffer16.2.1. It’s Not a Container!16.2.2. Class Interface16.2.3. Copying16.2.4. Nice Allocators Go Last16.2.5. swap()16.2.6. Performance16.3. filesystem_traits16.3.1. Member Types16.3.2. General String Handling16.3.3. File System Name Handling16.3.4. File System State Operations16.3.5. File System Control Operations16.3.6. Return Types and Error Handling16.4. file_path_buffer16.4.1. basic_??16.4.2. UNIX and PATH_MAX16.4.3. Windows and MAX_PATH16.4.4. Using the Buffers16.5. scoped_handle16.6. dl_call()
Two. Collections
17. Adapting the glob API
17.1. Introduction17.1.1. Motivation17.2. The glob API17.2. Decomposition of the Longhand Version17.3. unixstl::glob_sequence17.3.1. Public Interface17.3.2. Member Types17.3.3. Member Variables17.3.4. Flags17.3.5. Construction17.3.6. Size and Element Access17.3.7. Iteration17.3.8. init_glob_()17.4. Decomposition of the Shorthand Version17.5. Summary
18. Intermezzo: Constructor Clashes and Design That Is, If Not Bad, At Least Ill-Conceived for Seamless Evolution
19. Adapting the opendir/readdir API
19.1. Introduction19.1.1. Motivation19.1.2. The opendir/readdir API19.2. Decomposition of the Longhand Version19.3. unixstl::readdir_sequence19.3.1. Member Types and Constants19.3.2. Construction19.3.3. Iteration and Size Methods19.3.4. Attribute Methods19.3.5. const_iterator, Version 119.3.6. Using Version 119.3.7. const_iterator, Version 2: Copy Semantics19.3.8. operator ++()19.3.9. Iterator Category and Adaptable Member Types19.3.10. operator ->()19.3.11. Supporting fullPath and absolutePath19.4. Alternate Implementations19.4.1. Storing the Elements as a Snapshot19.4.2. Storing the Elements as an Iterator19.5. Summary
20. Adapting the FindFirstFile/FindNextFile API
20.1. Introduction20.1.1. Motivation20.1.2. The FindFirstFile/FindNextFile API20.2. Decomposition of Examples20.2.1. Longhand Version20.2.2. Shorthand Version20.2.3. Reparse Points and Infinite Recursion20.3. Sequence Design20.4. winstl::basic_findfile_sequence20.4.1. Class Interface20.4.2. Construction20.4.3. Iteration20.4.4. Exception Agnosticism20.5. winstl::basic_findfile_sequence_const_iterator20.5.1. Construction20.5.2. find_first_file_()20.5.3. operator ++()20.6. winstl::basic_findfile_sequence_value_type20.7. Shims20.8. What, No Shims and Constructor Templates?20.9. Summary20.10. File System Enumeration with recls: Coda
21. Intermezzo: When the Efficiency/Usability Balance Is Tipped: Enumerating FTP Server Directories
21.1. inetstl::basic_findfile_sequence21.2. inetstl::basic_ftpdir_sequence
22. Enumerating Processes and Modules
22.1. Collection Characteristics22.2. winstl::pid_sequence22.2.1. Simple Compositional Implementations22.2.2. Acquiring the Process Identifiers22.2.3. Working without Exception Support22.3. winstl::process_module_sequence22.4. Enumerating All Modules on a System22.5. Avoiding the System Pseudo Processes22.6. Handling Optional API Headers22.7. Summary
23. The Fibonacci Sequence
23.1. Introduction23.2. The Fibonacci Sequence23.3. Fibonacci as an STL Sequence23.3.1. Interface of an Infinite Sequence23.3.2. Put a Contract on It23.3.3. Changing Value Type?23.3.4. Constraining Type23.3.5. Throw std::overflow_error?23.4. Discoverability Failure23.5. Defining Finite Bounds23.5.1. Iterators Rule After All?23.5.2. Constructor-Bound Range23.5.3. True Typedefs23.6. Summary
24. Adapting MFC’s CArray Container Family
24.1. Introduction24.2. Motivation24.3. Emulating std::vector24.4. Design Considerations24.4.1. MFC’s Array Container Family24.4.2. CArray_traits24.4.3. Design of the Array Adaptor Classes24.4.4. Abstract Manipulation of State24.4.5. Copy-and-Swap Idiom24.4.6. Collection-Interface Composition24.4.7. Pedagogical Approach24.5. mfcstl::CArray_adaptor_base Interface24.6. mfcstl::CArray_cadaptor24.6.1. Template Declaration and Inheritance24.6.2. Applying CRTP24.6.3. Construction24.6.4. operator []()24.7. mfcstl::CArray_iadaptor24.8. Construction24.9. Allocator24.10. Element Access Methods24.11. Iteration24.11.1. begin() and end()24.11.2. rbegin() and rend()24.12. Size24.12.1. Memory Allocation Optimization24.13. Capacity24.14. Comparison24.15. Modifiers24.15.1. push_back()24.15.2. assign()24.15.3. pop_back() and clear()24.15.4. erase()24.15.5. insert()24.16. Assignment and swap()24.16.1. swap()24.17. Summary24.18. On the CD
25. A Map of the Environment
25.1. Introduction25.2. Motivation25.3. getenv(), putenv(), setenv()/unsetenv(), and environ25.4. platformstl::environment_variable_traits25.5. Planning the Interface25.6. Lookup by Name25.6.1. Option 1: Return a Fixed/Transient Reference to a Cached Object with an Up-to-Date Value25.6.2. Option 2: Return a Fixed Reference to a Cached Object with a Snapshot Value25.6.3. Option 3: Return a Fixed Reference to a Cached Object with an Up-to-Date Value25.6.4. Option 4: Return a By-Value Temporary Reference with an Up-to-Date Value25.6.5. Lookup by Name: Coda25.7. Inserting, Updating, and Deleting Values by Name25.8. Iteration25.8.1. Version 1: Contiguous Iterator25.8.2. Version 2: Bidirectional Iterator25.8.3. Version 3: Snapshot25.8.4. Version 4: Reference-Counted Snapshot25.9. Final Iteration Implementation25.9.1. Mutable Snapshot?25.9.2. Creating the Snapshot25.9.3. const_iterator Nested Class25.9.4. insert() Method25.9.5. erase() Method25.9.6. operator []() and lookup()25.9.7. snapshot Nested Class25.10. Heterogeneous Reference Categories?25.11. size() and Subscript by Index25.12. Summary25.13. On the CD
26. Traveling Back and Forth on the Z-Plane
26.1. Prologue26.2. Introduction26.3. Version 1: Forward Iteration26.3.1. zorder_iterator, Version 126.3.2. window_peer_sequence, Version 126.4. Version 2: Bidirectional Iteration26.5. Handling External Change26.5.1. stlsoft::external_iterator_invalidation26.6. winstl::child_window_sequence26.7. Bidirectional Iterator Blues26.7.1. end() Sentinels Gotcha26.7.2. Deadly Double Dereference26.7.3. When a Bidirectional Iterator Is Not a Forward Iterator but a Reversible Cloneable Iterator26.8. winstl::zorder_iterator: A Reversal of Self26.8.1. zorder_iterator Traits26.8.2. zorder_iterator_tmpl<>26.8.3. Reversed Semantics26.9. Finalizing the Window Peer Sequences26.10. Summary26.11. Z-Plane: Coda
27. String Tokenization
27.1. Introduction27.2. strtok()27.3. SynesisSTL::StringTokeniser27.4. Tokenization Use Cases27.5. Other Tokenization Alternatives27.5.1. strtok_r()27.5.2. IOStreams27.5.3. stlsoft::find_next_token()27.5.4. boost::tokenizer27.6. stlsoft::string_tokeniser27.6.1. stlsoft::string_tokeniser::const_iterator27.6.2. Selecting Categories27.6.3. stlsoft::string_tokeniser_type_traits27.6.4. stlsoft::string_tokeniser_comparator27.7. Test Drive27.7.1. Single-Character Delimiter27.7.2. Composite String Delimiter27.7.3. Preserving Blanks27.7.4. Copying versus Referencing: Considering Views27.7.4.1. s = view, v = view27.7.4.2. s = string, v = view27.7.4.3. s = view, v = string27.7.4.4. s = string, v = string27.7.5. Character Set Delimiter27.8. The Policy Folly27.8.1. Refactoring Template Parameters via Inheritance27.8.2. Type Generator Templates27.8.3. Handling Henney’s Hypothesis27.9. Performance27.10. Summary
28. Adapting COM Enumerators
28.1. Introduction28.2. Motivation28.2.1. Longhand Version28.2.2. Shorthand Version28.3. COM Enumerators28.3.1. IEnumXXXX::Next()28.3.2. IEnumXXXX::Skip()28.3.3. IEnumXXXX::Reset()28.3.4. IEnumXXXX::Clone()28.3.5. Different Value Types28.4. Decomposition of the Longhand Version28.5. comstl::enumerator_sequence28.5.1. Public Interface28.5.2. Member Types and Constants28.5.3. Value Policies28.5.4. Member Variables28.5.5. Construction28.5.6. Iteration Methods28.5.7. const-Incorrect Iterator Methods?28.5.8. Breaking Value Semantics?28.6. comstl::enumerator_sequence::iterator28.6.1. Construction28.6.2. Iteration Methods28.6.3. equal()28.7. comstl::enumerator_sequence::iterator::enumeration_context28.7.1. Why an Enumeration Context?28.7.2. Class Definition28.7.3. Construction28.7.4. Iterator Support Methods28.7.5. Invariant28.8. Iterator Cloning Policies28.8.1. comstl::input_cloning_policy28.8.2. comstl::forward_cloning_policy28.8.3. comstl::cloneable_cloning_policy28.9. Choosing a Default Cloning Policy: Applying the Principle of Least Surprise28.9.1. empty()28.10. Summary28.10.1. Why Not Default to Forward Iterators?28.10.2. Why Not Default to Input Iterators?28.10.3. Why Not Have a Fixed Quanta of 1?28.10.4. Why Not Use a Standard Container?28.11. Coming Next
29. Intermezzo: Correcting Minor Design Omissions with Member Type Inference
30. Adapting COM Collections
30.1. Introduction30.2. Motivation30.2.1. Longhand Version30.2.2. Shorthand Version30.3. comstl::collection_sequence30.3.1. Public Interface30.3.2. Member Types and Constants30.3.3. Construction30.3.4. Iteration: Using a Dirty Trick Cleanly30.3.5. size()?30.4. Enumerator Acquisition Policies30.5. Summary
31. Gathering Scattered I/O
31.1. Introduction31.2. Scatter/Gather I/O31.3. Scatter/Gather I/O APIs31.3.1. Linearizing with COM Streams31.3.2. platformstl::scatter_slice_sequence—A Teaser Trailer31.4. Adapting ACE_Message_Queue31.4.1. acestl::message_queue_sequence, Version 131.4.2. acestl::message_queue_sequence::iterator31.5. Time for Some Cake31.5.1. But Captain, I Canna’ Mek Her Goo Any Fastah!31.5.2. acestl::message_queue_sequence, Version 231.5.3. Specializing the Standard Library31.5.4. Performance31.6. Summary
32. Argument-Dependent Return-Type Variance
32.1. Introduction32.2. Borrowing a Jewel from Ruby32.3. Dual-Semantic Subscripting in C++32.4. Generalized Compatibility via String Access Shims32.5. A Fly in the int-ment32.6. Selecting Return Type and Overload32.6.1. Proscribing Signed Subscript Indexes32.7. Summary
33. External Iterator Invalidation
33.1. Element-Interface Coherence33.2. Windows ListBox and ComboBox Controls33.2.1. Retrieval Races?33.2.2. WinSTL listbox_sequence and combobox_sequence Classes33.3. Enumerating Registry Keys and Values33.3.1. So What’s the Problem?33.3.2. The WinSTL Registry Library33.3.3. Handling External Iterator Invalidation33.3.4. winstl::basic_reg_key_sequence33.4. Summary33.5. On the CD
Three. Iterators
34. An Enhanced ostream_iterator
34.1. Introduction34.2. std::ostream_iterator34.2.1. void Difference Type34.3. stlsoft::ostream_iterator34.3.1. Shims, Naturally34.3.2. Safe Semantics34.3.3. std::ostream_iterator Compatibility34.3.4. A Clash of Design Principles?34.4. Defining Stream Insertion Operators34.5. Summary
35. Intermezzo: Proscribing Fatuous Output Iterator Syntax Using the Dereference Proxy Pattern
35.1. stlsoft::ostream_iterator::deref_proxy
36. Transform Iterator
36.1. Introduction36.2. Motivation36.2.1. Using std::transform()36.2.2. Using the Transform Iterator36.3. Defining Iterator Adaptors36.3.1. Creator Functions36.3.2. Value Type36.4. stlsoft::transform_iterator36.4.1. Version 136.4.2. Construction36.4.3. Increment and Decrement Operators and Pointer Arithmetic Methods36.4.4. Comparison and Arithmetic Operators36.4.5. And the Problem Is . . .36.4.6. Version 236.4.7. stlsoft::transform_iterator36.5. Composite Transformations36.6. DRY SPOTViolations?36.6.1. Use Typedefs and Nontemporary Function Objects36.6.2. Use Heterogeneous Iterators and Algorithms36.6.3. Wear It, but Beware36.7. A Spoonful of Sequence Helps the Medicine . . . ?36.8. Summary36.9. On the CD
37. Intermezzo: Discretion Being the Better Part of Nomenclature . . .
38. Member Selector Iterator
38.1. Introduction38.2. Motivation38.2.1. std::accumulate()38.3. stlsoft::member_selector_iterator38.4. Creator Function Woes38.4.1. Nonmutating Access to a Non-const Array38.4.2. Nonmutating Access to a const Array38.4.3. Mutating Access to a Non-const Array38.4.4. Nonmutating Access to a Non-const Collection with Class-Type Iterators38.4.5. Nonmutating Access to a const Collection with Class-Type Iterators38.4.6. Mutating Access to a Collection with Class-Type Iterators38.4.7. Selecting const members38.5. Summary38.6. On the CD
39. C-Style String Concatenation
39.1. Motivation39.2. An Inflexible Version39.3. stlsoft::cstring_concatenator_iterator39.4. Creator Functions39.5. Summary39.6. On the CD
40. String Object Concatenation
40.1. Introduction40.2. stlsoft::string_concatenator_iterator40.3. Heterogeneity of String Types40.4. But . . .40.4.1. Assignability40.4.2. Dangling References40.4.3. Solution40.5. Summary
41. Adapted Iterators Traits
41.1. Introduction41.2. stlsoft::adapted_iterator_traits41.2.1. iterator_category41.2.2. value_type41.2.3. difference_type41.2.4. pointer41.2.5. reference41.2.6. const_pointer and const_reference41.2.7. effective_reference and effective_const_reference41.2.8. effective_pointer and effective_const_pointer41.2.9. Using the Traits41.3. Summary41.4. On the CD
42. Filtered Iteration
42.1. Introduction42.2. An Invalid Version42.3. Member Iterators Define the Range42.4. So . . . ?42.5. stlsoft::filter_iterator42.5.1. Forward Iterator Semantics42.5.2. Bidirectional Iterator Semantics42.5.3. Random Access Iterator Semantics42.6. Constraining the Iterator Category42.7. Summary42.8. On the CD
43. Composite Iterator Adaptations
43.1. Introduction43.2. Transforming a Filtered Iterator43.2.1. Creator Function43.3. Filtering a Transformed Iterator43.4. Hedging Our Bets43.5. Summary
Epilogue
Bibliography
Publications about STL:Books about other things:
CD-ROM Warranty

Content preview from Extended STL, Volume 1: Collections and Iterators

Chapter 3. Element Reference Categories

	In any revolutionary area, most of our current thinking is wrong.
	--David Suzuki

	If we had some ham, we could have some ham and eggs, if we had some eggs.
	--L. Hunter Lovin

Introduction

Q1:	When is an element reference not a reference?
A1:	When it’s elicited from a collection or an iterator that does not own its element(s).

That seems like a relatively uncontentious statement. As we will see, however, it has important and far-reaching implications for STL extensions. In this chapter, I will introduce the concept of an element reference category, which is a peer to the familiar concept of iterator category and just as important to STL extensions.

The reason you may not have heard of element reference categorization ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Imperfect C++ Practical Solutions for Real-Life Programming

Publisher Resources

ISBN: 9780321305503Purchase book

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

Extended STL, Volume 1: Collections and Iterators

by Matthew Wilson

Chapter 3. Element Reference Categories

Introduction

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.