24 Containers library [containers]

24.2 Requirements [container.requirements]

24.2.2 General containers [container.gen.reqmts]

24.2.2.2 Containers [container.reqmts]

A type X meets the container requirements if the following types, statements, and expressions are well-formed and have the specified semantics.
typename X::value_type
Result: T
Preconditions: T is Cpp17Erasable from X (see [container.alloc.reqmts], below).
typename X::reference
Result: T&
typename X::const_reference
Result: const T&
typename X::iterator
Result: A type that meets the forward iterator requirements ([forward.iterators]) with value type T.
The type X​::​iterator is convertible to X​::​const_­iterator.
typename X::const_iterator
Result: A type that meets the requirements of a constant iterator and those of a forward iterator with value type T.
typename X::difference_type
Result: A signed integer type, identical to the difference type of X​::​iterator and X​::​const_­iterator.
typename X::size_type
Result: An unsigned integer type that can represent any non-negative value of X​::​difference_­type.
X u; X u = X();
Postconditions: u.empty()
Complexity: Constant.
X u(a); X u = a;
Preconditions: T is Cpp17CopyInsertable into X (see below).
Postconditions: u == a
Complexity: Linear.
X u(rv); X u = rv;
Postconditions: u is equal to the value that rv had before this construction.
Complexity: Linear for array and constant for all other standard containers.
a = rv
Result: X&.
Effects: All existing elements of a are either move assigned to or destroyed.
Postconditions: If a and rv do not refer to the same object, a is equal to the value that rv had before this assignment.
Complexity: Linear.
a.~X()
Result: void
Effects: Destroys every element of a; any memory obtained is deallocated.
Complexity: Linear.
a.begin()
Result: iterator; const_­iterator for constant a.
Returns: An iterator referring to the first element in the container.
Complexity: Constant.
a.end()
Result: iterator; const_­iterator for constant a.
Returns: An iterator which is the past-the-end value for the container.
Complexity: Constant.
a.cbegin()
Result: const_­iterator.
Returns: const_­cast<X const&>(a).begin()
Complexity: Constant.
a.cend()
Result: const_­iterator.
Returns: const_­cast<X const&>(a).end()
Complexity: Constant.
i <=> j
Result: strong_­ordering.
Constraints: X​::​iterator meets the random access iterator requirements.
Complexity: Constant.
a == b
Preconditions: T meets the Cpp17EqualityComparable requirements.
Result: Convertible to bool.
Returns: equal(a.begin(), a.end(), b.begin(), b.end())
[Note 1:
The algorithm equal is defined in [alg.equal].
— end note]
Complexity: Constant if a.size() != b.size(), linear otherwise.
Remarks: == is an equivalence relation.
a != b
Effects: Equivalent to !(a == b).
a.swap(b)
Result: void
Effects: Exchanges the contents of a and b.
Complexity: Linear for array and constant for all other standard containers.
swap(a, b)
Effects: Equivalent to a.swap(b).
r = a
Result: X&.
Postconditions: r == a.
Complexity: Linear.
a.size()
Result: size_­type.
Returns: distance(a.begin(), a.end()), i.e. the number of elements in the container.
Complexity: Constant.
Remarks: The number of elements is defined by the rules of constructors, inserts, and erases.
a.max_size()
Result: size_­type.
Returns: distance(begin(), end()) for the largest possible container.
Complexity: Constant.
a.empty()
Result: Convertible to bool.
Returns: a.begin() == a.end()
Complexity: Constant.
Remarks: If the container is empty, then a.empty() is true.
In the expressions i == j 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.
Unless otherwise specified, all containers defined in this Clause obtain memory using an allocator (see [allocator.requirements]).
[Note 2:
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 3:
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.
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.