C++ named requirements: SequenceContainer

From cppreference.com
< cpp‎ | named req
 
 
C++ named requirements
Basic
Type properties
Library-Wide
Container
SequenceContainer
Container Elements
(C++11)

Iterator
Stream I/O
Formatters
(C++20)
Random Numbers
(C++11)    
Concurrency
(C++11)
(C++11)
Ranges
Other
(C++11)


 

A SequenceContainer is a Container that stores objects of the same type in a linear arrangement.

Requirements

Legend
X A sequence container class
T The element type of X
a An rvalue expression of type X
u The name of a declared variable
A The allocator type of X: X::allocator_type if it exists, otherwise std::allocator<T>
[ij) LegacyInputIterators such that [ij) is a valid range and that the iterators refer to elements implicitly convertible to value_type
rg
(since C++23)
A value of a type R that models container-compatible-range<T>
il An object of type std::initializer_list<value_type>
n A value of type X::size_type
p A valid const iterator into a
q A valid dereferenceable const iterator into a
[q1q2) Two const iterators into a such that [q1q2) is a valid range
t An lvalue or const rvalue of type X::value_type
rv A non-const rvalue of type X::value_type
Args A template parameter pack
args A function parameter pack with the pattern Arg&&

The type X satisfies SequenceContainer if

  • The type X satisfies Container, and
  • The following expressions must be valid and have their specified effects for all sequence containers except std::array (see notes):
Expression Return type Effects Precondition Postcondition
X u(n, t) Constructs the sequence container holding n copies of t T is CopyInsertable into X std::distance(u.begin(), u.end())

    == n

X u(i, j) Constructs the sequence container equal, element-wise, to the range [ij) T is EmplaceConstructible from *i into X

(std::vector) If the iterators are not LegacyForwardIterators, T must be CopyInsertable

std::distance(u.begin(), u.end())

    == std::distance(i, j)

X(std::from_range, rg)
(since C++23)
Constructs the sequence container equal, element-wise, to the range rg T is EmplaceConstructible from *ranges::begin(rg) into X.

(std::vector) If R models neither ranges::sized_range nor ranges::forward_range, T must be MoveInsertable into X.

Each iterator in the range rg is dereferenced once.

std::distance(begin(), end())
    == ranges::distance(rg)

X(il) X(il.begin(), il.end())
a = il X& Assigns the range represented by il into a[1] T is CopyInsertable and CopyAssignable Existing elements of a are destroyed or assigned to
a.emplace(p, args) iterator Insert an object of type T, constructed with std::forward<Args>(args) before p T is EmplaceConstructible

(std::vector, std::deque) T is MoveAssignable and MoveInsertable

Returned iterator points at the element constructed from args into a
a.insert(p, t) iterator Inserts a copy of t before p T is CopyInsertable

(std::vector, std::deque) T is CopyAssignable or MoveAssignable

Returned iterator points at the copy of t inserted into a
a.insert(p, rv) iterator Inserts a copy of rv before
p, possibly using move semantics
T is MoveInsertable

(std::vector, std::deque) T is MoveAssignable

Returned iterator points at the copy of rv inserted into a
a.insert(p, n, t) iterator Inserts n copies of t before p T is CopyInsertable and CopyAssignable Returned iterator points at the copy of the first element inserted into a or is p for n == 0
a.insert(p, i, j) iterator Inserts copies of elements in
[ij) before p
T is EmplaceConstructible and i and j are not in a

(std::vector) If the iterators are not LegacyForwardIterators, T must be MoveInsertable and MoveAssignable

Each iterator in [ij) is dereferenced once. Returned iterator points at the copy of the first element inserted into a or is p for i == j
a.insert_range(p, rg)
(since C++23)
iterator Inserts copies of elements in rg before p T is EmplaceConstructible into X from *ranges::begin(rg).

(std::vector, std::deque) T is also MoveInsertable into X, and T is MoveConstructible, MoveAssignable, and Swappable. rg and a do not overlap.

Each iterator in the range rg is dereferenced once. Returned iterator points at the copy of the first element inserted into a or at p if rg is empty
a.insert(p, il) iterator a.insert(p,

         il.begin(),
         il.end())

Returned iterator points at the copy of the first element inserted into a or is p if il is empty.
a.erase(q) iterator Erases the element pointed to by q (std::vector, std::deque) T is MoveAssignable Returned iterator points at the element that was immediately following q prior to erasure, or a.end() if no such element exists.
a.erase(q1, q2) iterator Erases elements in
[q1q2)
(std::vector, std::deque) T is MoveAssignable Returned iterator points at the element that was pointed by q2 prior to any erasure, or a.end() if no such element exists.
a.clear() void Destroys all elements in a All references, pointers, and iterators are invalidated, including the end iterator. a.empty() == true
a.assign(i, j) void Replaces elements in a with a copy of [ij) T is EmplaceConstructible and i, j are not in a.

(std::vector) If the iterators are not LegacyForwardIterators, T must be MoveInsertable.

Each iterator in [ij) is dereferenced once
a.assign_range(rg)
(since C++23)
void Replaces elements in a with a copy of each element in rg T[2] is EmplaceConstructible into X from *ranges::begin(rg). rg and a do not overlap.

