Files for the book are here. They are NOT guaranteed to be bug free. Some of them were left in an incomplete state.

The book was written before the standard was finalized. To see how to use the book (and the STL) with the final version of the standard look here.

The first printing has a few errors. Here is the errata sheet.

The following presents one chapter of a first draft of a book I am writing in which the Standard Template Library would be used to teach data structures. I think of this version as a bare tree that requires a lot of additional decoration in the form of student tasks and examples. It does, however, describe how the STL differs from other libraries and hints at why using the STL in the data structures course is a real challenge. It also gives the relationship between pointers and iterators, an understanding of which is fundamental to the STL. If your only interest here is in getting some ideas about the STL focus on sections 2.2, 2.3, 2.6, 2.7.2, and 2.8. Note also that run time bounds are part of the specification of every algorithm in the STL. This is the reason for the rather long section 2.7.5.

The following table of contents represents the current state of the work.
It will be updated from time to time as progress is made.

Joseph Bergin

November, 1996

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.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. (Incomplete)

**Chapter 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 and Graph Storage

3.7 Hashed Storage

3.8 Summary

3.9 Exercises

**Chapter 4. Overview of the Standard Template Library.**

4.1. Components of the STL

4.2 A Motovating Example: A Spelling 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.9 Permutation Generation Operations

4.5.10 Miscelaneous 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.2.1 Stack Adaptor

4.7.2.2 Queue Adaptor

4.7.2.3 Priority Queue Adaptor

4.7.3 Iterator Adaptors.

4.7.3.1 Reverse Iterators

4.7.3.2 Insert Iterators

4.8 Allocators

4.9 Summary

4.10 Exercises

**Chapter 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.9 A Graph Implemented with STL vectors

5.11 Summary

5.12 Exercises

**Chapter 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`s

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

**Chapter 7. List Programming.**

7.1. Implementation Strategies of STL Lists

7.2. Properties of STL Lists.

7.3 A Simple Implementaton 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 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

**Chapter 8. Set and Map Programming.**

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-4 Trees

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

**Chapter 9. Heap Programming.**

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 Reorgainzation 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

**Appendix. STL Summary.**

A.1 Algorithms prototypes

A.1.1. Maximum and Minimum

A.1.2. Generalized Numeric Operations

A.1.3 Nonmutating Sequence Operations

A.1.4 Mutating Sequence Operations

A.1.5. Sorting Related Operations

A.1.6. Set Operations on Sorted Structures

A.1.7. Heap Operations

A.1.8. Lexicographical Compare Operations

A.1.9. Permutation Generator Operations

A.1.10. Miscelaneous Operations

A.2 Containers

A.2.1 Sequential Containers

A.2.2 Sorted Associative Containers

A.3 Adaptors

A.3.1 Container Adaptors

A.3.1.1 Stack Adaptor

A.3.1.2 Queue Adaptor

A.3.1.3 Priority Queue Adaptor

Back to Joseph Bergin's Home Page