23 Containers library [containers]

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.

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]:

• (14.1)

  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.

• (14.2)

  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.

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