21 Containers library [containers]

21.2 Container requirements [container.requirements]

21.2.1 General container requirements [container.requirements.general]

1
#
Containers are objects that store other objects.
They control allocation and deallocation of these objects through constructors, destructors, insert and erase operations.
2
#
All of the complexity requirements in this Clause are stated solely in terms of the number of operations on the contained objects.
[ Example
:
The copy constructor of type vector<vector<int>> has linear complexity, even though the complexity of copying each contained vector<int> is itself linear.
— end example
 ]
3
#
For the components affected by this subclause that declare an allocator_­type, objects stored in these components shall be constructed using the function allocator_­traits<allocator_­type>​::​rebind_­traits<U>​::​​construct and destroyed using the function allocator_­traits<allocator_­type>​::​rebind_­traits<U>​::​​destroy, where U is either allocator_­type::value_­type or an internal type used by the container.
These functions are called only for the container's element type, not for internal types used by the container.
[ Note
:
This means, for example, that a node-based container might need to construct nodes containing aligned buffers and call construct to place the element into the buffer.
— end note
 ]
4
#
In Tables 62, 63, and 64 X denotes a container class containing objects of type T, a and b denote values of type X, u denotes an identifier, r denotes a non-const value of type X, and rv denotes a non-const rvalue of type X.
Table 62 — Container requirements
Expression
Return type
Operational
Assertion/note
Complexity
semantics
pre-/post-condition
X::value_­type
T
Requires:  T is Cpp17Erasable from X (see [container.requirements.general], below)
compile time
X::reference
T&
compile time
X::const_­reference
const T&
compile time
X::iterator
iterator type whose value type is T
any iterator category that meets the forward iterator requirements.
convertible to X::const_­iterator.
compile time
X::const_­iterator
constant iterator type whose value type is T
any iterator category that meets the forward iterator requirements.
compile time
X::difference_­type
signed integer type
is identical to the difference type of X::iterator and X::const_­iterator
compile time
X::size_­type
unsigned integer type
size_­type can represent any non-negative value of difference_­type
compile time
X u;
Ensures: u.empty()
constant
X()
Ensures: X().empty()
constant
X(a)
Requires: T is Cpp17CopyInsertable into X (see below).

Ensures: a == X(a).
linear
X u(a);
X u = a;
Requires: T is Cpp17CopyInsertable into X (see below).

Ensures: u == a
linear
X u(rv);
X u = rv;
Ensures: u shall be equal to the value that rv had before this construction
(Note B)
a = rv
X&
All existing elements of a are either move assigned to or destroyed
a shall be equal to the value that rv had before this assignment
linear
a.~X()
void
the destructor is applied to every element of a; any memory obtained is deallocated.
linear
a.begin()
iterator; const_­iterator for constant a
constant
a.end()
iterator; const_­iterator for constant a
constant
a.cbegin()
const_­iterator
const_­cast<​X const&​>(a)​.begin();
constant
a.cend()
const_­iterator
const_­cast<​X const&​>(a)​.end();
constant
a == b
convertible to bool
== is an equivalence relation.
equal(​a.begin(), a.end(), b.begin(), b.end())
Requires:  T is Cpp17EqualityComparable
Constant if a.size() != b.size(), linear otherwise
a != b
convertible to bool
Equivalent to !(a == b)
linear
a.swap(b)
void
exchanges the contents of a and b
(Note A)
swap(a, b)
void
Equivalent to a.swap(b)
(Note A)
r = a
X&
Ensures: r == a.
linear
a.size()
size_­type
distance(​a.begin(), a.end())
constant
a.max_­size()
size_­type
distance(​begin(), end()) for the largest possible container
constant
a.empty()
convertible to bool
a.begin() == a.end()
constant
Those entries marked “(Note A)” or “(Note B)” have linear complexity for array and have constant complexity for all other standard containers.
[ Note
:
The algorithm equal() is defined in [algorithms].
— end note
 ]
5
#
The member function size() returns the number of elements in the container.
The number of elements is defined by the rules of constructors, inserts, and erases.
6
#
begin() returns an iterator referring to the first element in the container.
end() returns an iterator which is the past-the-end value for the container.
If the container is empty, then begin() == end().
7
#
In the expressions 
i == j
i != j
i < j
i <= j
i >= j
i > j
i - j
where i and j denote objects of a container's iterator type, either or both may be replaced by an object of the container's const_­iterator type referring to the same element with no change in semantics.
8
#
Unless otherwise specified, all containers defined in this clause obtain memory using an allocator (see [allocator.requirements]).
[ Note
:
In particular, containers and iterators do not store references to allocated elements other than through the allocator's pointer type, i.e., as objects of type P or pointer_­traits<P>::template rebind<unspecified>, where P is allocator_­traits<allocator_­type>::pointer.
— end note
 ]
