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.