Standard Template Library Programmer's Guide

[1] The name deque is pronounced "deck", and stands for "double-ended queue." Knuth (section 2.6) reports that the name was coined by E. J. Schweppe. See section 2.2.1 of Knuth for more information about deques. (D. E. Knuth, The Art of Computer Programming. Volume 1: Fundamental Algorithms , second edition. Addison-Wesley, 1973.)

[2] Inserting an element at the beginning or end of a deque takes amortized constant time. Inserting an element in the middle is linear in n , where n is the smaller of the number of elements from the insertion point to the beginning, and the number of elements from the insertion point to the end.

[3] The semantics of iterator invalidation for deque is as follows. Insert (including push_front and push_back ) invalidates all iterators that refer to a deque . Erase in the middle of a deque invalidates all iterators that refer to the deque . Erase at the beginning or end of a deque (including pop_front and pop_back ) invalidates an iterator only if it points to the erased element.

[4] This member function relies on member template functions, which at present (early 1998) are not supported by all compilers. If your compiler supports member templates, you can call this function with any type of input iterator. If your compiler does not yet support member templates, though, then the arguments must either be of type const value_type* or of type deque::const_iterator .

vector , list , slist

Category: containers

Component type: type

A list is a doubly linked list. That is, it is a Sequence that supports both forward and backward traversal, and (amortized) constant time insertion and removal of elements at the beginning or the end, or in the middle. List s have the important property that insertion and splicing do not invalidate iterators to list elements, and that even removal invalidates only the iterators that point to the elements that are removed. The ordering of iterators may be changed (that is, list::iterator might have a different predecessor or successor after a list operation than it did before), but the iterators themselves will not be invalidated or made to point to different elements unless that invalidation or mutation is explicit. [1]

Note that singly linked lists, which only support forward traversal, are also sometimes useful. If you do not need backward traversal, then slist may be more efficient than list . Definition Defined in the standard header list, and in the nonstandard backward-compatibility header list.h.

list L;

L.push_back(0);

L.push_front(1);

L.insert(++L.begin(), 2);

copy(L.begin(), L.end(), ostream_iterator(cout, " "));

// The values that are printed are 1 2 0

Reversible Container, Front Insertion Sequence, Back Insertion Sequence.

None, except for those imposed by the requirements of Reversible Container, Front Insertion Sequence, and Back Insertion Sequence.

None.

These members are not defined in the Reversible Container, Front Insertion Sequence, and Back Insertion Sequence requirements, but are specific to list .