Using the STL: The C++ Standard Template Library

A lot has happened since the first edition of this book was written. When the first edition was prepared, there was only one version of the Standard Template Library (STL) available-the Hewlett-Packard version. Since then, several other versions have appeared from major compiler and library vendors. This is in an effort to conform to the recent International Standards Organization/International Electrotechnical Commission (ISO/IEC) C++ standards, which define the STL as part of the Standard C++ Library. As expected, the STL is becoming widely available and an accepted part of C++ program development. This is good. Unfortunately, the proliferation of implementations makes it difficult to exactly define the STL. We now have mul­ tiple implementations, many of which are slightly incompatible with one another. The reasons for this are largely due to different capabilities of the compilers on which they are implemented. Many compilers do not implement the most recent features of the language since production of standards often precedes conform­ ing implementations by many months. This will improve over time as the com­ pilers add the necessary capabilities to support the full STL.

1 Introduction.- 1.1 What Is the STL?.- 1.2 History.- 1.3 STL Components.- 1.4 Generic Algorithms.- 1.4.1 C++ Templates.- 1.5 Iterators.- 1.6 Standard Exceptions.- 1.7 Complexity.- 1.7.1 Analyzing Complexity.- 1.8 Thread Safety.- 1.9 Namespaces.- 1.10 Overview of This Book.- 2 Iterators.- 2.1 Introduction.- 2.2 Pointers as Iterators.- 2.3 Iterator Classes.- 2.3.1 Input Iterators.- 2.3.2 Output Iterators.- 2.3.3 Forward Iterators.- 2.3.4 Bidirectional Iterators.- 2.3.5 Random Access Iterators.- 2.4 Using Iterators.- 2.4.1 Stream Iterators.- 2.4.2 Forward Iterators.- 2.4.3 Bidirectional Iterators.- 2.4.4 Random Access Iterators.- 2.5 Iterator Functions.- 2.6 Iterator Tags.- 2.7 Iterator Traits.- 3 The STL Algorithms.- 3.1 Introduction.- 3.2 Operators.- 3.3 Function Objects.- 3.4 The STL Algorithms.- 3.4.1 Algorithm Categories.- 4 Sequence Algorithms.- 4.1 Introduction.- 4.2 Preliminaries.- 4.2.1 Pairs.- 4.3 Nonmutating Sequence Algorithms.- 4.3.1 Counting.- 4.3.2 Finding.- 4.3.3 Finding Members.- 4.3.4 Finding Adjacent Values.- 4.3.5 ForEach.- 4.3.6 Mismatching Values.- 4.3.7 Sequence Equality.- 4.3.8 Searching.- 4.4 Mutating Sequence Algorithms.- 4.4.1 Copy.- 4.4.2 Swapping.- 4.4.3 Filling.- 4.4.4 Generate.- 4.4.5 Replace.- 4.4.6 Transform.- 4.4.7 Remove.- 4.4.8 Unique.- 4.4.9 Reverse.- 4.4.10 Rotate.- 4.4.11 Random Shuffle.- 4.4.12 Partitioning.- 5 Sorting and Related Algorithms.- 5.1 Introduction.- 5.2 Preliminaries.- 5.3 Sorting.- 5.3.1 Nth Element.- 5.4 Searching Algorithms.- 5.4.1 Binary Search.- 5.4.2 Lower Bound.- 5.4.3 Upper Bound.- 5.4.4 Equal Range.- 5.4.5 Merge.- 5.5 Set Algorithms.- 5.5.1 Includes.- 5.5.2 Set Union.- 5.5.3 Set Intersection.- 5.5.4 Set Difference.- 5.5.5 Set Symmetric Difference.- 5.6 Heap Algorithms.- 5.7 Miscellaneous Algorithms.- 5.7.1 Maximum and Minimum.- 5.7.2 Lexicographical Comparison.- 5.7.3 Permutations.- 6 Generalized Numeric Algorithms.- 6.1 Introduction.- 6.2 Accumulation.- 6.3 Inner Product.- 6.4 Partial Sum.- 6.5 Adjacent Difference.- 6.6 Numeric Arrays.- 6.6.1 Subscripting.- 6.6.2 Methods and Functions.- 7 Sequence Containers.- 7.1 Introduction.- 7.2 Container Operations.- 7.3 Vectors.- 7.3.1 Bit Vectors.- 7.4 Lists.- 7.4.1 List Implementation.- 7.4.2 List Examples.- 7.4.3 List Operations.- 7.5 Deques.- 7.5.1 Deque Implementation.- 7.6 Choosing a Sequence Container.- 7.7 Strings.- 7.7.1 Character Traits.- 8 Associative Containers.- 8.1 Introduction.- 8.2 Associative Container Operations.- 8.3 Sets.- 8.4 Multisets.- 8.5 Maps.- 8.5.1 Multimaps.- 8.6 Associative Container Implementation.- 8.6.1 Trees.- 8.6.2 Hash Tables.- 8.7 Hash Table Implementations.- 8.8 Container Selection.- 9 Adaptors.- 9.1 Introduction.- 9.2 Container Adaptors.- 9.3 The Stack.- 9.4 Queues.- 9.5 Priority Queues.- 9.6 Iterator Adaptors.- 9.6.1 Reverse Iterators.- 9.6.2 Insert Iterators.- 9.7 Function Adaptors.- 9.7.1 Not1.- 9.7.2 Not2.- 9.7.3 Pointers to Functions and Methods.- 9.7.4 ptr_fun.- 10 Memory Management.- 10.1 Introduction.- 10.2 Allocators.- 10.3 Uninitialized Memory Operations.- 10.3.1 Raw Storage Iterators.- 10.3.2 Other Uninitialized Memory Operations.- 10.4 Temporary Buffers.- 10.5 auto_ptr.- 11 Putting the STL to Work.- 11.1 Introduction.- 11.2 A Banking Problem.- 11.3 Symbol Tables.- 11.3.1 A Cross-Reference Generator.- 11.3.2 Hierarchical Symbol Tables.- 12 The Story Continues.- 12.1 Introduction.- 12.2 The Future.- 12.3 Summary.- Appendix A STL Header Files.- Appendix B The STL Reference.- References.