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.1.1 An Example. A Guessing Game.- 2.1.2 Another Example. Array of Objects.- 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.7.1 Linear Search in Arrays.- 2.7.2 Selection Sort.- 2.7.3 Binary Search.- 2.7.4 Quicksort.- 2.7.5 The Efficiency of These Algorithms.- 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.3.1 Sequence Containers.- 4.3.2 More on the Spell Checker.- 4.3.3 Sorted Associative Containers.- 4.3.4 Rebuilding the Spelling Dictionary as a Set.- 4.4 Iterators.- 4.4.1 Forward Iterators.- 4.4.2 Bidirectional Iterators.- 4.4.3 Random Access Iterators.- 4.4.4 Input Iterators.- 4.4.5 Output Iterators.- 4.4.6 Istream and Ostream Iterators.- 4.5 Generic Algorithms.- 4.5.1 Minimum and Maximum Algorithms.- 4.5.2 Generalized Numeric Algorithms.- 4.5.3 Nonmutating Sequence Operations.- 4.5.4 Mutating Sequence Operations.- 4.5.5 Sorting Related Operations.- 4.5.6 Set Operations on Sorted Structures.- 4.5.7 Heap Operations.- 4.5.8 Lexicographical Compare Operations.- 4.5.9 Permutation Generation Operations.- 4.5.10 Miscellaneous Additional Operations.- 4.6 Function Objects.- 4.6.1 Arithmetic Operations.- 4.6.2 Comparison Operations.- 4.6.3 Logical Operations.- 4.7 Adaptors.- 4.7.1 Function Adaptors.- 4.7.2 Container Adaptors.- 4.7.3 Iterator 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-Ended Queues.- 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.7.1 Heaps.- 6.7.2 Priority Queues.- 6.8 STL Generic Algorithms—Searching and Sorting.- 6.8.1 Generalized Searching.- 6.8.2 Sorting.- 6.8.3 Searching Sorted Containers.- 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.3.1 Sorting a List.- 7.3.2 Recursive List Operations.- 7.3.3 Some Difficulties with This Implementation.- 7.4 An Alternate Implementation of Lists.- 7.5 The Iterator Invalidation Problem and Its Solution.- 7.6 Techniques for STL Lists.- 7.6.1 Finding an Item in a Sorted List.- 7.6.2 Inserting into a Sorted List.- 7.6.3 Applying an Arbitrary Function to Each Element of a List.- 7.6.4 Splicing Lists.- 7.6.5 Merging Sorted Lists.- 7.6.6 Reversing a List.- 7.6.7 Building a Spelling Dictionary.- 7.6.8 A Merge Sort Suitable for 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.8.1 The Hash Table.- 9.8.2 Sets and Maps.- 9.8.3 Using the Sets and Maps.- 9.9 Design Issues.- 9.10 Extending the Standard Template Library.- 9.11 Summary.- 9.12 Exercises.