23 Containers library [containers]

23.2 Container requirements [container.requirements]

23.2.3 Sequence containers [sequence.reqmts]

A sequence container organizes a finite set of objects, all of the same type, into a strictly linear arrangement. The library provides four basic kinds of sequence containers: vector, forward_list, list, and deque. In addition, array is provided as a sequence container which provides limited sequence operations because it has a fixed number of elements. The library also provides container adaptors that make it easy to construct abstract data types, such as stacks or queues, out of the basic sequence container kinds (or out of other kinds of sequence containers that the user might define).

The sequence containers offer the programmer different complexity trade-offs and should be used accordingly. vector or array is the type of sequence container that should be used by default. list or forward_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.

In Tables [tab:containers.sequence.requirements] and [tab:containers.sequence.optional], X denotes a sequence container class, a denotes a value of X containing elements of type T, A denotes X::allocator_type if it exists and std::allocator<T> if it doesn't, i and j denote iterators satisfying input iterator requirements and refer to elements implicitly convertible to value_type, [i, j) denotes a valid range, il designates an object of type initializer_list<value_type>, n denotes a value of X::size_type, p denotes a valid const iterator to a, q denotes a valid dereferenceable const iterator to a, [q1, q2) denotes a valid range of const iterators in a, t denotes an lvalue or a const rvalue of X::value_type, and rv denotes a non-const rvalue of X::value_type. Args denotes a template parameter pack; args denotes a function parameter pack with the pattern Args&&.

The complexities of the expressions are sequence dependent.

Table 100 — Sequence container requirements (in addition to container)
ExpressionReturn typeAssertion/note
pre-/post-condition
X(n, t)
X a(n, t)
Requires: T shall be CopyInsertable into X.
post: distance(begin(), end()) == n
Constructs a sequence container with n copies of t
X(i, j)
X a(i, j)
Requires: T shall be EmplaceConstructible into X from *i. For vector, if the iterator does not meet the forward iterator requirements ([forward.iterators]), T shall also be MoveInsertable into X. Each iterator in the range [i,j) shall be dereferenced exactly once.
post: distance(begin(), end()) == distance(i, j)
Constructs a sequence container equal to the range [i, j)
X(il); Equivalent to X(il.begin(), il.end())
a = il; X& Requires: T is CopyInsertable into X and CopyAssignable. Assigns the range [il.begin(),il.end()) into a. All existing elements of a are either assigned to or destroyed.
Returns: *this.
a.emplace(p, args); iterator Requires: T is EmplaceConstructible into X from args. For vector and deque, T is also MoveInsertable into X and MoveAssignable. Effects: Inserts an object of type T constructed with std::forward<Args>(args)... before p.
a.insert(p,t) iterator Requires: T shall be CopyInsertable into X. For vector and deque, T shall also be CopyAssignable.
Effects: Inserts a copy of t before p.
a.insert(p,rv) iterator Requires: T shall be MoveInsertable into X. For vector and deque, T shall also be MoveAssignable.
Effects: Inserts a copy of rv before p.
a.insert(p,n,t) iterator Requires: T shall be CopyInsertable into X and CopyAssignable.
Inserts n copies of t before p.
a.insert(p,i,j) iterator Requires: T shall be EmplaceConstructible into X from *i. For vector, if the iterator does not meet the forward iterator requirements ([forward.iterators]), T shall also be MoveInsertable into X and MoveAssignable. Each iterator in the range [i,j) shall be dereferenced exactly once.
pre: i and j are not iterators into a.
Inserts copies of elements in [i, j) before p
a.insert(p, il); iterator a.insert(p, il.begin(), il.end()).
a.erase(q) iterator Requires: For vector and deque, T shall be MoveAssignable.
Effects: Erases the element pointed to by q
a.erase(q1,q2) iterator Requires: For vector and deque, T shall be MoveAssignable.
Effects: Erases the elements in the range [q1, q2).
a.clear() void Destroys all elements in a. Invalidates all references, pointers, and iterators referring to the elements of a and may invalidate the past-the-end iterator.
post: a.empty() returns true.
Complexity: Linear.
a.assign(i,j) void Requires: T shall be EmplaceConstructible into X from *i and assignable from *i. For vector, if the iterator does not meet the forward iterator requirements ([forward.iterators]), T shall also be MoveInsertable into X.
Each iterator in the range [i,j) shall be dereferenced exactly once.
pre: i, j are not iterators into a.
Replaces elements in a with a copy of [i, j).
a.assign(il) void a.assign(il.begin(), il.end()).
a.assign(n,t) void Requires: T shall be CopyInsertable into X and CopyAssignable.
pre: t is not a reference into a.
Replaces elements in a with n copies of t.

