Instances of a container class are stores for other types of objects generically called storables. The relationship between a store and a storable is a special type of association called aggregation. A container provides basic operations for inserting, retrieving, and removing storables.

In a heterogeneous container Storable is an abstract base class:

In a homogeneous (or heterogeneous) container Storable can be a template parameter:

Containers differ in how remove(), insert(), and retrieve() are implemented. In a random access container, each stored item is identified by a unique index corresponding to its position in the container. Accessing stored elements is very efficient, but inserting and deleting elements can be expensive. Arrays are random access containers.

In a sequential access container a movable cursor designates a current element. remove() and retrieve() always refer to the current element. Insert() always takes place immediately before or after the current element. Inserting and removing are very efficient, but retrieving involves a sequential search. Files and linked lists are examples of sequential stores.

Locations in an associative access container are designated by unique or semi-unique keys associated with or computed from the storable elements. Retrieving an element is very efficient if the element's key is known. Tables and trees are examples of associative access stores.

Elements are retrieved or removed from a temporal access container according to when they were inserted into the container. LIFO and FIFO stores are examples.

A container is actually a handle that manages a potentially complicated C-style data structure such as an AVL tree, hash table, or doubly linked list (see the Handle-Body idiom). Fortunately, implementing these data structures is largely an academic exercise these days (but a good one). This is because the standard C++ library now comes with a collection of container templates called the standard template library (STL):

An iterator is an abstract pointer to an element in a sequence. A sequence can be an array, a container, a stream, or a string. Like pointers, iterators can be incremented, decremented, compared, or dereferenced.

For example, we can initialize an array using index numbers:

but we could just as easily use a pointer to traverse the array:

A pointer into an array is an example of an iterator.

We could do the same for a vector. Here we declare an integer vector, then use index numbers to initialize it:

Iterators for vectors may be implemented quite differently from pointers, list, deque, and map iterators (stacks and queues don't have iterators). The iterator type for any container class is given the name iterator inside the class using typedef or inner classes, so declaring an iterator requires qualifying the iterator type name with the container class name:

Initializing an iterator to the beginning of a container, or comparing it to the end of the container requires the container to provide fixed iterators "pointing" to the first element and just beyond the last element. All container classes provide begin() and end() functions for this purpose. The following statement produces the exact same result as the earlier for statement:

There are different categories of iterators. Output iterators only allow increment and read operations:

Input iterators only allow increment, compare, and write operations:

Forward iterators are both input and output iterators. Bidirectional iterators are forward iterators that can also be decremented:

Random access iterators are bidirectional iterators that can be incremented and decremented by random amounts:

Independent of category, an iterator can be declared const or non-const.

STL iterators are instances of the iterator design pattern discussed in Gamma, et al.'s book Design Patterns. They are particularly important in the context of sequential stores such as lists. Sharing a list is difficult because an apparently non destructive operation, such as printing the list, can actually be destructive if it moves the list's internal cursor. An iterator is like an external cursor provided and owned by the client. Modifying an iterator has no effect on iterators owned by other clients of the list.

Streams and strings are sequences, so iterators can be used with them, too:

Here are some of the header files you need to include if you want to use STL:

Assume c is a container of type yyy<xxx>. Assume x is of type xxx and p is of type yyy::iterator. Here are the most common operations:

Vectors encapsulate heap arrays. They automatically grow to accomodate any number of elements. The elements in a vector can be accessed and modified using iterators or indeces.

To begin, let's provide a template for printing vectors. We use a constant iterator:

The next function demonstrates the basic vector operations:

Here's the output produced by this function:

Exercise

Implement and test a reusable vector reader:

Users must enter vectors as sequences seperated by white space and bracketed by parenthesis. Should you use a constant or variable iterator?

Warning

I have found some of the STL containers in VC++ assume the members of the Storable class can be compared using == and <. Thus, vector<Employee> isn't allowed (unless Employee::operator==() and Employee::operator<() have been defined), but vector<Employee*> is okay. A related bug seems to prevent storing of the standard complex numbers, as in stack<complex<double> >.

As before, we begin with a list writer. Only two changes are needed from the vector writer:

The test function shows some of the differences between lists and vectors.

Here's the program output:

By themselves, deques (rhymes with "checks") are relatively useless. They are optimized for inserting and removing elements at either end, hence are ideal adaptees for stacks and queues.

A map contains pairs (a standard C++ library type):

Here are template functions for writing pairs and maps:

If m is a map and k is a key, then m.find(k) returns an iterator pointing to the first pair in m having key == k, otherwise m.end() is returned. Here's a template function that can be used to find the value associated with a particular key:

Here's a sample program:

Unfortunately, VC++ couldn't figure out if the Key parameter in the find template should be a string or a char*, so I had to perform a manual cast. Here's the program's output. Notice that the entries in a map are automatically sorted by key:

We can use m[k] to search a map m for a key k instead of the find template defined above. However, if the search fails, a "null" value will be associated with k and inserted into m. For objects, the null value is the value constructed by the default constructor. For numbers and pointers, the null value is 0. Sometimes we can use this to our advantage. The following short program counts the number of occurrences of each word in a given file, then displays the result:

The adapter design pattern allows us to change the interface of a class without changing its implementation or functionality. This can either be done using delegation or private inheritance:

Stacks, queues, and priority queues are adapters for sequences. The delegation implementation is used. Both queue and stack provides a push, pop, top interfaces to a deque. Of course queue<>::push() means enqueue() and queue<>::pop() means dequeue(). For example:

Printing and traversing stacks and queues can be difficult because the underlying deque, always called c, is a protected member. The only way around this is to subclass stack<Item>, so c becomes visible. We can call our derived class stack<>, too, if we leave the STL stack<> and deque<> names in the std namespace. Here are the includes and using declarations we need:

A writer for deques is needed:

Our stack template:

Finally, a writer for stacks:

We assume the adaptee type is the default deque<Storable> because VC++ doesn't provide a name for it. A more standard compiler should allow: