Standard Template Library Programmer's Guide

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.

Classification of STL components

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 Iterator is 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.

Using the STL documentation

The STL is a generic library: almost every class and function is a template. Accordingly, one of the most important purposes of the STL documentation is to provide a clear description of which types may be used to instantiate those templates. As described in the Introduction, a concept is a generic set of requirements that a type must satisfy: a type is said to be a model of a concept if it satisfies all of that concept's requirements.

Concepts are used very heavily in the STL documentation, both because they directly express type requirements, and because they are a tool for organizing types conceptually. (For example, the fact that ostream_iterator and insert_iterator are both models of Output Iterator is an important statement about what those two classes have in common.) Concepts are used for the documentation of both types and functions.

The format of a concept page

A page that documents a concept has the following sections.

• Summary: a description of the concept's purpose.

• Refinement of: a list of other concepts that this concept refines , with links to those concepts.

• Associated types: a concept is a set of requirements on some type. Frequently, however, some of those requirements involve some other type. For example, one of the Unary Function requirements is that a Unary Function must have an argument type ; if F is a type that models Unary Function and f is an object of type F, then, in the expression f (x), x must be of F 's argument type. If a concept does have any such associated types, then they are defined in this section.

• Notation: the next three sections, definitions, valid expressions, and expression semantics, present expressions involving types that model the concept being defined. This section defines the meaning of the variables and identifiers used in those expressions.

• Definitions: some concepts, such as LessThan Comparable, use specialized terminology. If a concept requires any such terminology, it is defined in this section.

• Valid Expressions: a type that models a concept is required to support certain operations. In most cases, it doesn't make sense to describe this in terms of specific functions or member functions: it doesn't make any difference, for example, whether a type that models Input Iterator uses a global function or a member function to provide operator++. This section lists the expressions that a type modeling this concept must support. It includes any special requirements (if any) on the types of the expression's operands, and the expression's return type (if any).

• Expression Semantics: the previous section, valid expressions, lists which expressions involving a type must be supported; it doesn't, however, define the meaning of those expressions. This section does: it lists the semantics, preconditions, and postconditions for the expressions defined in the previous section.

• Complexity Guarantees: in some cases, the run-time complexity of certain operations is an important part of a concept's requirements. For example, one of the most significant distinctions between a Bidirectional Iterator and a Random Access Iterator is that, for random access iterators, expressions like p + n take constant time. Any such requirements on run-time complexity are listed in this section.

• Invariants: many concepts require that some property is always true for objects of a type that models the concept being defined. For example, LessThan Comparable imposes the