The Standard Template Library: Generic Programming
This chapter is from the book
This chapter is from the book
This chapter is from the book
The Standard Template Library (STL) consists of two primary components: a set of container classes (including the vector, list, set, and map classes) and a set of generic algorithms to operate over these containers, including find(), sort(), replace(), and merge().
The vector and list container classes represent sequential containers. A sequential container maintains a first element, a second element, and so on through a last element. We primarily iterate over a sequential container. The map and set classes represent associative containers. An associative container supports fast lookup of a value.
A map is a key/value pair: The key is used for lookup, and the value represents the data we store and retrieve. A telephone directory, for example, is easily represented by a map. The key is the individual's name. The value is the associated phone number.
A set contains only key values. We query it as to whether a value is present. For example, if we were to build an index of words that occur in news stories, we would want to exclude neutral words such as the, an, but, and so on. Before a word is entered into the index, we query an excluded_word set. If the word is present, we discard it; otherwise, we include the word in our index.
The generic algorithms provide a large number of operations that can be applied both to the container classes and to the built-in array. The algorithms are called generic because they are independent of both the type of element that they are operating on (for example, whether it is an int, double, or string) and the type of container within which the elements are held (whether it is a vector, list, or built-in array).
The generic algorithms achieve type independence by being implemented as function templates. They achieve container independence by not operating directly on the container. Instead, they are passed an iterator pair (first,last), marking the range of elements over which to iterate. While first is unequal to last, the algorithm operates on the element addressed by first, increments first to address the next element, and then recompares first and last for equality. A good first question is, what is an iterator? The next two sections try to answer that.