Data Structure Programming With the Standard Template Library in C++

Once programmers have grasped the basics of object-oriented programming and C++, the most important tool that they have at their disposal is the Standard Template Library (STL). This provides them with a library of re-usable objects and standard data structures. It has recently been accepted by the C++ Standards Committee. This textbook is an introduction to data structures and the STL. It provides a carefully integrated discussion of general data structures and their implementation and use in the STL. In so doing, the author is able to teach readers the important features of abstraction and how to develop applications using the STL.

1. Data Structures and Algorithms.- 1.1 Data Abstraction and Encapsulation.- 1.2 Classes, Data Abstraction, Encapsulation, and Information Hiding.- 1.3 Derived Classes. Object Orientation.- 1.4 Templates.- 1.5 Which Data Abstractions Are Useful?.- 1.6 Abstractions Provided by the STL.- 1.7 Summary.- 1.8 Exercises.- 2. Programming with Arrays and Pointers.- 2.1 Arrays.- 2.2 Pointers and Arrays.- 2.3 Pointer Arithmetic.- 2.4 Arrays with More than One Dimension.- 2.5 Putting It Together. An Application.- 2.6 How the STL Generalizes Arrays and Pointers.- 2.7 Some Common Problems. Searching and Sorting.- 2.8 Using Arrays with the STL.- 2.9 Another Example. A Simple Database.- 2.10 Arrays That Contain Pointers.- 2.11 Another Use for Pointers—Lists.- 2.12 Summary.- 2.13 Exercises.- 3. Overview of Container Mechanisms.- 3.1 Storage Mechanisms.- 3.2 Dense Storage.- 3.3 An Extended Example Part 1: The Array Stack.- 3.4 Linked Storage.- 3.5 An Extended Example Part 2: The Linked Stack.- 3.6 Tree Storage.- 3.7 Graph Storage.- 3.8 Hashed Storage.- 3.9 Indexed Storage.- 3.10 Summary.- 3.11 Exercises.- 4. Overview of the Standard Template Library.- 4.1 Components of the STL.- 4.2 A Motivating Example: A Spell Checker.- 4.3 Containers.- 4.4 Iterators.- 4.5 Generic Algorithms.- 4.6 Function Objects.- 4.7 Adaptors.- 4.8 Allocators.- 4.9 Summary.- 4.10 Exercises.- 5. Vector Programming.- 5.1 Vectors—Expandable Arrays.- 5.2 The Indexing Problem.- 5.3 How We Can Implement Vectors.- 5.4 Memory Management.- 5.5 Adding to the Functionality of ExpandableArrays.- 5.6 Programming with Expandable Arrays.- 5.7 Building a Stack Adaptor.- 5.8 The STL vector Template.- 5.9 A Graph Implemented with STL vectors.- 5.10 Summary.- 5.11 Exercises.- 6. Dequeue Programming.- 6.1 Queues and Double-EndedQueues.- 6.2 Implementing a Dequeue.- 6.3 A Simple deque Example.- 6.4 The deque Interface.- 6.5 Efficiency of deque.- 6.6 More on Container Adaptors—The queue Adaptor.- 6.7 Priority Queues and Heaps.- 6.8 STL Generic Algorithms—Searching and Sorting.- 6.9 Median and Other Order Statistics.- 6.10 Merging.- 6.11 Summary.- 6.12 Exercises.- 7. Lists.- 7.1. Implementation Strategies of STL Lists.- 7.2. Properties of STL Lists.- 7.3 A Simple Implementation of Circular Lists.- 7.4 An Alternate Implementation of Lists.- 7.5 The Iterator Invalidation Problem and Its Solution.- 7.6 Techniques for STL Lists.- 7.7 Summary.- 7.8 Exercises.- 8. Sets, Maps, Multisets, and MultiMaps.- 8.1 Sequential Versus Sorted Containers.- 8.2 Binary Trees.- 8.3 Binary Search Trees.- 8.4 Balanced Binary Search Trees.- 8.5 2-3-4Trees.- 8.6 Red-Black Trees.- 8.7 Sets and Multisets.- 8.8 Maps and Multimaps.- 8.9 An Implementation of Red-Black Trees.- 8.10 Summary.- 8.11 Exercises.- 9. Hash Tables.- 9.1. Hashed Associative Containers and the STL.- 9.2 Simple Hashing—Separate Chaining.- 9.3 Simple Hashing—Circular Hashing.- 9.4 Variations on Simple Hashing.- 9.5 Hash Functions.- 9.6 Reorganization of a Hash Table.- 9.7 Using Hashed Structures.- 9.8 Elements of an Implementation.- 9.9 Design Issues.- 9.10 Extending the Standard Template Library.- 9.11 Summary.- 9.12 Exercises.