Data Structure Programming

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.