The STL is increasingly becoming an extension to the language that will be supported by most if not all C++ compilers. It provides a collection of generic data structures and algorithms and has been adopted by the ANSI committee for the standardisation of C++. Its principal strengths are that: * the STL generalises the concept of iterator * the STL algorithms can be used on regular arrays, thus increasing the applicability of the algorithms * the STL pays particular attention to the efficiency of the algorithms used.
This book provides a comprehensive introduction and guide to the STL, pitched at the level of readers already familiar with C++. It presents a thorough overview of the capabilities of the STL, detailed discussions of the use of containers, descriptions of the algorithms and how they may be used, and how the STL may be extended. Finally, an appendix provides an alphabetical reference to the entire STL. As a result, programmers of C++ and students coming to the STL for the first time will find this an extremely useful hands-on text.

1 Introduction.- 1.1 What Is STL?.- 1.2 History.- 1.3 STL Components.- 1.4 Generic Algorithms.- 1.4.1 C++ Templates.- 1.5 Iterators.- 1.6 Complexity.- 1.6.1 Analyzing Complexity.- 1.7 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.- 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.3 Non-Mutating Sequence Algorithms.- 4.3.1 Counting.- 4.3.2 Finding.- 4.3.3 Finding Adjacent Values.- 4.3.4 ForEach.- 4.3.5 Mismatching Values.- 4.3.6 Sequence Equality.- 4.3.7 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 EqualRange.- 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 Symmetric Set 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 Numeric Algorithms.- 6.2 Accumulation.- 6.3 Inner Product.- 6.4 Partial Sum.- 6.5 Adjacent Difference.- 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.- 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 Experimental Hash Table Implementation.- 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.6.3 Raw Storage Iterators.- 9.7 Summary.- 10 Allocators.- 10.1 Introduction.- 10.2 The PC Memory Model.- 10.3 The Allocator Solution.- 10.3.1 The Allocator Interface.- 10.4 Summary.- 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.- 11.4 Reversing Sequences.- 12: The Story Continues.- 12.1 Introduction.- 12.2 The Future.- 12.2.1 Persistence.- 12.2.2 Safety.- 12.3 Summary.- References.- Appendix A: The STL Reference.