iDog's Interview C++ Part 9

STL

Containers, Algorithms & Iterators

• Containers: classes whose purpose is to contain other objects
• Algorithms: manipulate the data stored in containers. They are global functions, usually taking two iterators to indicate the range in which it operates.
• Iterators: a generalization of pointers, ==, !=, ++ and * (dereferance) operators are overloaded (for some, more are overloaded). They make it possible to decouple algorithms from containers: algorithms (which are templates) are parameterized by the type of iterator.

Iterators are the major feature which allow the generality of the STL. For example, an algorithm to reverse a sequence can be implemented using bidirectional iterators, and then the same implementation can be used on lists, vectors and deques. User-created containers only have to provide an iterator which implements one of the 5 standard iterator interfaces, and all the algorithms provided in the STL can be used on the container.

This generality also comes at a price at times. For example, performing a search on an associative container such as a map or set can be much slower using iterators than by calling member functions offered by the container itself. This is because an associative container's methods can take advantage of knowledge of the internal structure, which is opaque to algorithms using iterators.

Example of an algorithm:

// search in range [first, last) for value
// I: input iterator; T: data type
template <typename I, typename T>
I find(I first, I last, const T& value)
{
    while(first != last && *first != value) ++first;
    return first;
}

Concepts & Modeling

• Concepts: a set of type requirements
• Modeling: if a type satisfies all of the specified requirements of a concept, the type conforms to this concept, or we can say that the type is a model of this concept.

Refinement: Bidirectional Iterator is a refinement of Input Iterator, since it defines not only all requirements (=, , ++, *) of Input Iterator, but also --.

Five iterator concepts:

• Input Iterator: can only be used to read a sequence of values
• Output Iterator: can only be used to write a sequence of values
• Forward Iterator: can be read, written to, and move forward
• Bidirectional Iterator: like forward iterators but can also move backwards
• Random Access Iterator: can move freely any number of steps in one operation

It is possible to have bidirectional iterators act like random access iterators, as moving forward ten steps could be done by simply moving forward a step at a time a total of ten times. However, having distinct random access iterators offers efficiency advantages. For example, a vector would have a random access iterator, but a list only a bidirectional iterator.

Refinement of them:

Input Iterator --> Forward Iterator --> Bidirectional Iterator --> Random Access Iterator

Output Iterator doesn't have refinement relationships with the above four.

Containers' concepts: All containers are models of concept Container.

Other Components

Besides containers, algorithms and iterators, there are also following components in STL:

• Functors: function objects, a generalization of functions.
• Utinities: very basic concepts and functions widely used in STL, like Assignable concept.
• some low-level mechanisms for allocating & deallocating memory, such as Allocator concept. These can be safely ignored for almost all purposes.

Notes

• STL containers are not intended to be used as base classes (their destructors are deliberately non-virtual). Deriving from a container is a common mistake made by novices.
• iterator issue: if a value pointed to by the iterator is deleted, the iterator itself is then no longer valid. This is a common source of errors. Most implementations of the STL provide a debug mode which is slower but can locate such errors if used. A similar problem exists in Java.
• The set of algorithms is not complete — for example, the copy_if algorithm was left out by oversight (added in C++0x)