23 Containers library [containers]

23.2 Container requirements [container.requirements]

23.2.1 General container requirements [container.requirements.general]

Containers are objects that store other objects. They control allocation and deallocation of these objects through constructors, destructors, insert and erase operations.

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 ]

For the components affected by this subclause that declare an allocator_type, objects stored in these components shall be constructed using the allocator_traits<allocator_type>::construct function and destroyed using the allocator_traits<allocator_type>::destroy function ([allocator.traits.members]). 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 ]

In Tables [tab:containers.container.requirements] and [tab:containers.reversible.requirements], 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 96 — Container requirements
ExpressionReturn typeOperationalAssertion/noteComplexity
semanticspre-/post-condition
X::value_type T Requires: T is Destructible compile time
X::reference lvalue of T compile time
X::const_reference const lvalue of 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; post: u.empty() constant
X() post: X().empty() constant
X(a) Requires: T is CopyInsertable into X (see below).
post: a == X(a).
linear
X u(a)
X u = a;
Requires: T is CopyInsertable into X (see below).
post: u == a
linear
X u(rv)
X u = rv
post: 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 note: the destructor is applied to every element of a; all the memory 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. distance(a.begin(), a.end()) == distance(b.begin(), b.end()) && equal(a.begin(), a.end(), b.begin()) Requires: T is EqualityComparable linear
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 a.swap(b) (Note A)
r = a X& post: 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

Notes: the algorithm equal() is defined in Clause [algorithms]. Those entries marked “(Note A)” or “(Note B)” have linear complexity for array and have constant complexity for all other standard containers.

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.

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();

Unless otherwise specified, all containers defined in this clause obtain memory using an allocator (see [allocator.requirements]). Copy constructors for these container types obtain an allocator by calling allocator_traits<allocator_type>::select_on_container_copy_construction on their first parameters. 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 an Allocator& argument ([allocator.requirements]), an allocator whose value type is the same as the container's value type. [ 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 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. The behavior of a call to a container's swap function is undefined unless the objects being swapped have allocators that compare equal or allocator_traits<allocator_type>::propagate_on_container_swap::value is true. 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.

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. Any Compare, Pred, or Hash objects belonging to a and b shall be swappable and shall be exchanged by unqualified calls to non-member swap. If allocator_traits<allocator_type>::propagate_on_container_swap::value is true, then the allocators of a and b shall also be exchanged using an unqualified call to non-member swap. Otherwise, they 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.

If the iterator type of a container belongs to the bidirectional or random access iterator categories ([iterator.requirements]), the container is called reversible and satisfies the additional requirements in Table [tab:containers.reversible.requirements].

Table 97 — Reversible container requirements
ExpressionReturn typeAssertion/noteComplexity
pre-/post-condition
X::reverse_iterator iterator type whose value type is T reverse_iterator<iterator> compile time
X::const_reverse_iterator iterator type whose value type is const 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

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:

  • if an exception is thrown by an insert() or emplace() function while inserting a single element, that function has no effects.

  • if an exception is thrown by a push_back() or push_front() function, that function has no effects.

  • no erase(), clear(), pop_back() or pop_front() function throws an exception.

  • no copy constructor or assignment operator of a returned iterator throws an exception.

  • no swap() function throws an exception.

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

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.

Table [tab:containers.optional.operations] 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 [tab:containers.optional.operations] unless otherwise stated.

Table 98 — Optional container operations
ExpressionReturn typeOperationalAssertion/noteComplexity
semanticspre-/post-condition
a < b convertible to bool lexicographical_compare( a.begin(), a.end(), b.begin(), b.end()) pre: < 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 Clause [algorithms].

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 [tab:containers.allocatoraware].

Given a container type X having an allocator_type identical to A and a value_type identical to T and given an lvalue m of type A, a pointer p of type T*, an expression v of type 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 std::allocator<T>.)

Note: A container calls allocator_traits<A>::construct(m, p, args) to construct an element at p using args. The default construct in std::allocator will call ::new((void*)p) T(args), but specialized allocators may choose a different definition.  — end note ]

In Table [tab:containers.allocatoraware], 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, m is a value of type A, and Q is an allocator type.

Table 99 — Allocator-aware container requirements
ExpressionReturn typeAssertion/noteComplexity
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 DefaultConstructible.
post: u.empty() returns true, u.get_allocator() == A()
constant
X(m) post: u.empty() returns true, constant
X u(m); u.get_allocator() == m
X(t, m)
X u(t, m);
Requires: T is CopyInsertable into X.
post: u == t, get_allocator() == m
linear
X(rv)
X u(rv)
Requires: move construction of A shall not exit via an exception.
post: u shall have the same elements as rv had before this construction; the value of 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 MoveInsertable into X.
post: u shall have the same elements, or copies of the elements, that rv had before this construction, get_allocator() == m
constant if m == rv.get_allocator(), otherwise linear
a = t X& Requires: T is CopyInsertable into X and CopyAssignable.
post: a == t
linear
a = rv X& Requires: If allocator_-
traits<allocator_type>
::propagate_on_container_-
move_assignment::value is
false, T is MoveInsertable into X and MoveAssignable. All existing elements of a are either move assigned to or destroyed.
post: 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