Standard Template Library Programmer's Guide

[2] Note that p equal to a.begin() means to insert something at the beginning of a (that is, before any elements already in a ), and p equal to a.end() means to append something to the end of a .

[3] Warning: there is no guarantee that a valid iterator on a is still valid after an insertion or an erasure. In some cases iterators do remain valid, and in other cases they do not. The details are different for each sequence class.

[4] a.insert(p, n, t) is guaranteed to be no slower then calling a.insert(p, t)n times. In some cases it is significantly faster.

[5] Vector is usually preferable to deque and list. Deque is useful in the case of frequent insertions at both the beginning and end of the sequence, and list and slist are useful in the case of frequent insertions in the middle of the sequence. In almost all other situations, vector is more efficient.

Container, Forward Container, Associative Container, Front Insertion Sequence, Back Insertion Sequence, vector , deque , list , slist

Category: containers

Component type: concept

A Front Insertion Sequence is a Sequence where it is possible to insert an element at the beginning, or to access the first element, in amortized constant time. Front Insertion Sequences have special member functions as a shorthand for those operations.

Sequence

None, except for those of Sequence.

XA type that is a model of Front Insertion Sequence

aObject of type X

TThe value type of X

tObject of type T

In addition to the expressions defined in Sequence, the following expressions must be valid.

Front, push front, and pop front are amortized constant time. [2]

• list

• deque

[1] Front is actually defined in Sequence, since it is always possible to implement it in amortized constant time. Its definition is repeated here, along with push front and pop front, in the interest of clarity.

[2] This complexity guarantee is the only reason that front() , push_front() , and pop_front() are defined: they provide no additional functionality. Not every sequence must define these operations, but it is guaranteed that they are efficient if they exist at all.

Container, Sequence, Back Insertion Sequence, deque , list , slist

Category: containers

Component type: concept

A Back Insertion Sequence is a Sequence where it is possible to append an element to the end, or to access the last element, in amortized constant time. Back Insertion Sequences have special member functions as a shorthand for those operations.

Sequence

None, except for those of Sequence.

XA type that is a model of Back Insertion Sequence

aObject of type X

TThe value type of X

tObject of type T

In addition to the expressions defined in Sequence, the following expressions must be valid.

Back, push back, and pop back are amortized constant time. [1]

vector

list

deque

[1] This complexity guarantee is the only reason that back() , push_back() , and pop_back() are defined: they provide no additional functionality. Not every sequence must define these operations, but it is guaranteed that they are efficient if they exist at all.

Container, Sequence, Front Insertion Sequence, vector , deque , list

Category: containers

Component type: concept

An Associative Container is a variable-sized Container that supports efficient retrieval of elements (values) based on keys. It supports insertion and removal of elements, but differs from a Sequence in that it does not provide a mechanism for inserting an element at a specific position. [1]

As with all containers, the elements in an Associative Container are of type value_type . Additionally, each element in an Associative Container has a key , of type key_type . In some Associative Containers, Simple Associative Containers, the value_type and key_type are the same: elements are their own keys. In others, the key is some specific part of the value. Since elements are stored according to their keys, it is essential that the key associated with each element is immutable. In Simple Associative Containers this means that the elements themselves are immutable, while in other types of Associative Containers, such as Pair Associative Containers, the elements themselves are mutable but the part of an element that is its key cannot be modified. This means that an Associative Container's value type is not Assignable.