The Standard Template Library

Item 4. The Standard Template Library

A short description of the standard template library (STL) cannot do its design justice. What follows is an appetizer to encourage you to study the STL in depth.

The STL isn't really a library. It's an inspired idea and a set of conventions.

The STL consists of three major kinds of components: containers, algorithms, and iterators. Containers contain and organize elements. Algorithms perform operations. Iterators are used to access the elements of a container. This is nothing new, as many traditional libraries have these components, and many traditional libraries are implemented with templates. The STL's inspired idea is that containers and the algorithms that operate on them need no knowledge of each other. This sleight of hand is accomplished with iterators.

An iterator is like a pointer. (In fact, pointers are one kind of STL iterator.) Like a pointer, an iterator can refer to an element of a sequence, can be dereferenced to get the value of the object to which it refers, and can be manipulated like a pointer to refer to different elements of a sequence. STL iterators may be predefined pointers, or they may be user-defined class types that overload the appropriate operators to have the same syntax of use as a predefined pointer (see Smart Pointers [42, 145]).

An STL container is an abstraction of a data structure, implemented as a class template. As with different data structures, different containers organize their elements in different ways to optimize access or manipulation. The STL defines seven (or, if you count string, eight) standard containers, and several widely accepted nonstandard containers are available.

An STL algorithm is an abstraction of a function, implemented as a function template (see Generic Algorithms [60, 221]). Most STL algorithms work with one or more sequences of values, where a sequence is defined by an ordered pair of iterators. The first iterator refers to the first element of the sequence, and the second iterator refers to one past the last element of the sequence (not to the last element). If the iterators refer to the same location, they define an empty sequence.

Iterators are the mechanism by which containers and algorithms work together. A container can produce a pair of iterators that indicates a sequence of its elements (either all its elements or a subrange), and an algorithm operates on that sequence. In this way, containers and algorithms can work closely together while remaining ignorant of each other. (The beneficial effect of ignorance is a recurring theme in advanced C++ programming. See Polymorphism [2, 3], Factory Method [30, 103], Commands and Hollywood [19, 67], and Generic Algorithms [60, 221].)

In addition to containers, algorithms, and iterators, the STL defines a number of ancillary capabilities. Algorithms and containers may be customized with function pointers and function objects (see STL Function Objects [20, 71]), and these function objects may be adapted and combined with various function object adapters.

Containers may also be adapted with container adapters that modify the interface of the container to be that of a stack, queue, or priority queue.

The STL relies heavily on convention. Containers and function objects must describe themselves through a standard set of nested type names (see Embedded Type Information [53, 189], Traits [54, 193], and STL Function Objects [20, 71]). Both container and function object adapters require that member functions have specific names and contain specific type information. Algorithms require that iterators passed to them be able to support certain operations and be able to identify what these operations are. If you abandon convention when using or extending the STL, abandon all hope as well. If you adhere to convention when using the STL, you'll have an easy life.

The STL conventions do not specify implementation details, but they do specify efficiency constraints on the implementation. In addition, because the STL is a template library, much optimization and tuning can take place at compile time. Many of the naming and information conventions mentioned previously are there precisely to allow significant compile-time optimization. Use of the STL generally rivals the efficiency of hand-coding by an expert, and it beats hand-coding by the average nonexpert or by any team of programmers hands down. The result is also generally clearer and more maintainable.

Learn the STL, and use it extensively.