Copy constructors for these container types obtain an allocator by calling allocator_­traits<allocator_­type>::select_­on_­container_­copy_­construction on the allocator belonging to the container being copied.
Move constructors obtain an allocator by move construction from the allocator belonging to the container being moved.
Such move construction of the allocator shall not exit via an exception.
All other constructors for these container types take a const allocator_­type& argument.
[ Note
:
If an invocation of a constructor uses the default value of an optional allocator argument, then the allocator type must support value-initialization.
— end note
 ]
A copy of this allocator is used for any memory allocation and element construction performed, by these constructors and by all member functions, during the lifetime of each container object or until the allocator is replaced.
The allocator may be replaced only via assignment or swap().
Allocator replacement is performed by copy assignment, move assignment, or swapping of the allocator only if allocator_­traits<allocator_­type>::propagate_­on_­container_­copy_­assignment::value, allocator_­traits<allocator_­type>::propagate_­on_­container_­move_­assignment::value, or allocator_­traits<allocator_­type>::propagate_­on_­container_­swap::value is true within the implementation of the corresponding container operation.
In all container types defined in this Clause, the member get_­allocator() returns a copy of the allocator used to construct the container or, if that allocator has been replaced, a copy of the most recent replacement.
9
#
The expression a.swap(b), for containers a and b of a standard container type other than array, shall exchange the values of a and b without invoking any move, copy, or swap operations on the individual container elements.
Lvalues of any Compare, Pred, or Hash types belonging to a and b shall be swappable and shall be exchanged by calling swap as described in [swappable.requirements].
If allocator_­traits<allocator_­type>::propagate_­on_­container_­swap::value is true, then lvalues of type allocator_­type shall be swappable and the allocators of a and b shall also be exchanged by calling swap as described in [swappable.requirements].
Otherwise, the allocators shall not be swapped, and the behavior is undefined unless a.get_­allocator() == b.get_­allocator().
Every iterator referring to an element in one container before the swap shall refer to the same element in the other container after the swap.
It is unspecified whether an iterator with value a.end() before the swap will have value b.end() after the swap.
10
#
If the iterator type of a container belongs to the bidirectional or random access iterator categories, the container is called reversible and satisfies the additional requirements in Table 63.
Table 63 — Reversible container requirements
Expression
Return type
Assertion/note
Complexity
pre-/post-condition
X::reverse_­iterator
iterator type whose value type is T
reverse_­iterator<iterator>
compile time
X::const_­reverse_­iterator
constant iterator type whose value type is T
reverse_­iterator<const_­iterator>
compile time
a.rbegin()
reverse_­iterator; const_­reverse_­iterator for constant a
reverse_­iterator(end())
constant
a.rend()
reverse_­iterator; const_­reverse_­iterator for constant a
reverse_­iterator(begin())
constant
a.crbegin()
const_­reverse_­iterator
const_­cast<X const&>(a).rbegin()
constant
a.crend()
const_­reverse_­iterator
const_­cast<X const&>(a).rend()
constant
11
#
Unless otherwise specified (see [associative.reqmts.except], [unord.req.except], [deque.modifiers], and [vector.modifiers]) all container types defined in this Clause meet the following additional requirements:
  • (11.1)
    if an exception is thrown by an insert() or emplace() function while inserting a single element, that function has no effects.
  • (11.2)
    if an exception is thrown by a push_­back(), push_­front(), emplace_­back(), or emplace_­front() function, that function has no effects.
  • (11.3)
    no erase(), clear(), pop_­back() or pop_­front() function throws an exception.
  • (11.4)
    no copy constructor or assignment operator of a returned iterator throws an exception.
  • (11.5)
    no swap() function throws an exception.
  • (11.6)
    no swap() function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped.
    [ Note
    :
    The end() iterator does not refer to any element, so it may be invalidated.
    — end note
     ]
12
#
Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container.
13
#
A contiguous container is a container whose member types iterator and const_­iterator meet the Cpp17RandomAccessIterator requirements ([random.access.iterators]) and model ContiguousIterator ([iterator.concept.contiguous]).
14
#
Table 64 lists operations that are provided for some types of containers but not others.
Those containers for which the listed operations are provided shall implement the semantics described in Table 64 unless otherwise stated.
If the iterators passed to lexicographical_­compare satisfy the constexpr iterator requirements ([iterator.requirements.general]) then the operations described in Table 64 are implemented by constexpr functions.
Table 64 — Optional container operations
Expression
Return type
Operational
Assertion/note
Complexity
semantics
pre-/post-condition
a < b
convertible to bool
lexicographical_­compare( a.begin(), a.end(), b.begin(), b.end())
Requires: < is defined for values of T.
< is a total ordering relationship.
linear
a > b
convertible to bool
b < a
linear
a <= b
convertible to bool
!(a > b)
linear
a >= b
convertible to bool
!(a < b)
linear
[ Note
:
The algorithm lexicographical_­compare() is defined in [algorithms].
— end note
 ]
