26 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 87 and 88, X denotes a sequence container class, a denotes a value of type X containing elements of type T, u denotes the name of a variable being declared, A denotes X​::​allocator_­type if the qualified-id X​::​allocator_­type is valid and denotes a type ([temp.deduct]) and 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 type X​::​size_­type, p denotes a valid constant iterator to a, q denotes a valid dereferenceable constant iterator to a, [q1, q2) denotes a valid range of constant 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.

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

• (13.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.

• (13.2)

  If the member functions of the forms:

  template <class InputIterator>
    return-type F(const_iterator p,
                  InputIterator first, InputIterator last);       // such as insert
  
  template <class InputIterator>
    return-type F(InputIterator first, InputIterator last);       // such as append, assign
  
  template <class InputIterator>
    return-type F(const_iterator i1, const_iterator i2,
                  InputIterator first, InputIterator last);       // such as replace
  

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

• (13.3)

  A deduction guide for a sequence container shall not participate in overload resolution if it has an InputIterator template parameter and a type that does not qualify as an input iterator is deduced for that parameter, or if it has an Allocator template parameter and a type that does not qualify as an allocator is deduced for that parameter.

Table 88 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().