24 Containers library [containers]

24.2 Requirements [container.requirements]

24.2.4 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 defines).
[Note 1:
The sequence containers offer the programmer different complexity trade-offs.
vector is appropriate in most circumstances.
array has a fixed size known during translation.
list or forward_­list support frequent insertions and deletions from the middle of the sequence.
deque supports efficient insertions and deletions taking place at the beginning or at the end of the sequence.
When choosing a container, remember vector is best; leave a comment to explain if you choose from the rest!
— end note]
In this subclause,
  • 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 that meet the Cpp17InputIterator requirements and refer to elements implicitly convertible to value_­type,
  • [i, j) denotes a valid range,
  • rg denotes a value of a type R that models container-compatible-range<T>,
  • 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.
A type X meets the sequence container requirements if X meets the container requirements and the following statements and expressions are well-formed and have the specified semantics.
X u(n, t);
Preconditions: T is Cpp17CopyInsertable into X.
Effects: Constructs a sequence container with n copies of t.
Postconditions: distance(u.begin(), u.end()) == n is true.
X u(i, j);
Preconditions: T is Cpp17EmplaceConstructible into X from *i.
For vector, if the iterator does not meet the Cpp17ForwardIterator requirements ([forward.iterators]), T is also Cpp17MoveInsertable into X.
Effects: Constructs a sequence container equal to the range [i, j).
Each iterator in the range [i, j) is dereferenced exactly once.
Postconditions: distance(u.begin(), u.end()) == distance(i, j) is true.
X(from_range, rg)
Preconditions: T is Cpp17EmplaceConstructible into X from *ranges​::​begin(rg).
For vector, if R models neither ranges​::​sized_­range nor ranges​::​forward_­range, T is also Cpp17MoveInsertable into X.
Effects: Constructs a sequence container equal to the range rg.
Each iterator in the range rg is dereferenced exactly once.
Postconditions: distance(begin(), end()) == ranges​::​distance(rg) is true.
X(il)
Effects: Equivalent to X(il.begin(), il.end()).
a = il
Result: X&.
Preconditions: T is Cpp17CopyInsertable into X and Cpp17CopyAssignable.
Effects: 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)
Result: iterator.
Preconditions: T is Cpp17EmplaceConstructible into X from args.
For vector and deque, T is also Cpp17MoveInsertable into X and Cpp17MoveAssignable.
Effects: Inserts an object of type T constructed with std​::​forward<Args>(args)... before p.
[Note 2:
args can directly or indirectly refer to a value in a.
— end note]
Returns: An iterator that points to the new element constructed from args into a.
a.insert(p, t)
Result: iterator.
Preconditions: T is Cpp17CopyInsertable into X.
For vector and deque, T is also Cpp17CopyAssignable.
Effects: Inserts a copy of t before p.
Returns: An iterator that points to the copy of t inserted into a.
a.insert(p, rv)
Result: iterator.
Preconditions: T is Cpp17MoveInsertable into X.
For vector and deque, T is also Cpp17MoveAssignable.
Effects: Inserts a copy of rv before p.
Returns: An iterator that points to the copy of rv inserted into a.
a.insert(p, n, t)
Result: iterator.
Preconditions: T is Cpp17CopyInsertable into X and Cpp17CopyAssignable.
Effects: Inserts n copies of t before p.
Returns: An iterator that points to the copy of the first element inserted into a, or p if n == 0.
a.insert(p, i, j)
Result: iterator.
Preconditions: T is Cpp17EmplaceConstructible into X from *i.
For vector and deque, T is also Cpp17MoveInsertable into X, Cpp17MoveConstructible, Cpp17MoveAssignable, and swappable ([swappable.requirements]).
Neither i nor j are iterators into a.
Effects: Inserts copies of elements in [i, j) before p.
Each iterator in the range [i, j) shall be dereferenced exactly once.
Returns: An iterator that points to the copy of the first element inserted into a, or p if i == j.
a.insert_range(p, rg)
Result: iterator.
Preconditions: T is Cpp17EmplaceConstructible into X from *ranges​::​begin(rg).
For vector and deque, T is also Cpp17MoveInsertable into X, Cpp17MoveConstructible, Cpp17MoveAssignable, and swappable ([swappable.requirements]).
rg and a do not overlap.
Effects: Inserts copies of elements in rg before p.
Each iterator in the range rg is dereferenced exactly once.
Returns: An iterator that points to the copy of the first element inserted into a, or p if rg is empty.
a.insert(p, il)
Effects: Equivalent to a.insert(p, il.begin(), il.end()).
a.erase(q)
Result: iterator.
Preconditions: For vector and deque, T is Cpp17MoveAssignable.
Effects: Erases the element pointed to by q.
Returns: An iterator that points to the element immediately following q prior to the element being erased.
If no such element exists, a.end() is returned.
a.erase(q1, q2)
Result: iterator.
Preconditions: For vector and deque, T is Cpp17MoveAssignable.
Effects: Erases the elements in the range [q1, q2).
Returns: An iterator that points to the element pointed to by q2 prior to any elements being erased.
If no such element exists, a.end() is returned.
a.clear()
Result: void
Effects: 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() is true.
Complexity: Linear.
a.assign(i, j)
Result: void
Preconditions: T is Cpp17EmplaceConstructible into X from *i and assignable from *i.
For vector, if the iterator does not meet the forward iterator requirements ([forward.iterators]), T is also Cpp17MoveInsertable into X.
Neither i nor j are iterators into a.
Effects: 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.
Each iterator in the range [i, j) is dereferenced exactly once.
a.assign_range(rg)
Result: void
Mandates: assignable_­from<T&, ranges​::​range_­reference_­t<R>> is modeled.
Preconditions: T is Cpp17EmplaceConstructible into X from *ranges​::​begin(rg).
For vector, if R models neither ranges​::​sized_­range nor ranges​::​forward_­range, T is also Cpp17MoveInsertable into X.
rg and a do not overlap.
Effects: Replaces elements in a with a copy of each element in rg.
Invalidates all references, pointers, and iterators referring to the elements of a.
For vector and deque, also invalidates the past-the-end iterator.
Each iterator in the range rg is dereferenced exactly once.
a.assign(il)
Effects: Equivalent to a.assign(il.begin(), il.end()).
a.assign(n, t)
Result: void
Preconditions: T is Cpp17CopyInsertable into X and Cpp17CopyAssignable.
t is not a reference into a.
Effects: 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.
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.
The following operations are provided for some types of sequence containers but not others.
An implementation shall implement them so as to take amortized constant time.
a.front()
Result: reference; const_­reference for constant a.
Returns: *a.begin()
Remarks: Required for basic_­string, array, deque, forward_­list, list, and vector.
a.back()
Result: reference; const_­reference for constant a.
Effects: Equivalent to: auto tmp = a.end(); --tmp; return *tmp;
Remarks: Required for basic_­string, array, deque, list, and vector.
a.emplace_front(args)
Result: reference
Preconditions: T is Cpp17EmplaceConstructible into X from args.
Effects: Prepends an object of type T constructed with std​::​forward<Args>(args)....
Returns: a.front().
Remarks: Required for deque, forward_­list, and list.
a.emplace_back(args)
Result: reference
Preconditions: T is Cpp17EmplaceConstructible into X from args.
For vector, T is also Cpp17MoveInsertable into X.
Effects: Appends an object of type T constructed with std​::​forward<Args>(args)....
Returns: a.back().
Remarks: Required for deque, list, and vector.
a.push_front(t)
Result: void
Preconditions: T is Cpp17CopyInsertable into X.
Effects: Prepends a copy of t.
Remarks: Required for deque, forward_­list, and list.
a.push_front(rv)
Result: void
Preconditions: T is Cpp17MoveInsertable into X.
Effects: Prepends a copy of rv.
Remarks: Required for deque, forward_­list, and list.
a.prepend_range(rg)
Result: void
Preconditions: T is Cpp17EmplaceConstructible into X from *ranges​::​begin(rg).
Effects: Inserts copies of elements in rg before begin().
Each iterator in the range rg is dereferenced exactly once.
[Note 3:
The order of elements in rg is not reversed.
— end note]
Remarks: Required for deque, forward_­list, and list.
a.push_back(t)
Result: void
Preconditions: T is Cpp17CopyInsertable into X.
Effects: Appends a copy of t.
Remarks: Required for basic_­string, deque, list, and vector.
a.push_back(rv)
Result: void
Preconditions: T is Cpp17MoveInsertable into X.
Effects: Appends a copy of rv.
Remarks: Required for basic_­string, deque, list, and vector.
a.append_range(rg)
Result: void
Preconditions: T is Cpp17EmplaceConstructible into X from *ranges​::​begin(rg).
For vector, T is also Cpp17MoveInsertable into X.
Effects: Inserts copies of elements in rg before end().
Each iterator in the range rg is dereferenced exactly once.
Remarks: Required for deque, list, and vector.
a.pop_front()
Result: void
Preconditions: a.empty() is false.
Effects: Destroys the first element.
Remarks: Required for deque, forward_­list, and list.
a.pop_back()
Result: void
Preconditions: a.empty() is false.
Effects: Destroys the last element.
Remarks: Required for basic_­string, deque, list, and vector.
a[n]
Result: reference; const_­reference for constant a
Returns: *(a.begin() + n)
Remarks: Required for basic_­string, array, deque, and vector.
a.at(n)
Result: reference; const_­reference for constant a
Returns: *(a.begin() + n)
Throws: out_­of_­range if n >= a.size().
Remarks: Required for basic_­string, array, deque, and vector.