The Standard Template Library

The Standard Template Library

Table of Contents


Node:Top, Next:, Previous:(dir), Up:(dir)

Standard Template Library

Alexander Stepanov
Silicon Graphics Inc.
2011 N. Shoreline Blvd.
Mt. View, CA 94043

Meng Lee
Hewlett-Packard Laboratories
1501 Page Mill Road
Palo Alto, CA 94304

October 31, 1995


Converted to texinfo format by
LEE Sau Dan
17th March, 2004




Node:COPYING, Next:, Previous:Top, Up:Top

COPYING

Copyright © 1994 Hewlett-Packard Company
Permission to use, copy, modify, distribute and sell this document for any purpose is hereby granted without fee, provided that the above copyright notice appear in all copies and that both that copyright notice and this permission notice appear in supporting documentation.


Copyright © 2004 LEE Sau Dan
Permission to use, copy, modify, distribute and sell this document for any purpose is hereby granted without fee, provided that the above copyright notice appear in all copies and that both that copyright notice and this permission notice appear in supporting documentation.



$Id: STLDocHTML.txt,v 1.1 2006/04/30 19:23:55 AnarManafov Exp www-data $


Node:Introduction, Next:, Previous:COPYING, Up:Top

Introduction

The Standard Template Library provides a set of well structured generic C++ components that work together in a seamless way. Special care has been taken to ensure that all the template algorithms work not only on the data structures in the library, but also on built-in C++ data structures. For example, all the algorithms work on regular pointers. The orthogonal design of the library allows programmers to use library data structures with their own algorithms, and to use library algorithms with their own data structures. The well specified semantic and complexity requirements guarantee that a user component will work with the library, and that it will work efficiently. This flexibility ensures the widespread utility of the library.

Another important consideration is efficiency. C++ is successful because it combines expressive power with efficiency. Much effort has been spent to verify that every template component in the library has a generic implementation that performs within a few percentage points of the efficiency of the corresponding hand-coded routine.

The third consideration in the design has been to develop a library structure that, while being natural and easy to grasp, is based on a firm theoretical foundation.


Node:Structure of the Library, Next:, Previous:Introduction, Up:Top

Structure of the Library

The library contains five main kinds of components:

  • algorithm: defines a computational procedure. See Algorithms.
  • container: manages a set of memory locations. See Containers.
  • iterator: provides a means for an algorithm to traverse through a container. See Iterators.
  • function object: encapsulates a function in an object for use by other components. See Function objects.
  • adaptor: adapts a component to provide a different interface. See Adaptors.

Such decomposition allows us to dramatically reduce the component space. For example, instead of providing a search member function for every kind of container we provide a single version that works with all of them as long as a basic set of requirements is satisfied. The following description helps clarify the structure of the library. If software components are tabulated as a three-dimensional array, where one dimension represents different data types (e.g. int, double), the second dimension represents different containers (e.g. vector, linked-list, file), and the third dimension represents different algorithms on the containers (e.g. searching, sorting, rotation), if i, j, and k are the size of the dimensions, then i \times j \times k different versions of code have to be designed. By using template functions that are parameterized by a data type, we need only j \times k versions. Further, by making our algorithms work on different containers, we need merely j+k versions. This significantly simplifies software design work and also makes it possible to use components in the library together with user defined components in a very flexible way. A user may easily define a specialized container class and use the library's sort function to sort it. A user may provide a different comparison function for the sort either as a regular pointer to a comparison function, or as a function object (an object with an operator() defined) that does the comparisons. If a user needs to iterate through a container in the reverse direction, the reverse_iterator adaptor allows that.

The library extends the basic C++ paradigms in a consistent way, so it is easy for a C/C++ programmer to start using the library. For example, the library contains a merge template function. When a user has two arrays a and b to be merged into c it can be done with:


int a[1000];
int b[2000];
int c[3000];
...
merge(a, a + 1000, b, b + 2000, c);

When a user wants to merge a vector and a list (both of which are template classes in the library) and put the result into a freshly allocated uninitialized storage it can be done with:


vector a;
list b;
...
Employee* c = allocate(a.size() + b.size(), (Employee*)0);
merge(a.begin(), a.end(), b.begin(), b.end(),
      raw_storage_iterator(c));

where begin() and end() are member functions of containers that return the right types of iterators or pointer-like objects that allow the merge to do the job and raw_storage_iterator is an adapter that allows algorithms to put results directly into uninitialized memory by calling the appropriate copy constructor.

In many cases it is useful to iterate through input/output streams in the same way as through regular data structures. For example, if we want to merge two data structures and then store them in a file, it would be nice to avoid creation of an auxiliary data structure for the result, instead storing the result directly into the corresponding file. The library provides both istream_iterator and ostream_iterator template classes to make many of the library algorithms work with I/O streams that represent homogenous aggregates of data. Here is a program that reads a file of integers from the standard input, removes all those that are divisible by its command argument, and writes the result to the standard output:


main(int argc, char** argv) {
    if (argc != 2) throw("usage: remove_if_divides integer\n");
    remove_copy_if(istream_iterator(cin), istream_iterator(),
                   ostream_iterator(cout, "\n"),
                   not1(bind2nd(modulus(), atoi(argv[1]))));
}

All the work is done by remove_copy_if which reads integers one by one until the input iterator becomes equal to the end-of-stream iterator that is constructed by the constructor with no arguments. (In general, all the algorithms work in a "from here to there" fashion taking two iterators that signify the beginning and the end of the input.) Then remove_copy_if writes the integers that pass the test onto the output stream through the output iterator that is bound to cout. As a predicate, remove_copy_if uses a function object constructed from a function object, modulus<int>, which takes i and j and returns i%j, as a binary predicate and makes it into a unary predicate by using bind2nd to bind the second argument to the command line argument, atoi(argv[1]). Then the negation of this unary predicate is obtained using function adaptor not1.

A somewhat more realistic example is a filter program that takes a file and randomly shuffles its lines.


main(int argc, char**) {
    if (argc != 1) throw("usage: shuffle\n");
    vector v;
    copy(istream_iterator(cin), istream_iterator(),
         inserter(v, v.end()));
    random_shuffle(v.begin(), v.end());
    copy(v.begin(), v.end(), ostream_iterator(cout));
}

In this example, copy moves lines from the standard input into a vector, but since the vector is not pre-allocated it uses an insert iterator to insert the lines one by one into the vector. (This technique allows all of the copying functions to work in the usual overwrite mode as well as in the insert mode.) Then random_shuffle shuffles the vector and another call to copy copies it onto the cout stream.


Node:Requirements, Next:, Previous:Structure of the Library, Up:Top

Requirements

To ensure that the different components in a library work together, they must satisfy some basic requirements. Requirements should be as general as possible, so instead of saying "class X has to define a member function operator++()," we say "for any object x of class X, ++x is defined." (It is unspecified whether the operator is a member or a global function.) Requirements are stated in terms of well-defined expressions, which define valid terms of the types that satisfy the requirements. For every set of requirements there is a table that specifies an initial set of the valid expressions and their semantics. Any generic algorithm that uses the requirements has to be written in terms of the valid expressions for its formal type parameters.

If an operation is required to be linear time, it means no worse than linear time, and a constant time operation satisfies the requirement. In some cases we present the semantic requirements using C++ code. Such code is intended as a specification of equivalence of a construct to another construct, not necessarily as the way the construct must be implemented (although in some cases the code given is unambiguously the optimum implementation).


Node:Core components, Next:, Previous:Requirements, Up:Top

Core components

This section contains some basic template functions and classes that are used throughout the rest of the library.


Node:Operators, Next:, Previous:Core components, Up:Core components

Operators

!= (const T1& x, const T2& y) Operator on T1, T2
> (const T1& x, const T2& y) Operator on T1, T2
<= (const T1& x, const T2& y) Operator on T1, T2
>= (const T1& x, const T2& y) Operator on T1, T2

To avoid redundant definitions of operator!= out of operator== and operators>, <=, and >= out of operator< the library provides the following:


template 
inline bool operator!=(const T1& x, const T2& y) {
    return !(x == y);
}

template 
inline bool operator>(const T1& x, const T2& y) {
    return y < x;
}

template 
inline bool operator<=(const T1& x, const T2& y) {
    return !(y < x);
}

template 
inline bool operator>=(const T1& x, const T2& y) {
    return !(x < y);
}


Node:Pair, Previous:Operators, Up:Core components

Pair

pair <T1,T2> Class
The library includes templates for heterogeneous pairs of values.

T1 first Instance Variable of pair
T2 second Instance Variable of pair

pair () Constructor on pair
pair (const T1& x, const T2& y) Constructor on pair
== Operator on pair
< Operator on pair


template 
struct pair {
    T1 first;
    T2 second;
    pair() {}
    pair(const T1& x, const T2& y) : first(x), second(y) {}
};

template 
inline bool operator==(const pair& x, const pair& y) {
    return x.first == y.first && x.second == y.second;
}

template 
inline bool operator<(const pair& x, const pair& y) {
    return x.first < y.first || (!(y.first < x.first) && x.second < y.second);
}

pair<T1, T2> make_pair ( Function
The library provides a matching template function make_pair to simplify their construction. Instead of saying, for example,


return pair(5, 3.1415926); // explicit types
one may say
return make_pair(5, 3.1415926); // types are deduced


template 
inline pair make_pair(const T1& x, const T2& y) {
    return pair(x, y);
}


Node:Iterators, Next:, Previous:Core components, Up:Top

Iterators

Iterators are a generalization of pointers that allow a programmer to work with different data structures(containers) in a uniform manner. To be able to construct template algorithms that work correctly and efficiently on different types of data structures, we need to formalize not just the interfaces but also the semantics and complexity assumptions of iterators. Iterators are objects that have operator* returning a value of some class or built-in type T called a value type of the iterator. For every iterator type X for which equality is defined, there is a corresponding signed integral type called the distance type of the iterator.

Since iterators are a generalization of pointers, their semantics is a generalization of the semantics of pointers in C++. This assures that every template function that takes iterators works with regular pointers. Depending on the operations defined on them, there are five categories of iterators: input iterators See Input iterators, output iterators See Output iterators, forward iterators See Forward iterators, bidirectional iterators See Bidirectional iterators, and random access iterators See Random access iterators. Forward iterators satisfy all the requirements of the input and output iterators and can be used whenever either kind is specified.Bidirectional iterators satisfy all the requirements of the forward iterators and can be used whenever a forward iterator is specified. Random access iterators satisfy all the requirements of bidirectional iterators and can be used whenever a bidirectional iterator is specified. There is an additional attribute that forward, bidirectional and random access iterators might have, that is, they can be mutable or constant depending on whether the result of the operator* behaves as a reference or as a reference to a constant. Constant iterators do not satisfy the requirements for output iterators.


Table 1: Relations among iterator categories
                                                      /---> Input
       Random access --> Bidirectional --> Forward --*
                                                      \---> Output


Just as a regular pointer to an array guarantees that there is a pointer value pointing past the last element of the array, so for any iterator type there is an iterator value that points past the last element of a corresponding container. These values are called past-the-end values. Values of the iterator for which the operator* is defined are called dereferenceable. The library never assumes that past-the-end values are dereferenceable. Iterators might also have singular values that are not associated with any container. For example, after the declaration of an uninitialized pointer x (as with int* x;), x should always be assumed to have a singular value of a pointer. Results of most expressions are undefined for singular values. The only exception is an assignment of a non-singular value to an iterator that holds a singular value. In this case the singular value is overwritten the same way as any other value. Dereferenceable and past-the-end values are always non-singular.

An iterator j is called reachable from an iterator i if and only if there is a finite sequence of applications of operator++ to i that makes i == j. If i and j refer to the same container, then either j is reachable from i, or i is reachable from j, or both (i == j).

Most of the library's algorithmic templates that operate on data structures have interfaces that use ranges. A range is a pair of iterators that designate the beginning and end of the computation. A range [i, i) is an empty range; in general, a range [i, j) refers to the elements in the data structure starting with the one pointed to by i and up to but not including the one pointed to by j. Range [i, j) is valid if and only if j is reachable from i. The result of the application of the algorithms in the library to invalid ranges is undefined.

All the categories of iterators require only those functions that are realizable for a given category in constant time (amortized). Therefore, requirement tables for the iterators do not have a complexity column. In the following sections, we assume: a and b are values of X, n is a value of the distance type Distance, u, tmp, and m are identifiers, r and s are lvalues of X, t is a value of value type T.


Node:Input iterators, Next:, Previous:Iterators, Up:Iterators

Input iterators

X (const X& a) Constructor on input iterators
== Operator on input iterators
!= Operator on input iterators
* Operator on input iterators
++ Operator on input iterators
A class or a built-in type X satisfies the requirements of an input iterator for the value type T if the following expressions are valid:


Table 2: Input iterator requirements

expression return type operational semantics assertion/note pre/post-condition
X(a) X(a) is a copy of a.

note
a destructor is assumed.

X u(a);
X u = a;
post: u is a copy of a.
u = a X& post: u is a copy of a.
a == b convertible to bool if a is a copy of b, then a == b returns true.
== is an equivalence relation over the domain of ==.
a = b convertible to bool !(a == b)
*a convertible to T pre: a is dereferenceable.
if a is a copy of b, then *a is equivalent to *b.
++r X& pre: r is dereferenceable.
post: r is dereferenceable or r is past-the-end.
(void)r++ void (void)++r
*r++ T
{ X tmp = r;
  ++r;
  return tmp; }


NOTE: For input iterators, there are no requirements on the type or value of r++ beyond the requirement that *r++ works appropriately. In particular, r = s does not imply ++r = ++s. (Equality does not guarantee the substitution property or referential transparency.) As for ++r, there are no more requirements on the values of any copies of r except that they can be safely destroyed or assigned to. After executing ++r, copies of (the previous) r are not required to be in the domain of ==. Algorithms on input iterators should never attempt to pass through the same iterator twice. They should be single pass algorithms. Value type T is not required to be an lvalue type. These algorithms can be used with istreams as the source of the input data through the istream_iterator class.


Node:Output iterators, Next:, Previous:Input iterators, Up:Iterators

Output iterators

X (const X& a) Constructor on output iterators
* Operator on output iterators
++ Operator on output iterators
A class or a built-in type X satisfies the requirements of an output iterator if the following expressions are valid:


Table 3: Output iterator requirements

expression return type operational semantics assertion/note pre/post-condition
X(a) *a = t is equivalent to *X(a) = t.
note: a destructor is assumed.
X u(a);
X u = a;
*a = t result is not used
++r X&
r++ X or X&


NOTE: The only valid use of an operator* is on the left side of the assignment statement. Assignment through the same value of the iterator happens only once. Algorithms on output iterators should never attempt to pass through the same iterator twice. They should be single pass algorithms. Equality and inequality are not necessarily defined. Algorithms that take output iterators can be used with ostreams as the destination for placing data through the ostream_iterator class as well as with insert iterators and insert pointers. In particular, the following two conditions should hold: first, any iterator value should be assigned through before it is incremented (this is, for an output iterator i, i++; i++; is not a valid code sequence); second,any value of an output iterator may have at most one active copy at any given time (for example, i = j; *++i = a; *j = b; is not a valid code sequence).


Node:Forward iterators, Next:, Previous:Output iterators, Up:Iterators

Forward iterators

X () Constructor on forward iterators
X (const X& a) Constructor on forward iterators
== Operator on forward iterators
!= Operator on forward iterators
* Operator on forward iterators
++ Operator on forward iterators
A class or a built-in type X satisfies the requirements of a forward iterator if the following expressions are valid:


Table 4: Forward iterator requirements

expression return type operational semantics assertion/note pre/post-condition
X u; note: u might have a singular value.
note: a destructor is assumed.
X() note: X() might be singular.
X(a) a == X(a).
X u(a);
X u = a;
X u; u = a; post: u == a.
a == b convertible to bool == is an equivalence relation.
a = b convertible to bool !(a == b)
r = a X& post: r == a.
*a convertible to T pre: a is dereferenceable. a = b implies *a = *b.
If X is mutable, *a = t is valid.
++r X& pre: r is dereferenceable.
post: r is dereferenceable or r is past-the-end.
r == s and r is dereferenceable implies ++r == ++s.
&r == &++r.
r++ X
{ X tmp = r;
  ++r;
  return tmp; }


NOTE: The fact that r = s implies ++r = ++s (which is not true for input and output iterators) and the removal on the restrictions on the number of the assignments through the iterator (which applies to output iterators) allows the use of multi-pass one-directional algorithms with forward iterators.


Node:Bidirectional iterators, Next:, Previous:Forward iterators, Up:Iterators

Bidirectional iterators

-- Operator on bidirectional iterators
A class or a built-in type X satisfies the requirements of a bidirectional iterator if to the table that specifies forward iterators we add the following lines:


Table 5: Bidirectional iterator requirements (in addition to forward iterator)

expression return type operational semantics assertion/note pre/post-condition
--r X& pre: there exists s such that r == ++s.

post
s is dereferenceable.
--(++r) = r.      
--r = --s
implies r = s.      
&r = &--r
.

r-- X
{ X tmp = r;
  --r;
  return tmp; }


NOTE: Bidirectional iterators allow algorithms to move iterators backward as well as forward.


Node:Random access iterators, Next:, Previous:Bidirectional iterators, Up:Iterators

Random access iterators

+= Operator on random access iterators
+ Operator on random access iterators
-= Operator on random access iterators
- Operator on random access iterators
[n] Operator on random access iterators
< Operator on random access iterators
> Operator on random access iterators
<= Operator on random access iterators
>= Operator on random access iterators
A class or a built-in type X satisfies the requirements of a random access iterator if to the table that specifies bidirectional iterators we add the following lines:


Table 6: Random access iterator requirements (in addition to bidirectional iterator)

expression return type operational semantics assertion/note pre/post-condition
r += n X&
{ Distance m = n;
  if (m >= 0)
    while (m--) ++r;
  else
    while (m++) --r;
  return r; }


a + n
n + a
X
{ X tmp = a;
  return tmp += n; }
a + n == n + a.


r -= n X& return r += -n;


a - n X
{ X tmp = a;
  return tmp -= n; }


b - a Distance pre: there exists a value n of Distance such that a + n = b.
b == a + (b - a).


a[n] convertible to T *(a + n)
a < b convertible to bool b - a > 0 < is a total ordering relation
a > b convertible to bool b < a > is a total ordering relation opposite to <.
a >= b convertible to bool !(a < b)
a <= b convertible to bool !(a > b)



Node:Iterator tags, Next:, Previous:Random access iterators, Up:Iterators

Iterator tags

T* value_type (const T*) Function
ptrdiff_t* distance_type (const T*) Function
To implement algorithms only in terms of iterators, it is often necessary to infer both of the value type and the distance type from the iterator. To enable this task it is required that for an iterator i of any category other than output iterator, the expression value_type(i) returns (T*)(0) and the expression distance_type(i) returns (Distance*)(0). For output iterators, these expressions are not required.


Node:Examples of using iterator tags, Next:, Previous:Iterator tags, Up:Iterator tags

Examples of using iterator tags

For all the regular pointer types we can define value_type and distance_type with the help of:


template 
inline T* value_type(const T*) { return (T*)(0); }

template 
inline ptrdiff_t* distance_type(const T*) { return (ptrdiff_t*)(0); }

Then, if we want to implement a generic reverse function, we do the following:


template 
inline void reverse(BidirectionalIterator first, BidirectionalIterator last) {
    __reverse(first, last, value_type(first), distance_type(first));
}

where __reverse is defined as:


template 
void __reverse(BidirectionalIterator first, BidirectionalIterator last, T*,
               Distance*) {
    Distance n;
    distance(first, last, n); // see Iterator operations section
    --n;
    while (n > 0) {
        T tmp = *first;
        *first++ = *--last;
        *last = tmp;
        n -= 2;
    }
}

If there is an additional pointer type __huge such that the difference of two __huge pointers is of the type long long, we define:


template 
inline T* value_type(const T __huge *) { return (T*)(0); }

template 
inline long long* distance_type(const T __huge *) { return (long long*)(0); }

input_iterator_tag Tag
output_iterator_tag Tag
forward_iterator_tag Tag
bidirectional_iterator_tag Tag
random_access_iterator_tag Tag

It is often desirable for a template function to find out what is the most specific category of its iterator argument, so that the function can select the most efficient algorithm at compile time. To facilitate this, the library introduces category tag classes which are used as compile time tags for algorithm selection. They are: input_iterator_tag, output_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag and random_access_iterator_tag.

iterator_category (const iterator_type&) Function
Every iterator i must have an expression iterator_category(i) defined on it that returns the most specific category tag that describes its behavior. For example, we define that all the pointer types are in the random access iterator category by:


template 
inline random_access_iterator_tag iterator_category(const T*) {
    return random_access_iterator_tag();
}

For a user-defined iterator BinaryTreeIterator, it can be included into the bidirectional iterator category by saying:


template 
inline bidirectional_iterator_tag iterator_category(
        const BinaryTreeIterator&) {
    return bidirectional_iterator_tag();
}

If a template function evolve is well defined for bidirectional iterators, but can be implemented more efficiently for random access iterators, then the implementation is like:


template 
inline void evolve(BidirectionalIterator first, BidirectionalIterator last) {
    evolve(first, last, iterator_category(first));
}

template 
void evolve(BidirectionalIterator first, BidirectionalIterator last,
            bidirectional_iterator_tag) {
    // ... more generic, but less efficient algorithm
}

template 
void evolve(RandomAccessIterator first, RandomAccessIterator last,
            random_access_iterator_tag) {
    // ... more efficient, but less generic algorithm
}


Node:Library defined primitives, Previous:Examples of using iterator tags, Up:Iterator tags

Library defined primitives

input_iterator <T, Distance> Iterator
output_iterator Iterator
forward_iterator <T, Distance> Iterator
bidirectional_iterator <T, Distance> Iterator
random_access_iterator <T, Distance> Iterator

To simplify the task of defining the iterator_category, value_type and distance_type for user definable iterators, the library provides the following predefined classes and functions:


// iterator tags
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag {};
struct bidirectional_iterator_tag {};
struct random_access_iterator_tag {};

// iterator bases
template  struct input_iterator {};
struct output_iterator {};
// output_iterator is not a template because output iterators
// do not have either value type or distance type defined.
template  struct forward_iterator {};
template  struct bidirectional_iterator {};
template  struct random_access_iterator {};

// iterator_category
template 
inline input_iterator_tag
iterator_category(const input_iterator&) {
    return input_iterator_tag();
}

inline output_iterator_tag iterator_category(const output_iterator&) {
    return output_iterator_tag();
}

template 
inline forward_iterator_tag
iterator_category(const forward_iterator&) {
    return forward_iterator_tag();
}

template 
inline bidirectional_iterator_tag
iterator_category(const bidirectional_iterator&) {
    return bidirectional_iterator_tag();
}

template 
inline random_access_iterator_tag
iterator_category(const random_access_iterator&) {
    return random_access_iterator_tag();
}

template 
inline random_access_iterator_tag iterator_category(const T*) {
    return random_access_iterator_tag();}
}

