Previous Table of Contents Next


7.6.4.2. Associative Containers

Associative containers keep their elements sorted, which makes it easy to determine quickly whether a particular element is in the container. Indeed, there are operations that do more than that, such as determining the first element that is greater than a particular value, less than a particular value, and so on.

Of course, this property carries with it the requirement that the elements in the container must have < appropriately defined on them. Most of the fundamental types have appropriate definitions of <; users who define their own types must define < themselves if they wish objects of those types to be held by associative containers.

The two main associative containers are set and map. A set is just that; any particular value appears in a set only once, and there are efficient operations to test if particular values are there, combine sets in various ways, and so on.

We have already seen the map class; we can think of a map as a set of key-value pairs, sorted by key, with the requirement that all the keys be distinct. Indeed, the library provides a template called pair, and it is possible to treat a map<K, V> object as a sequence of pair<const K, V> values.

In addition to set and map, there are multiset and multimap. The difference between the multi- and the other versions is that they allow multiple elements with the same value.

It should be easy to see why a multimap is useful. For example, we might keep track of student registration with a multimap<Student, Course> object. Such an object would store student-course pairs, so if a student was enrolled in n courses, there would be n distinct pairs for that student.

It is less obvious why a multiset should be useful. What does a multiset<T> buy us that a map<T, int> doesn’t? We could, after all, associate a count with each T value; that count would represent “how many times” the value appears in the multiset.

It turns out, however, that there is an important distinction: Values that are equal might not be identical. For example, some operating systems do not distinguish between files that are equal except for the case of the letters in their names. On such an operating system, FOO and foo would be two names for the same file. If we were writing programs to run under such an operating system, we might want to define a class that represents file names. Such a class might plausibly have the property that two file names are equal even though the characters that constitute them are not. In such a case, it might be important to keep track of several different files that are equal, and yet to remember that they had distinct names for printing purposes. A multiset would be just the type to do this.

7.6.4.3. Compound Containers

In addition to the sequential and associative containers, there are a few templates that can be used to build containers from other containers. For example, there is not a single stack class. Instead, there is a stack template that can use either a vector, a list, or a deque to implement the stack. Similarly, there is a queue container that works on top of some other container.

It is not necessary for these compound containers to built on top of standard containers; user-defined container classes can also be used as the basis for a stack or a queue, provided only that the user-defined containers have the right properties. Those properties are documented as part of the library specification.

7.6.5. Iterators

We have already noted that the various sequential containers have several properties in common. This suggests that it is desirable to be able to write programs that take advantage only of those properties, without direct knowledge of the types of containers they are using. The C++ library encapsulates knowledge of such properties into iterators. Loosely speaking, an iterator is an object of a type (or, sometimes, the type itself) that supports a set of operations that allow it to be used to mark a place in a container. More specifically, it is an object that acts enough like a pointer to make it possible to pretend it is a pointer.

The library recognizes five kinds of iterators. The two simplest, and most common, are input iterators and output iterators. If p is an input iterator, then *p, p++, ++p, and p->member must have their usual meanings. Moreover, if p and q are input iterators, p==q must be true if and only if p and q refer to the same place in the input sequence.

Output iterators are similar to input iterators except for the meaning of *p. If p is an output iterator, *p can be used only on the left side of an assignment. Moreover, each distinct value of p must have *p used on the left of an assignment exactly once.

An example of an algorithm that uses input and output iterators is copy:

   template<class In, class Out>
   Out copy(In begin, In end, Out result)
   {
       while (begin != end)
             *result++ = *begin++;
       return result;
   }

This algorithm relies only on the properties of input and output iterators. It is clear that it can be used to copy elements of (built-in) arrays:

   int x[100], y[100];
   // ...
   copy(x, x+100, y);

Recall that because x and y are arrays, uttering their names yields the addresses of their initial elements. Therefore, x+100 is the address of one past the last element of the array x. The copy algorithm uses these pointers to copy the elements of the array x into y.


Previous Table of Contents Next