[container.requirements.general] (original) (raw)

23.2.2.1 Introduction [container.intro.reqmts]

In [container.requirements.general],

• X denotes a container class containing objects of type T,
• a denotes a value of type X,
• b and c denote values of type (possibly const) X,
• i and j denote values of type (possibly const) X​::​iterator,
• u denotes an identifier,
• v denotes an lvalue of type (possibly const) X or an rvalue of type const X,
• s and t denote non-const lvalues of type X, and
• rv denotes a non-const rvalue of type X.

The following exposition-only concept is used in the definition of containers:template<class R, class T> concept container-compatible-range = ranges::input_range<R> && convertible_to<ranges::range_reference_t<R>, T>;

23.2.2.2 Container requirements [container.reqmts]

A type X meets the container requirements if the following types, statements, and expressions are well-formed and have the specified semantics.

Preconditions: T is Cpp17Erasable from X(see [container.alloc.reqmts], below).

typename X::const_reference

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 ofX​::​iterator and X​::​const_iterator.

Result: An unsigned integer type that can represent any non-negative value of X​::​difference_type.

Postconditions: u.empty()

Preconditions: T is Cpp17CopyInsertable into X (see below).

Postconditions: u is equal to the value that rv had before this construction.

Complexity: Linear for array and inplace_vector and constant for all other standard containers.

Effects: All existing elements of t are either move assigned to or destroyed.

Postconditions: If t and rv do not refer to the same object,t is equal to the value that rv had before this assignment.

Effects: Destroys every element of a; any memory obtained is deallocated.

Result: iterator;const_iterator for constant b.

Returns: An iterator referring to the first element in the container.

Result: iterator;const_iterator for constant b.

Returns: An iterator which is the past-the-end value for the container.

Returns: const_cast<X const&>(b).begin()

Returns: const_cast<X const&>(b).end()

Constraints: X​::​iterator meets the random access iterator requirements.

Preconditions: T meets the Cpp17EqualityComparable requirements.

Returns: equal(c.begin(), c.end(), b.begin(), b.end())

[Note 1:

The algorithm equal is defined in [alg.equal].

— _end note_]

Complexity: Constant if c.size() != b.size(), linear otherwise.

Remarks: == is an equivalence relation.

Effects: Equivalent to !(c == b).

Effects: Exchanges the contents of t and s.

Complexity: Linear for array and inplace_vector, and constant for all other standard containers.

Effects: Equivalent to t.swap(s).

Returns: distance(c.begin(), c.end()), i.e., the number of elements in the container.

Remarks: The number of elements is defined by the rules of constructors, inserts, and erases.

Returns: distance(begin(), end()) for the largest possible container.

Returns: c.begin() == c.end()

Remarks: If the container is empty, then c.empty() is true.

In the expressionsi == j i != j i < j i <= j i >= j i > j i <=> j i - jwhere i and j denote objects of a container's iteratortype, either or both may be replaced by an object of the container'sconst_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 orpointer_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 callingallocator_traits<allocator_type>​::​select_on_container_copy_constructionon 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 aconst 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 orswap().

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 truewithin 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 and inplace_vector, shall exchange the values of a andb without invoking any move, copy, or swap operations on the individual container elements.

Any Compare, Pred, or Hash types belonging to a and b shall meet the Cpp17Swappable requirements and shall be exchanged by calling swapas described in [swappable.requirements].

Ifallocator_traits<allocator_type>​::​propagate_on_container_swap​::​value istrue, thenallocator_type shall meet the Cpp17Swappable requirements 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.

Unless otherwise specified (see [associative.reqmts.except], [unord.req.except], [deque.modifiers], [inplace.vector.modifiers], and[vector.modifiers]) all container types defined in this Clause meet the following additional requirements:

• If an exception is thrown by aninsert() or emplace()function while inserting a single element, that function has no effects.
• If an exception is thrown by apush_back(),push_front(),emplace_back(), or emplace_front()function, that function has no effects.
• Noerase(),clear(),pop_back()orpop_front()function throws an exception.
• No copy constructor or assignment operator of a returned iterator throws an exception.
• Noswap()function throws an exception.
• Noswap()function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped.
  [Note 4:
  The end() iterator does not refer to any element, so it can 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.

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 meets both of the following conditions:

• The expression declval<A&>().allocate(size_t{})is well-formed when treated as an unevaluated operand.

23.2.2.3 Reversible container requirements [container.rev.reqmts]

A type X meets the reversible container requirements ifX meets the container requirements, the iterator type of X belongs to the bidirectional or random access iterator categories ([iterator.requirements]), and the following types and expressions are well-formed and have the specified semantics.

typename X::reverse_iterator

Result: The type reverse_iterator<X​::​iterator>, an iterator type whose value type is T.

typename X::const_reverse_iterator

Result: The type reverse_iterator<X​::​const_iterator>, a constant iterator type whose value type is T.

Result: reverse_iterator;const_reverse_iterator for constant a.

Returns: reverse_iterator(end())

Result: reverse_iterator;const_reverse_iterator for constant a.

Returns: reverse_iterator(begin())

Result: const_reverse_iterator.

Returns: const_cast<X const&>(a).rbegin()

Result: const_reverse_iterator.

Returns: const_cast<X const&>(a).rend()

23.2.2.4 Optional container requirements [container.opt.reqmts]

The following operations are provided for some types of containers but not others.

Those containers for which the listed operations are provided shall implement the semantics as described unless otherwise stated.

If the iterators passed to lexicographical_compare_three_waymeet the constexpr iterator requirements ([iterator.requirements.general]) then the operations described below are implemented by constexpr functions.

Result: synth-three-way-result<X​::​value_type>.

Preconditions: Either T models three_way_comparable, or < is defined for values of type (possibly const) T and< is a total ordering relationship.

Returns: lexicographical_compare_three_way(a.begin(), a.end(), b.begin(), b.end(),
synth-three-way)

[Note 1:

The algorithm lexicographical_compare_three_wayis defined in [algorithms].

— _end note_]

23.2.2.5 Allocator-aware containers [container.alloc.reqmts]

Given an allocator type Aand given a container type X having a value_type identical to Tand 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 that denotes an lvalue of type T or const T or an rvalue of type const T, and an rvalue rv of type T, the following terms are defined.

If Xis not allocator-aware or is a specialization of basic_string, the terms below are defined as if A wereallocator<T> — no allocator object needs to be created and user specializations of allocator<T> are not instantiated:

• T is _Cpp17DefaultInsertable into Xmeans that the following expression is well-formed:allocator_traits<A>::construct(m, p)
• An element of X is default-inserted if it is initialized by evaluation of the expressionallocator_traits<A>::construct(m, p) where p is the address of the uninitialized storage for the element allocated within X.
• T is _Cpp17MoveInsertable into Xmeans 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 1:
  rv remains a valid object.
  Its state is unspecified.
  — _end note_]
• T is _Cpp17CopyInsertable into Xmeans that, in addition to T being Cpp17MoveInsertable intoX, 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.
• 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)
• T is_Cpp17Erasable from Xmeans that the following expression is well-formed:allocator_traits<A>::destroy(m, p)

[Note 2:

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 can choose a different definition.

— _end note_]

In this subclause,

• X denotes an allocator-aware container class with a value_type of T using an allocator of type A,
• u denotes a variable,
• a and b denote non-const lvalues of type X,
• c denotes an lvalue of type const 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.

A type X meets the allocator-aware container requirements if X meets the container requirements and the following types, statements, and expressions are well-formed and have the specified semantics.

typename X::allocator_type

Mandates: allocator_type​::​value_type is the same as X​::​value_type.

Preconditions: A meets the Cpp17DefaultConstructible requirements.

Postconditions: u.empty() returns true, u.get_allocator() == A().

Postconditions: u.empty() returns true, u.get_allocator() == m.

Preconditions: T is Cpp17CopyInsertable into X.

Postconditions: u == t, u.get_allocator() == m.

Postconditions: u has the same elements as rv had before this construction; the value of u.get_allocator() is the same as the value of rv.get_allocator() before this construction.

Preconditions: T is Cpp17MoveInsertable into X.

Postconditions: u has the same elements, or copies of the elements, that rv had before this construction,u.get_allocator() == m.

Complexity: Constant if m == rv.get_allocator(), otherwise linear.

Preconditions: T is Cpp17CopyInsertable into X and_Cpp17CopyAssignable_.

Postconditions: a == t is true.

Preconditions: Ifallocator_traits<allocator_type>​::​propagate_on_container_move_assignment​::​valueis false,T is Cpp17MoveInsertable into X and_Cpp17MoveAssignable_.

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.

Effects: Exchanges the contents of a and b.