// value_type of iterator
template 
inline T* value_type(const input_iterator&) {
    return (T*)(0);
}

template 
inline T* value_type(const forward_iterator&) {
    return (T*)(0);
}

template 
inline T* value_type(const bidirectional_iterator&) {
    return (T*)(0);
}

template 
inline T* value_type(const random_access_iterator&) {
    return (T*)(0);
}

template  inline T* value_type(const T*) { return (T*)(0); }

// distance_type of iterator
template 
inline Distance* distance_type(const input_iterator&) {
    return (Distance*)(0);
}

template 
inline Distance* distance_type(const forward_iterator&) {
    return (Distance*)(0);
}

template 
inline Distance* distance_type(const bidirectional_iterator&) {
    return (Distance*)(0);
}

template 
inline Distance* distance_type(const random_access_iterator&) {
    return (Distance*)(0);
}

template 
inline ptrdiff_t* distance_type(const T*) { return (ptrdiff_t*)(0); }

If a user wants to define a bidirectional iterator for some data structure containing double and such that it works on a large memory model of a computer, it can be done by defining:


class MyIterator : public bidirectional_iterator {
    // code implementing ++, etc.
};

Then there is no need to define iterator_category, value_type, and distance_type on MyIterator.


Node:Iterator operations, Previous:Iterator tags, Up:Iterators

