Standard Template Library Programmer's Guide

Input Iteratoris, in fact, a rather weak concept: that is, it imposes very few requirements. An Input Iteratormust support a subset of pointer arithmetic (it must be possible to increment an Input Iteratorusing prefix and postfix operator++ ), but need not support all operations of pointer arithmetic. This is sufficient for find , but some other algorithms require that their arguments satisfy additional requirements. Reverse , for example, must be able to decrement its arguments as well as increment them; it uses the expression --last . In terms of concepts, we say that reverse 's arguments must be models of Bidirectional Iteratorrather than Input Iterator.

The Bidirectional Iteratorconcept is very similar to the Input Iteratorconcept: it simply imposes some additional requirements. The types that are models of Bidirectional Iteratorare a subset of the types that are models of Input Iterator: every type that is a model of Bidirectional Iteratoris also a model of Input Iterator. Int* , for example, is both a model of Bidirectional Iteratorand a model of Input Iterator, but istream_iterator , is only a model of Input Iterator: it does not conform to the more stringent Bidirectional Iteratorrequirements.

We describe the relationship between Input Iteratorand Bidirectional Iteratorby saying that Bidirectional Iteratoris a refinement of Input Iterator. Refinement of concepts is very much like inheritance of C++ classes; the main reason we use a different word, instead of just calling it "inheritance", is to emphasize that refinement applies to concepts rather than to actual types.

There are actually three more iterator concepts in addition to the two that we have already discussed: the five iterator concepts are Output Iterator, Input Iterator, Forward Iterator, Bidirectional Iterator, and Random Access Iterator; Forward Iteratoris a refinement of Input Iterator, Bidirectional Iteratoris a refinement of Forward Iterator, and Random Access Iteratoris a refinement of Bidirectional Iterator. ( Output Iteratoris related to the other four concepts, but it is not part of the hierarchy of refinement: it is not a refinement of any of the other iterator concepts, and none of the other iterator concepts are refinements of it.) The Iterator Overview has more information about iterators in general.

Container classes, like iterators, are organized into a hierarchy of concepts. All containers are models of the concept Container; more refined concepts, such as Sequenceand Associative Container, describe specific types of containers.

If you understand algorithms, iterators, and containers, then you understand almost everything there is to know about the STL. The STL does, however, include several other types of components.

First, the STL includes several utilities : very basic concepts and functions that are used in many different parts of the library. The concept Assignable, for example, describes types that have assignment operators and copy constructors; almost all STL classes are models of Assignable, and almost all stl algorithms require their arguments to be models of Assignable.

Second, the STL includes some low-level mechanisms for allocating and deallocating memory. Allocators are very specialized, and you can safely ignore them for almost all purposes.

Finally, the STL includes a large collection of function objects , also known as functors . Just as iterators are a generalization of pointers, function objects are a generalization of functions: a function object is anything that you can call using the ordinary function call syntax. There are several different concepts relating to function objects, including Unary Function(a function object that takes a single argument, i.e. one that is called as f(x) ) and Binary Function(a function object that takes two arguments, i.e. one that is called as f(x, y) ). Function objects are an important part of generic programming because they allow abstraction not only over the types of objects, but also over the operations that are being performed.

This site documents all of the components (classes, functions, and concepts) in the SGI Standard Template Library. Each page describes a single component, and also includes links to related components.

This documentation assumes a general familiarity with C++, especially with C++ templates. Additionally, you should read Introduction to the Standard Template Library before proceeding to the pages that describe individual components: the introductory page defines several terms that are used throughout the documentation.

The STL components are divided into six broad categories on the basis of functionality: Containers , Iterators , Algorithms , Function Objects , Utilities , and Allocators ; these categories are defined in the Introduction, and the Table of Contents is organized according to them.

The STL documentation contains two indices. One of them, the Main Index, lists all components in alphabetical order. The other, the Divided Index, contains a separate alphabetical listing for each category. The Divided Index includes one category that is not present in the Table of Contents: Adaptors . An adaptor is a class or a function that transforms one interface into a different one. The reason that adaptors don't appear in the Table of Contents is that no component is merely an adaptor, but always an adaptor and something else; stack , for example, is a container and an adaptor. Accordingly, stack appears in two different places in the Divided Index. There are several other components that appear in the Divided Index in more than one place.

The STL documentation classifies components in two ways.

1. Categories are a classification by functionality. The categories are:

• Container

• Iterator

• Algorithm

• Function Object

• Utility

• Adaptor

• Allocator.

2. Component types are a structural classification: one based on what kind of C++ entity (if any) a component is. The component types are:

• Type ( i.e. a struct or class )

• Function

• Concept (as defined in the Introduction).

These two classification schemes are independent, and each of them applies to every STL component; vector , for example, is a type whose category is Containers , and Forward Iteratoris a concept whose category is Iterators .

Both of these classification schemes appear at the top of every page that documents an STL component. The upper left corner identifies the the component's category as Containers , Iterators , Algorithms , Function Objects , Utilities , Adaptors , or Allocators , and the upper right corner identifies the component as a type , a function , or a concept .