[container.gen.reqmts] - C++20 → C++23

Files changed (1) hide show

tmp/tmprhu2dvzw/{from.md → to.md} +677 -0

tmp/tmprhu2dvzw/{from.md → to.md} RENAMED Viewed

	@@ -0,0 +1,677 @@

+### General containers <a id="container.gen.reqmts">[[container.gen.reqmts]]</a>
+#### General <a id="container.requirements.general">[[container.requirements.general]]</a>
+In subclause [[container.gen.reqmts]],
+- `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:
+``` cpp
+template<class R, class T>
+concept container-compatible-range =    // exposition only
+  ranges::input_range<R> && convertible_to<ranges::range_reference_t<R>, T>;
+```
+#### Containers <a id="container.reqmts">[[container.reqmts]]</a>
+A type `X` meets the *container* requirements if the following types,
+statements, and expressions are well-formed and have the specified
+semantics.
+``` cpp
+typename X::value_type
+```
+*Result:* `T`
+*Preconditions:* `T` is *Cpp17Erasable* from `X`
+(see  [[container.alloc.reqmts]], below).
+``` cpp
+typename X::reference
+```
+*Result:* `T&`
+``` cpp
+typename X::const_reference
+```
+*Result:* `const T&`
+``` cpp
+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`.
+``` cpp
+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`.
+``` cpp
+typename X::difference_type
+```
+*Result:* A signed integer type, identical to the difference type of
+`X::iterator` and `X::const_iterator`.
+``` cpp
+typename X::size_type
+```
+*Result:* An unsigned integer type that can represent any non-negative
+value of `X::difference_type`.
+``` cpp
+X u;
+X u = X();
+```
+*Ensures:* `u.empty()`
+*Complexity:* Constant.
+``` cpp
+X u(v);
+X u = v;
+```
+*Preconditions:* `T` is *Cpp17CopyInsertable* into `X` (see below).
+*Ensures:* `u == v`.
+*Complexity:* Linear.
+``` cpp
+X u(rv);
+X u = rv;
+```
+*Ensures:* `u` is equal to the value that `rv` had before this
+construction.
+*Complexity:* Linear for `array` and constant for all other standard
+containers.
+``` cpp
+t = v;
+```
+*Result:* `X&`.
+*Ensures:* `t == v`.
+*Complexity:* Linear.
+``` cpp
+t = rv
+```
+*Result:* `X&`.
+*Effects:* All existing elements of `t` are either move assigned to or
+destroyed.
+*Ensures:* If `t` and `rv` do not refer to the same object, `t` is equal
+to the value that `rv` had before this assignment.
+*Complexity:* Linear.
+``` cpp
+a.~X()
+```
+*Result:* `void`.
+*Effects:* Destroys every element of `a`; any memory obtained is
+deallocated.
+*Complexity:* Linear.
+``` cpp
+b.begin()
+```
+*Result:* `iterator`; `const_iterator` for constant `b`.
+*Returns:* An iterator referring to the first element in the container.
+*Complexity:* Constant.
+``` cpp
+b.end()
+```
+*Result:* `iterator`; `const_iterator` for constant `b`.
+*Returns:* An iterator which is the past-the-end value for the
+container.
+*Complexity:* Constant.
+``` cpp
+b.cbegin()
+```
+*Result:* `const_iterator`.
+*Returns:* `const_cast<X const&>(b).begin()`
+*Complexity:* Constant.
+``` cpp
+b.cend()
+```
+*Result:* `const_iterator`.
+*Returns:* `const_cast<X const&>(b).end()`
+*Complexity:* Constant.
+``` cpp
+i <=> j
+```
+*Result:* `strong_ordering`.
+*Constraints:* `X::iterator` meets the random access iterator
+requirements.
+*Complexity:* Constant.
+``` cpp
+c == b
+```
+*Preconditions:* `T` meets the *Cpp17EqualityComparable* requirements.
+*Result:* `bool`.
+*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.
+``` cpp
+c != b
+```
+*Effects:* Equivalent to `!(c == b)`.
+``` cpp
+t.swap(s)
+```
+*Result:* `void`.
+*Effects:* Exchanges the contents of `t` and `s`.
+*Complexity:* Linear for `array` and constant for all other standard
+containers.
+``` cpp
+swap(t, s)
+```
+*Effects:* Equivalent to `t.swap(s)`.
+``` cpp
+c.size()
+```
+*Result:* `size_type`.
+*Returns:* `distance(c.begin(), c.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.
+``` cpp
+c.max_size()
+```
+*Result:* `size_type`.
+*Returns:* `distance(begin(), end())` for the largest possible
+container.
+*Complexity:* Constant.
+``` cpp
+c.empty()
+```
+*Result:* `bool`.
+*Returns:* `c.begin() == c.end()`
+*Complexity:* Constant.
+*Remarks:* If the container is empty, then `c.empty()` is `true`.
+In the expressions
+``` cpp
+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 1*: 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 2*: 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. Any `Compare`, `Pred`, or `Hash` types
+belonging to `a` and `b` shall meet the *Cpp17Swappable* requirements
+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 `allocator_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]], 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()`, `push_front()`,
+  `emplace_back()`, or `emplace_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 3*: 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.
+A *contiguous container* is a container whose member types `iterator`
+and `const_iterator` meet the *Cpp17RandomAccessIterator* requirements
+[[random.access.iterators]] and model `contiguous_iterator`
+[[iterator.concept.contiguous]].
+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 *qualified-id* `A::value_type` is valid and denotes a type
+  [[temp.deduct]].
+- The expression `declval<A&>().allocate(size_t{})` is well-formed when
+  treated as an unevaluated operand.
+#### Reversible container requirements <a id="container.rev.reqmts">[[container.rev.reqmts]]</a>
+A type `X` meets the *reversible container* requirements if `X` 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.
+``` cpp
+typename X::reverse_iterator
+```
+*Result:* The type `reverse_iterator<X::iterator>`, an iterator type
+whose value type is `T`.
+``` cpp
+typename X::const_reverse_iterator
+```
+*Result:* The type `reverse_iterator<X::const_iterator>`, a constant
+iterator type whose value type is `T`.
+``` cpp
+a.rbegin()
+```
+*Result:* `reverse_iterator`; `const_reverse_iterator` for constant `a`.
+*Returns:* `reverse_iterator(end())`
+*Complexity:* Constant.
+``` cpp
+a.rend()
+```
+*Result:* `reverse_iterator`; `const_reverse_iterator` for constant `a`.
+*Returns:* `reverse_iterator(begin())`
+*Complexity:* Constant.
+``` cpp
+a.crbegin()
+```
+*Result:* `const_reverse_iterator`.
+*Returns:* `const_cast<X const&>(a).rbegin()`
+*Complexity:* Constant.
+``` cpp
+a.crend()
+```
+*Result:* `const_reverse_iterator`.
+*Returns:* `const_cast<X const&>(a).rend()`
+*Complexity:* Constant.
+#### Optional container requirements <a id="container.opt.reqmts">[[container.opt.reqmts]]</a>
+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_way`
+meet the constexpr iterator requirements
+[[iterator.requirements.general]] then the operations described below
+are implemented by constexpr functions.
+``` cpp
+a <=> b
+```
+*Result:* *`synth-three-way-result`*`<X::value_type>`.
+*Preconditions:* Either `<=>` is defined for values of type (possibly
+const) `T`, 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_way` is defined
+in [[algorithms]]. — *end note*]
+*Complexity:* Linear.
+#### Allocator-aware containers <a id="container.alloc.reqmts">[[container.alloc.reqmts]]</a>
+All of the containers defined in [[containers]] and in  [[basic.string]]
+except `array` meet the additional requirements of an
+*allocator-aware container*, as described below.
+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 `T` or
+`const T`, and an rvalue `rv` of type `T`, the following terms are
+defined. If `X` is not allocator-aware or is a specialization of
+`basic_string`, 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:
+- `T` is **Cpp17DefaultInsertable* into `X`* means that the following
+  expression is well-formed:
+  ``` cpp
+  allocator_traits<A>::construct(m, p)
+  ```
+- An element of `X` is *default-inserted* if it is initialized by
+  evaluation of the expression
+  ``` cpp
+  allocator_traits<A>::construct(m, p)
+  ```
+  where `p` is the address of the uninitialized storage for the element
+  allocated within `X`.
+- `T` is **Cpp17MoveInsertable* into `X`* means that the following
+  expression is well-formed:
+  ``` cpp
+  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 `X`* means that, in addition to `T`
+  being *Cpp17MoveInsertable* into `X`, the following expression is
+  well-formed:
+  ``` cpp
+  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:
+  ``` cpp
+  allocator_traits<A>::construct(m, p, args)
+  ```
+- `T` is **Cpp17Erasable* from `X`* means that the following expression
+  is well-formed:
+  ``` cpp
+  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.
+``` cpp
+typename X::allocator_type
+```
+*Result:* `A`
+*Mandates:* `allocator_type::value_type` is the same as `X::value_type`.
+``` cpp
+c.get_allocator()
+```
+*Result:* `A`
+*Complexity:* Constant.
+``` cpp
+X u;
+X u = X();
+```
+*Preconditions:* `A` meets the *Cpp17DefaultConstructible* requirements.
+*Ensures:* `u.empty()` returns `true`, `u.get_allocator() == A()`.
+*Complexity:* Constant.
+``` cpp
+X u(m);
+```
+*Ensures:* `u.empty()` returns `true`, `u.get_allocator() == m`.
+*Complexity:* Constant.
+``` cpp
+X u(t, m);
+```
+*Preconditions:* `T` is *Cpp17CopyInsertable* into `X`.
+*Ensures:* `u == t`, `u.get_allocator() == m`
+*Complexity:* Linear.
+``` cpp
+X u(rv);
+```
+*Ensures:* `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.
+*Complexity:* Constant.
+``` cpp
+X u(rv, m);
+```
+*Preconditions:* `T` is *Cpp17MoveInsertable* into `X`.
+*Ensures:* `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.
+``` cpp
+a = t
+```
+*Result:* `X&`.
+*Preconditions:* `T` is *Cpp17CopyInsertable* into `X` and
+*Cpp17CopyAssignable*.
+*Ensures:* `a == t` is `true`.
+*Complexity:* Linear.
+``` cpp
+a = rv
+```
+*Result:* `X&`.
+*Preconditions:* If
+`allocator_traits<allocator_type>::propagate_on_container_move_assignment::value`
+is `false`, `T` is *Cpp17MoveInsertable* into `X` and
+*Cpp17MoveAssignable*.
+*Effects:* All existing elements of `a` are either move assigned to or
+destroyed.
+*Ensures:* 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.
+``` cpp
+a.swap(b)
+```
+*Result:* `void`
+*Effects:* Exchanges the contents of `a` and `b`.
+*Complexity:* Constant.

Diff to HTML by rtfpessoa