iterator and const_iterator types for sequence containers shall be at least of the forward iterator category.

The iterator returned from a.insert(p, t) points to the copy of t inserted into a.

The iterator returned from a.insert(p, rv) points to the copy of rv inserted into a.

The iterator returned from a.insert(p, n, t) points to the copy of the first element inserted into a, or p if n == 0.

The iterator returned from a.insert(p, i, j) points to the copy of the first element inserted into a, or p if i == j.

The iterator returned from a.insert(p, il) points to the copy of the first element inserted into a, or p if il is empty.

The iterator returned from a.emplace(p, args) points to the new element constructed from args into a.

The iterator returned from a.erase(q) points to the element immediately following q prior to the element being erased. If no such element exists, a.end() is returned.

The iterator returned by a.erase(q1,q2) points to the element pointed to by q2 prior to any elements being erased. If no such element exists, a.end() is returned.

For every sequence container defined in this Clause and in Clause [strings]:

  • If the constructor

    template <class InputIterator>
    X(InputIterator first, InputIterator last,
      const allocator_type& alloc = allocator_type())
    

    is called with a type InputIterator that does not qualify as an input iterator, then the constructor shall not participate in overload resolution.

  • If the member functions of the forms:

    template <class InputIterator>          // such as insert()
    rt fx1(const_iterator p, InputIterator first, InputIterator last);
    
    template <class InputIterator>          // such as append(), assign()
    rt fx2(InputIterator first, InputIterator last);
    
    template <class InputIterator>          // such as replace()
    rt fx3(const_iterator i1, const_iterator i2, InputIterator first, InputIterator last);
    

    are called with a type InputIterator that does not qualify as an input iterator, then these functions shall not participate in overload resolution.

The extent to which an implementation determines that a type cannot be an input iterator is unspecified, except that as a minimum integral types shall not qualify as input iterators.

Table [tab:containers.sequence.optional] lists operations that are provided for some types of sequence containers but not others. An implementation shall provide these operations for all container types shown in the “container” column, and shall implement them so as to take amortized constant time.

Table 101 — Optional sequence container operations
ExpressionReturn typeOperational semanticsContainer
a.front() reference; const_reference for constant a *a.begin() basic_string, array, deque, forward_list, list, vector
a.back() reference; const_reference for constant a { auto tmp = a.end();
-- tmp;
return *tmp; }
basic_string, array, deque, list, vector
a.emplace_- front(args) void Prepends an object of type T constructed with std::forward<Args>(args)....
Requires: T shall be EmplaceConstructible into X from args.
deque, forward_list, list
a.emplace_- back(args) void Appends an object of type T constructed with std::forward<Args>(args)....
Requires: T shall be EmplaceConstructible into X from args. For vector, T shall also be MoveInsertable into X.
deque, list, vector
a.push_front(t) void Prepends a copy of t.
Requires: T shall be CopyInsertable into X.
deque, forward_list, list
a.push_front(rv) void Prepends a copy of rv.
Requires: T shall be MoveInsertable into X.
deque, forward_list, list
a.push_back(t) void Appends a copy of t.
Requires: T shall be CopyInsertable into X.
basic_string, deque, list, vector
a.push_back(rv) void Appends a copy of rv.
Requires: T shall be MoveInsertable into X.
basic_string, deque, list, vector
a.pop_front() void Destroys the first element.
Requires: a.empty() shall be false.
deque, forward_list, list
a.pop_back() void Destroys the last element.
Requires: a.empty() shall be false.
basic_string, deque, list, vector
a[n] reference; const_reference for constant a *(a.begin() + n) basic_string, array, deque, vector
a.at(n) reference; const_reference for constant a *(a.begin() + n) basic_string, array, deque, vector

The member function at() provides bounds-checked access to container elements. at() throws out_of_range if n >= a.size().