(std::vector) If R models neither ranges::sized_range nor ranges::forward_range, T is also MoveInsertable into X.

Each iterator in the range rg is dereferenced once. All references, pointers, and iterators are invalidated.

(std::vector, std::deque) Also invalidates the end iterator.

a.assign(il) void a.assign(il.begin(),

         il.end())

a.assign(n, t) void Replaces elements in a with n copies of t T is CopyInsertable and CopyAssignable
Notes
  1. std::array supports assignment from a braced-init-list, but not from an std::initializer_list.
  2. T and R are such that ranges::assignable_from<T&, ranges::range_reference_t<R>> is modeled.

Optional operations

The following expressions must be valid and have their specified effects for the sequence containers named, all operations except prepend_range and append_range (since C++23) take amortized constant time:

Expression Return type Effects Preconditions Containers
a.front() reference,

const_reference for const a

Equivalent to *a.begin() (all)
a.back() reference,

const_reference for const a

Equivalent to auto tmp = a.end();

--tmp;
return *tmp;

std::basic_string std::array std::deque std::list std::vector
a.emplace_front(args) void Prepends a T constructed with std::forward<Args>(args)... T is EmplaceConstructible into X from args std::deque std::forward_list std::list
a.emplace_back(args) void Appends a T constructed with std::forward<Args>(args)... T is EmplaceConstructible into X from args

(std::vector) T is MoveInsertable into X

std::deque std::list std::vector
a.push_front(t) void Prepends a copy of t T is CopyInsertable into X std::deque std::forward_list std::list
a.push_front(rv) void Prepends a copy of rv, possibly using move semantics T is MoveInsertable into X std::deque std::forward_list std::list
a.prepend_range(rg)
(since C++23)
void Inserts[1] copies of elements in rg before begin() dereferencing each iterator in rg once. T is EmplaceConstructible into X from *ranges::begin(rg)

(std::deque) T is also MoveInsertable into X, and T is MoveConstructible, MoveAssignable, and Swappable

std::deque std::forward_list std::list
a.push_back(t) void Appends a copy of t T is CopyInsertable into X std::basic_string std::deque std::list std::vector
a.push_back(rv) void Appends a copy of rv, possibly using move semantics T is MoveInsertable into X std::basic_string std::deque std::list std::vector
a.append_range(rg)
(since C++23)
void Inserts[1] copies of elements in rg before end() dereferencing each iterator in rg once. T is EmplaceConstructible into X from *ranges::begin(rg)

(std::vector) T is also MoveInsertable into X

std::deque std::list std::vector
a.pop_front() void Destroys the first element. a.empty()

    == false

std::deque std::forward_list std::list
a.pop_back() void Destroys the last element a.empty()

    == false

std::basic_string std::deque std::list std::vector
a[n] reference,

const_reference for const a

Equivalent to *(n + a.begin()) std::basic_string std::array std::deque std::vector
a.at(n) reference,

const_reference for const a

Equivalent to *(n + a.begin()), except that std::out_of_range is thrown if n >= size() std::basic_string std::array std::deque std::vector
Notes
  1. 1.0 1.1 Insertion order, relative to order of elements in rg, is non-reversing.

Additionally, for every sequence container:

  • A constructor template that takes two input iterators and the member function template overloads of insert, append, assign, replace that take two input iterators do not participate in overload resolution if the corresponding template argument does not satisfy LegacyInputIterator.
  • A deduction guide that has either a LegacyInputIterator or an Allocator template parameter does not participate in overload resolution if the type that does not qualify as an input iterator or an allocator respectively is deduced for that parameter.
(since C++17)

Sequence containers in the standard library

stores and manipulates sequences of characters
(class template)
(C++11)
static contiguous array
(class template)
dynamic contiguous array
(class template)
double-ended queue
(class template)
singly-linked list
(class template)
doubly-linked list
(class template)

Trade-offs / usage notes

std::vector Fast access but mostly inefficient insertions/deletions
std::array Fast access but fixed number of elements
std::list
std::forward_list
Efficient insertion/deletion in the middle of the sequence
std::deque Efficient insertion/deletion at the beginning and at the end of the sequence

Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

DR Applied to Behavior as published Correct behavior
LWG 139 C++98 the optional operations were not required to
be implemented for the designated containers
required with
amortized time
LWG 149 C++98 a.insert(p, t) returned iterator while
a.insert(p, n, t) and a.insert(p, n, t) returned void
they all return
iterator
LWG 151 C++98 q1 was dereferenceable[1] it can be non-dereferenceable
LWG 355 C++98 calling a.back() or a.pop_back() would
execute --a.end(), which is dangerous[2]
decrements a copy of
a.end() instead
LWG 589 C++98 the elements that i and j refer to
might not be convertible to value_type
they are implicitly
convertible to value_type
  1. It is a defect because it makes the behavior of a.erase(a.begin(), a.end()) undefined is a is an empty container.
  2. If the type of a.end() is a fundamental type, --a.end() is ill-formed. It is dangerous when the type of a is templated, in this case this bug can be difficult to be found.