This chapter introduces three key components of the Standard Library—containers (templatized data structures), iterators and algorithms. Containers are data structures capable of storing objects of almost any data type (there are some restrictions). We’ll see that there are three styles of container classes—first-class containers, container adapters and near containers.

Each container has associated member functions—a subset of these is defined in all containers. We illustrate most of this common functionality in our examples of array (which was introduced in Chapter 7), vector (also introduced in Chapter 7 and covered in more depth here), list (Section 15.5.2) and deque (pronounced “deck”; Section 15.5.3).

Iterators, which have properties similar to those of pointers, are used to manipulate container elements. Built-in arrays also can be manipulated by Standard Library algorithms, using pointers as iterators. We’ll see that manipulating containers with iterators is convenient and provides tremendous expressive power when combined with Standard Library algorithms—in some cases, reducing many lines of code to a single statement.

Standard Library algorithms are function templates that perform such common data manipulations as searching, sorting and comparing elements or entire containers. The Standard Library provides many algorithms. Most of them use iterators to access container elements. Each algorithm has minimum requirements for the kinds of iterators that can be used with it. We’ll see that containers support specific kinds of iterators, some more powerful than others. The iterators a container supports determine whether the container can be used with a specific algorithm. Iterators encapsulate the mechanisms used to traverse containers and access their elements. This encapsulation enables many of the algorithms to be applied to various containers independently of the underlying container implementation. This also enables you to create new algorithms that can process the elements of multiple container types.

In Chapter 19, we’ll build our own custom templatized data structures, including linked lists, queues, stacks and trees:

• Linked lists are collections of data items logically “lined up in a row”—insertions and removals are made anywhere in a linked list.

• Stacks are important in compilers and operating systems: Insertions and removals are made only at one end of a stack—its top. Section 6.11 discussed the importance of stacks in the function call and return mechanism.

• Queues represent waiting lines; insertions are made at the back (also referred to as the tail) of a queue and removals are made from the front (also referred to as the head) of a queue.

• Binary trees are nonlinear, hierarchical data structures that facilitate searching and sorting data, duplicate elimination and compiling expressions into machine code.

Each of these data structures has many other interesting applications. We’ll carefully weave linked objects together with pointers. Pointer-based code is complex and can be error prone—the slightest omissions or oversights can lead to serious memory-access violations and memory-leak errors with no forewarning from the compiler. If many programmers on a large project implement custom containers and algorithms for different tasks, the code becomes difficult to modify, maintain and debug.