Iterator operations

advance (InputIterator& i, Distance n) Function
distance (InputIterator first, InputIterator last, Distance& n) Function

Since only random access iterators provide + and - operators, the library provides two template functions advance and distance. These functions use + and - for random access iterators (and are, therefore,constant time for them); for input, forward and bidirectional iterators they use ++ to provide linear time implementations. advance takes a negative argument n for random access and bidirectional iterators only. advance increments (or decrements for negative n) iterator reference i by n. distance increments n by the number of times it takes to get from first to last.


template 
inline void advance(InputIterator& i, Distance n);

template 
inline void distance(InputIterator first, InputIterator last, Distance& n);

distance must be a three argument function storing the result into a reference instead of returning the result because the distance type cannot be deduced from built-in iterator types such as int*.


Node:Function objects, Next:, Previous:Iterators, Up:Top

Function objects

operator() () Function
Function objects are objects with an operator() defined. They are important for the effective use of the library. In the places where one would expect to pass a pointer to a function to an algorithmic template, the interface is specified to accept an object with an operator() defined. This not only makes algorithmic templates work with pointers to functions, but also enables them to work with arbitrary function objects. Using function objects together with function templates increases the expressive power of the library as well as making the resulting code much more efficient. For example, if we want to have a by-element addition of two vectors a and b containing double and put the result into a we can do:


transform(a.begin(), a.end(), b.begin(), a.begin(), plus());

If we want to negate every element of a we can do:


transform(a.begin(), a.end(), a.begin(), negate());

argument_type Typedef on unary_function
result_type Typedef on unary_function
first_argument_type Typedef on binary_function
second_argument_type Typedef on binary_function
result_type Typedef on binary_function
The corresponding functions will inline the addition and the negation. To enable adaptors and other components to manipulate function objects that take one or two arguments it is required that they correspondingly provide typedefs argument_type and result_type for function objects that take one argument and first_argument_type, second_argument_type, and result_type for function objects that take two arguments.


Node:Base, Next:, Previous:Function objects, Up:Function objects

Base

unary_function Function Object
binary_function Function Object
The following classes are provided to simplify the typedefs of the argument and result types:


template 
struct unary_function {
    typedef Arg argument_type;
    typedef Result result_type;
};

template 
struct binary_function {
    typedef Arg1 first_argument_type;
    typedef Arg2 second_argument_type;
    typedef Result result_type;
};


Node:Arithmetic operations, Next:, Previous:Base, Up:Function objects

Arithmetic operations

plus Function Object
minus Function Object
times Function Object
divides Function Object
modulus Function Object
negate Function Object

The library provides basic function object classes for all of the arithmetic operators in the language.


template 
struct plus : binary_function {
    T operator()(const T& x, const T& y) const { return x + y; }
};

template 
struct minus : binary_function {
    T operator()(const T& x, const T& y) const { return x - y; }
};

template 
struct times : binary_function {
    T operator()(const T& x, const T& y) const { return x * y; }
};

template 
struct divides : binary_function {
    T operator()(const T& x, const T& y) const { return x / y; }
};

template 
struct modulus : binary_function {
    T operator()(const T& x, const T& y) const { return x % y; }
};

template 
struct negate : unary_function {
    T operator()(const T& x) const { return -x; }
};


Node:Comparisons, Next:, Previous:Arithmetic operations, Up:Function objects

Comparisons

equal_to Binary Predicate
not_equal_to Binary Predicate
greater Binary Predicate
less Binary Predicate
greater_equal Binary Predicate
less_equal Binary Predicate

The library provides basic function object classes for all of the comparison operators in the language.


template 
struct equal_to : binary_function {
    bool operator()(const T& x, const T& y) const { return x == y; }
};

template 
struct not_equal_to : binary_function {
    bool operator()(const T& x, const T& y) const { return x != y; }
};

template 
struct greater : binary_function {
    bool operator()(const T& x, const T& y) const { return x > y; }
};

template 
struct less : binary_function {
    bool operator()(const T& x, const T& y) const { return x < y; }
};

template 
struct greater_equal : binary_function {
    bool operator()(const T& x, const T& y) const { return x >= y; }
};

template 
struct less_equal : binary_function {
    bool operator()(const T& x, const T& y) const { return x <= y; }
};


Node:Logical operations, Previous:Comparisons, Up:Function objects

Logical operations

logical_and Binary Predicate
logical_or Binary Predicate
logical_not Binary Predicate


template 
struct logical_and : binary_function {
    bool operator()(const T& x, const T& y) const { return x && y; }
};

template 
struct logical_or : binary_function {
    bool operator()(const T& x, const T& y) const { return x || y; }
};

template 
struct logical_not : unary_function {
    bool operator()(const T& x) const { return !x; }
};


Node:Allocators, Next:, Previous:Function objects, Up:Top

Allocators

One of the common problems in portability is to be able to encapsulate the information about the memory model. This information includes the knowledge of pointer types, the type of their difference, the type of the size of objects in this memory model, as well as the memory allocation and deallocation primitives for it.

STL addresses this problem by providing a standard set of requirements for allocators, which are objects that encapsulate this information. All of the containers in STL are parameterized in terms of allocators. That dramatically simplifies the task of dealing with multiple memory models.


Node:Allocator requirements, Next:, Previous:Allocators, Up:Allocators

Allocator requirements

value_type Typedef on allocators
reference Typedef on allocators
const_reference Typedef on allocators
pointer Typedef on allocators
const_pointer Typedef on allocators
size_type Typedef on allocators
difference_type Typedef on allocators
In the following table, we assume X is an allocator class for objects of type T, a is a value of X, n is of type X::size_type, p is of type X::pointer, r is of type X::reference and s is of type X::const_reference.

X () Constructor on allocators

pointer address (reference r) Method on allocators
const_pointer const_address (const_reference s) Method on allocators
pointer allocate (size_type n) Method on allocators
deallocate (pointer p) Method on allocators
void construct (pointer p, value_type a) Method on allocators
void destroy (pointer p) Method on allocators
size_type init_page_size () Method on allocators
size_type max_size () Method on allocators

All the operations on the allocators are expected to be amortized constant time.


Table 7: Allocator requirements

expression return type assertion/note pre/post-condition
X::value_type T
X::reference lvalue of T
X::const_reference const lvalue of T
X::pointer pointer to T type the result of operator* of values of X::pointer is of reference.
X::const_pointer pointer to const T type the result of operator* of values of X::const_pointer is of const_reference; it is the same type of pointer as X::pointer, in particular, sizeof(X::const_pointer) == sizeof(X::pointer).
X::size_type unsigned integral type the type that can represent the size of the largest object in the memory model.
X::difference_type signed integral type the type that can represent the difference between any two pointers in the memory model.
X a; note: a destructor is assumed.
a.address(r) pointer *(a.address(r)) == r.
a.const_address(s) const_pointer *(a.address(s)) == s.
a.allocate(n) X::pointer memory is allocated for n objects of type T but objects are not constructed. allocate may raise an appropriate exception.
a.deallocate(p) result is not used all the objects in the area pointed by p should be destroyed prior to the call of the deallocate.
construct(p, a) void post: *p == a.
destroy(p) void the value pointed by p is destroyed.
a.init_page_size() X::size_type the returned value is the optimal value for an initial buffer size of the given type. It is assumed that if k is returned by init_page_size, t is the construction time for T, and u is the time that it takes to do allocate(k), then k \times t is much greater than u.
a.max_size() X::size_type the largest positive value of X::difference_type


pointer belongs to the category of mutable random access iterators referring to T. const_pointer belongs to the category of constant random access iterators referring to T. There is a conversion defined from pointer to const_pointer.

For any allocator template Alloc there is a specialization for type void. Alloc<void> has only constructor, destructor, and Alloc<void>::pointer defined. Conversions are defined from any instance of Alloc<T>::pointer into Alloc<void>::pointer and back so that for any p, p == Alloc<T>::pointer(Alloc<void>::pointer(p)).


Node:The default allocator, Previous:Allocator requirements, Up:Allocators

The default allocator

allocator Allocator
allocator Allocator


template 
class allocator {
public:
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef const T& const_reference;
    typedef T value_type;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    allocator();
    ~allocator();
    pointer address(reference x);
    const_pointer const_address(const_reference x);
    pointer allocate(size_type n);
    void deallocate(pointer p);
    size_type init_page_size();
    size_type max_size();
};

class allocator {
public:
    typedef void* pointer;
    allocator();
    ~allocator();
};

In addition to allocator the library vendors are expected to provide allocators for all supported memory models.


Node:Containers, Next:, Previous:Allocators, Up:Top

Containers

value_type Typedef on containers
reference Typedef on containers
const_reference Typedef on containers
pointer Typedef on containers
iterator Typedef on containers
const_iterator Typedef on containers
difference_type Typedef on containers
size_type Typedef on containers
Containers are objects that store other objects. They control allocation and deallocation of these objects through constructors, destructors, insert and erase operations.

X () Constructor on containers
X (const X& a) Constructor on containers
~X () Destructor on containers
== Operator on containers
!= Operator on containers
< Operator on containers
> Operator on containers
<= Operator on containers
>= Operator on containers

size_type max_size () Method on containers
bool empty () Method on containers
void swap () Method on containers

In the following table, we assume X is a container class containing objects of type T, a and b are values of X, u is an identifier and r is a value of X&.


Table 8: Container requirements

expression return type operational semantics assertion/note pre/post-condition complexity
X::value_type T compile time
X::reference compile time
X::const_reference compile time
X::pointer a pointer type pointing to X::reference pointer to T in the memory model used by the container compile time
X::iterator iterator type pointing to X::reference an iterator of any iterator category except output iterator. compile time
X::const_iterator iterator type pointing to X::const_reference a constant iterator of any iterator category except output iterator. compile time
X::difference_type signed integral type is identical to the distance type of X::iterator and X::const_iterator compile time
X::size_type unsigned integral type size_type can represent any non-negative value of difference_type compile time
X u; post: u.size() == 0. constant
X() X().size() == 0. constant
X(a) a == X(a). linear
X u(a);
X u = a;
X u; u = a; post: u == a. linear
(&a)->~X() result is not used post: a.size() == 0.
note: the destructor is applied to every element of a and all the memory is returned.
linear
a.begin() iterator; const_iterator for constant a constant
a.end() iterator; const_iterator for constant a constant
a == b convertible to bool a.size() == b.size() && equal(a.begin(), a.end(), b.begin()) == is an equivalence relation. See Equal. linear
a = b convertible to bool !(a == b) linear
r = a X&
 if (&r != &a) {
  (&r)->X::~X();
  new (&r) X(a);
  return r; }
post: r == a. linear
a.size() size_type size_type n = 0; distance(a.begin(), a.end(), n); return n; constant
a.max_size() size_type size() of the largest possible container. constant
a.empty() convertible to bool a.size() == 0 constant
a < b convertible to bool lexicographical_compare(a.begin(), a.end(), b.begin(), b.end()) pre: < is defined for values of T. < is a total ordering relation. See Lexicographical comparison. linear
a > b convertible to bool b < a linear
a <= b convertible to bool !(a > b) linear
a >= b convertible to bool !(a < b) linear
a.swap(b) void swap(a,b) constant

size () Method on containers
The member function size() returns the number of elements in the container. Its semantics is defined by the rules of constructors, inserts, and erases.

begin () Method on containers
end () Method on containers
begin() returns an iterator referring to the first element in the container. end() returns an iterator which is the past-the-end value.

reverse_iterator Typedef on reversible containers
const_reverse_iterator Typedef on reversible containers

( const_)reverse_iterator rbegin () Method on reversible containers
( const_)reverse_iterator rend () Method on reversible containers
If the iterator type of a container belongs to the bidirectional or random access iterator categories, the container is called reversible and satisfies the following additional requirements:


Table 9: Reversible container requirements (in addition to container)

expression return type operational semantics complexity
X::reverse_iterator reverse_iterator<iterator, value_type, reference, difference_type> for random access iterator reverse_bidirectional_iterator<iterator, value_type, reference, difference_type> for bidirectional iterator compile time
X::const_reverse_iterator reverse_iterator<const_iterator, value_type, const_reference, difference_type> for random access iterator

reverse_bidirectional_iterator< const_iterator, value_type, const_reference, difference_type> for bidirectional iterator

compile time
a.rbegin() reverse_iterator; const_reverse_iterator for constant a reverse_iterator(end()) constant
a.rend() reverse_iterator; const_reverse_iterator for constant a reverse_iterator(begin()) constant


Node:Sequences, Next:, Previous:Containers, Up:Containers

Sequences

X (size_type n, const T& t) Constructor on sequences
X (InputIterator& i, InputIterator& t) Constructor on sequences
A sequence is a kind of container (See Containers.) that organizes a finite set of objects, all of the same type, into a strictly linear arrangement. The library provides three basic kinds of sequence containers: vector, list, and deque. It also provides container adaptors that make it easy to construct abstract data types, such as stacks or queues, out of the basic sequence kinds (or out of other kinds of sequences that the user might define).

iterator insert (iterator& p, const T& t) Method on sequences
insert (iterator& p, size_type n, const T& t) Method on sequences
insert (iterator& p, const_iterator& i, const_iterator& j) Method on sequences
erase (iterator& q) Method on sequences
erase (iterator& q1, iterator& q2) Method on sequences

In the following two tables, X is a sequence class, a is value of X, i and j satisfy input iterator requirements, [i, j) is a valid range, n is a value of X::size_type, p is a valid iterator to a, q is a dereferenceable iterator to a, [q1, q2) is a valid range in a, t is a value of X::value_type.

The complexities of the expressions are sequence dependent.


Table 10: Sequence requirements (in addition to container)

expression return type assertion/note pre/post-condition
X(n, t)
X a(n, t);
post: size() == n.
constructs a sequence with n copies of t.
X(i, j)
X a(i, j);
post: size() == distance between i and j.
constructs a sequence equal to the range [i, j).
a.insert(p, t) iterator inserts a copy of t before p.
the return value points to the inserted copy.
a.insert(p, n, t) result is not used inserts n copies of t before p.
a.insert(p, i, j) result is not used inserts copies of elements in [i, j) before p.
a.erase(q) result is not used erases the element pointed to by q.
a.erase(q1, q2) result is not used erases the elements in the range [q1, q2).


vector, list, and deque offer the programmer different complexity trade-offs and should be used accordingly. vector is the type of sequence that should be used by default. list should be used when there are frequent insertions and deletions from the middle of the sequence. deque is the data structure of choice when most insertions and deletions take place at the beginning or at the end of the sequence.

iterator and const_iterator types for sequences have to be at least of the forward iterator category.

( const_)reference front () Method on sequences
( const_)reference back () Method on sequences
void push_front (const T& t) Method on sequences
void push_back (const T& t) Method on sequences
void pop_front () Method on sequences
void pop_back () Method on sequences

[n] Operator on sequences


Table 11: Optional sequence operations

expression return type operational semantics container
a.front() reference; const_reference for constant a *a.begin() vector, list, deque
a.back() reference; const_reference for constant a *a.(--end()) vector, list, deque
a.push_front(t) void a.insert(a.begin(), t) list, deque
a.push_back(t) void a.insert(a.end(), t) vector, list, deque
a.pop_front() void a.erase(a.begin()) list, deque
a.pop_back() void a.erase(--a.end()) vector, list, deque
a[n] reference; const_reference for constant a *(a.begin() + n) vector, deque


All the operations in the above table are provided only for the containers for which they take constant time.


Node:Vector, Next:, Previous:Sequences, Up:Sequences

Vector

vector <T, Allocator> Sequence
vector is a kind of sequence (See Sequences.) that supports random access iterators. In addition, it supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time. Storage management is handled automatically, though hints can be given to improve efficiency. See Reversible Container.