15
#
All of the containers defined in this Clause and in [basic.string] except array meet the additional requirements of an allocator-aware container, as described in Table 65.
Given an allocator type A and given a container type X having a value_­type identical to T and an allocator_­type identical to allocator_­traits<A>::rebind_­alloc<T> and given an lvalue m of type A, a pointer p of type T*, an expression v of type (possibly const) T, and an rvalue rv of type T, the following terms are defined.
If X is not allocator-aware, the terms below are defined as if A were allocator<T> — no allocator object needs to be created and user specializations of allocator<T> are not instantiated:
  • (15.1)
    T is Cpp17DefaultInsertable into X means that the following expression is well-formed: 
    allocator_traits<A>::construct(m, p)
  • (15.2)
    An element of X is default-inserted if it is initialized by evaluation of the expression 
    allocator_traits<A>::construct(m, p)
    where p is the address of the uninitialized storage for the element allocated within X.
  • (15.3)
    T is Cpp17MoveInsertable into X means that the following expression is well-formed: 
    allocator_traits<A>::construct(m, p, rv)
    and its evaluation causes the following postcondition to hold: The value of *p is equivalent to the value of rv before the evaluation.
    [ Note
    :
    rv remains a valid object.
    Its state is unspecified
    — end note
     ]
  • (15.4)
    T is Cpp17CopyInsertable into X means that, in addition to T being Cpp17MoveInsertable into X, the following expression is well-formed: 
    allocator_traits<A>::construct(m, p, v)
    and its evaluation causes the following postcondition to hold: The value of v is unchanged and is equivalent to *p.
  • (15.5)
    T is Cpp17EmplaceConstructible into X from args, for zero or more arguments args, means that the following expression is well-formed: 
    allocator_traits<A>::construct(m, p, args)
  • (15.6)
    T is Cpp17Erasable from X means that the following expression is well-formed: 
    allocator_traits<A>::destroy(m, p)
[ Note
:
A container calls allocator_­traits<A>::construct(m, p, args) to construct an element at p using args, with m == get_­allocator().
The default construct in allocator will call ::new((void*)p) T(args), but specialized allocators may choose a different definition.
— end note
 ]
16
#
In Table 65, X denotes an allocator-aware container class with a value_­type of T using allocator of type A, u denotes a variable, a and b denote non-const lvalues of type X, t denotes an lvalue or a const rvalue of type X, rv denotes a non-const rvalue of type X, and m is a value of type A.
Table 65 — Allocator-aware container requirements
Expression
Return type
Assertion/note
Complexity
pre-/post-condition
allocator_­type
A
Requires: allocator_­type::value_­type is the same as X::value_­type.
compile time
get_­- allocator()
A
constant
X()
X u;
Requires:  A is Cpp17DefaultConstructible.

Ensures: u.empty() returns true, u.get_­allocator() == A()
constant
X(m)
Ensures: u.empty() returns true,
constant
X u(m);
u.get_­allocator() == m
X(t, m)
X u(t, m);
Requires:  T is Cpp17CopyInsertable into X.

Ensures: u == t, u.get_­allocator() == m
linear
X(rv)
X u(rv);
Ensures: u shall have the same elements as rv had before this construction; the value of u.get_­allocator() shall be the same as the value of rv.get_­allocator() before this construction.
constant
X(rv, m)
X u(rv, m);
Requires:  T is Cpp17MoveInsertable into X.

Ensures: u shall have the same elements, or copies of the elements, that rv had before this construction, u.get_­allocator() == m
constant if m == rv.get_­allocator(), otherwise linear
a = t
X&
Requires:  T is Cpp17CopyInsertable into X and Cpp17CopyAssignable.

Ensures: a == t
linear
a = rv
X&
Requires:  If allocator_­-
traits<allocator_­type>
::propagate_­on_­container_­-
move_­assignment::value is
false, T is Cpp17MoveInsertable into X and Cpp17MoveAssignable.
All existing elements of a are either move assigned to or destroyed.

Ensures: a shall be equal to the value that rv had before this assignment.
linear
a.swap(b)
void
exchanges the contents of a and b
constant
17
#
The behavior of certain container member functions and deduction guides depends on whether types qualify as input iterators or allocators.
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.
Likewise, the extent to which an implementation determines that a type cannot be an allocator is unspecified, except that as a minimum a type A shall not qualify as an allocator unless it satisfies both of the following conditions: