26 Containers library [containers]

26.2 Container requirements [container.requirements]

26.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 79 and 80, 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.
Table 79 — Sequence container requirements (in addition to container)
Expression
Return type
Assertion/note
pre-/post-condition
X(n, t)
X u(n, t);
Requires:  T shall be CopyInsertable into X.

Postconditions: distance(begin(), end()) == n
Constructs a sequence container with n copies of t
X(i, j)
X u(i, j);
Requires:  T shall be EmplaceConstructible into X from *i.
For vector, if the iterator does not meet the forward iterator requirements, T shall also be MoveInsertable into X.
Each iterator in the range [i, j) shall be dereferenced exactly once.

Postconditions: 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 and deque, T shall also be MoveInsertable into X, MoveConstructible, MoveAssignable, and swappable.
Each iterator in the range [i, j) shall be dereferenced exactly once.

Requires: 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.

Postconditions: 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, T shall also be MoveInsertable into X.

Each iterator in the range [i, j) shall be dereferenced exactly once.

Requires: i, j are not iterators into a.

Replaces elements in a with a copy of [i, j).

Invalidates all references, pointers and iterators referring to the elements of a.
For vector and deque, also invalidates the past-the-end iterator.
a.assign(il)
void
a.assign(il.begin(), il.end()).
a.assign(n,t)
void
Requires:  T shall be CopyInsertable into X and CopyAssignable.

Requires: t is not a reference into a.

Replaces elements in a with n copies of t.

Invalidates all references, pointers and iterators referring to the elements of a.
For vector and deque, also invalidates the past-the-end iterator.
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 [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>
      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.
  • 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 80 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 80 — Optional sequence container operations
Expression
Return type
Operational semantics
Container
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)
reference
Prepends an object of type T constructed with std​::​forward<​Args​>(​args)....

Requires:  T shall be EmplaceConstructible into X from args.

Returns: a.front().
deque, forward_­list, list
a.emplace_­back(args)
reference
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.

Returns: a.back().
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().