template  class Allocator = allocator>
class vector {
public:

// typedefs:
    typedef iterator;
    typedef const_iterator;
    typedef Allocator::pointer pointer;
    typedef Allocator::reference reference;
    typedef Allocator::const_reference const_reference;
    typedef size_type;
    typedef difference_type;
    typedef T value_type;
    typedef reverse_iterator;
    typedef const_reverse_iterator;

// allocation/deallocation:
    vector();
    vector(size_type n, const T& value = T());
    vector(const vector& x);
    template 
    vector(InputIterator first, InputIterator last);
    ~vector();
    vector& operator=(const vector& x);
    void reserve(size_type n);
    void swap(vector& x);

// accessors:
    iterator begin();
    const_iterator begin() const;
    iterator end();
    const_iterator end() const;
    reverse_iterator rbegin();
    const_reverse_iterator rbegin();
    reverse_iterator rend();
    const_reverse_iterator rend();
    size_type size() const;
    size_type max_size() const;
    size_type capacity() const;
    bool empty() const;
    reference operator[](size_type n);
    const_reference operator[](size_type n) const;
    reference front();
    const_reference front() const;
    reference back();
    const_reference back() const;

// insert/erase:
    void push_back(const T& x);
    iterator insert(iterator position, const T& x = T());
    void insert(iterator position, size_type n, const T& x);
    template 
    void insert(iterator position, InputIterator first, InputIterator last);
    void pop_back();
    void erase(iterator position);
    void erase(iterator first, iterator last);
};

template 
bool operator==(const vector& x, const vector& y);
template 
bool operator<(const vector& x, const vector& y);

iterator Typedef on vector
iterator is a random access iterator referring to T. The exact type is implementation dependent and determined by Allocator.

const_iterator Typedef on vector
const_iterator is a constant random access iterator referring to const T. The exact type is implementation dependent and determined by Allocator. It is guaranteed that there is a constructor for const_iterator out of iterator.

size_type Typedef on vector
size_type is an unsigned integral type. The exact type is implementation dependent and determined by Allocator.

difference_type Typedef on vector
difference_type is a signed integral type. The exact type is implementation dependent and determined by Allocator.

vector (InputIterator first, InputIterator last) Constructor on vector
The constructor template <class InputIterator> vector(InputIterator first, InputIterator last) makes only N calls to the copy constructor of T (where N is the distance between first and last) and no reallocations if iterators first and last are of forward, bidirectional, or random access categories. It does at most 2N calls to the copy constructor of T and \log N reallocations if they are just input iterators, since it is impossible to determine the distance between first and last and then do copying.

capacity () Method on vector
reserve () Method on vector
The member function capacity returns the size of the allocated storage in the vector. The member function reserve is a directive that informs vector of a planned change in size, so that it can manage the storage allocation accordingly. It does not change the size of the sequence and takes at most linear time in the size of the sequence. Reallocation happens at this point if and only if the current capacity is less than the argument of reserve. After reserve, capacity is greater or equal to the argument of reserve if reallocation happens; and equal to the previous value of capacity otherwise. Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. It is guaranteed that no reallocation takes place during the insertions that happen after reserve takes place till the time when the size of the vector reaches the size specified by reserve.

insert (iterator position, const T& x = T()); Method on vector
insert (iterator position, size_type n, const T& x); Method on vector
insert (iterator position, InputIterator first, InputIterator last); Method on vector
insert causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid. Inserting a single element into a vector is linear in the distance from the insertion point to the end of the vector. The amortized complexity over the lifetime of a vector of inserting a single element at its end is constant. Insertion of multiple elements into a vector with a single call of the insert member function is linear in the sum of the number of elements plus the distance to the end of the vector. In other words, it is much faster to insert many elements into the middle of a vector at once than to do the insertion one at a time. The insert template member function preallocates enough storage for the insertion if the iterators first and last are of forward, bidirectional or random access category. Otherwise, it does insert elements one by one and should not be used for inserting into the middle of vectors.

erase (iterator position); Method on vector
erase (iterator first, iterator last); Method on vector
erase invalidates all the iterators and references after the point of the erase. The destructor of T is called the number of times equal to the number of the elements erased, but the assignment operator of T is called the number of times equal to the number of elements in the vector after the erased elements.

vector <bool, allocator> Sequence
To optimize space allocation, a specialization for bool is provided:


class vector {
public:

// bit reference:
    class reference {
    public:
        ~reference();
        operator bool() const;
        reference& operator=(const bool x);
        void flip(); // flips the bit
    };

// typedefs:
    typedef bool const_reference;
    typedef iterator;
    typedef const_iterator;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    typedef bool value_type;
    typedef reverse_iterator;
    typedef const_reverse_iterator;

// allocation/deallocation:
    vector();
    vector(size_type n, const bool& value = bool());
    vector(const vector& x);
    template 
    vector(InputIterator first, InputIterator last);
    ~vector();
    vector& operator=(const vector& x);
    void reserve(size_type n);
    void swap(vector& x);

// accessors:
    iterator begin();
    const_iterator begin() const;
    iterator end();
    const_iterator end() const;
    reverse_iterator rbegin();
    const_reverse_iterator rbegin();
    reverse_iterator rend();
    const_reverse_iterator rend();
    size_type size() const;
    size_type max_size() const;
    size_type capacity() const;
    bool empty() const;
    reference operator[](size_type n);
    const_reference operator[](size_type n) const;
    reference front();
    const_reference front() const;
    reference back();
    const_reference back() const;

// insert/erase:
    void push_back(const bool& x);
    iterator insert(iterator position, const bool& x = bool());
    void insert (iterator position, size_type n, const bool& x);
    template 
    void insert (iterator position, InputIterator first, InputIterator last);
    void pop_back();
    void erase(iterator position);
    void erase(iterator first, iterator last);
};

void swap(vector::reference x,
          vector::reference y);

bool operator==(const vector& x,
                const vector& y);

bool operator<(const vector& x,
               const vector& y);

reference Typedef on vector<bool>
reference is a class that simulates the behavior of references of a single bit in vector<bool>.

Every implementation is expected to provide specializations of vector<bool> for all supported memory models.

At present, it is not possible to templatize a specialization. That is, we cannot write:

            template