[container.requirements] - C++17 → C++20

Files changed (1) hide show

tmp/tmpj47lu1pn/{from.md → to.md} +235 -202

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

@@ -16,31 +16,31 @@ linear complexity, even though the complexity of copying each contained
 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` (
-[[allocator.traits.members]]), 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 1*: 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]],
-[[tab:containers.reversible.requirements]], and
-[[tab:containers.optional.operations]] `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`.
 Those entries marked “(Note A)” or “(Note B)” have linear complexity for
 `array` and have constant complexity for all other standard containers.
-[*Note 2*: The algorithm `equal()` is defined in Clause
 [[algorithms]]. — *end note*]
 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.
@@ -58,10 +58,11 @@ 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
@@ -85,11 +86,11 @@ 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 4*: 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
@@ -123,13 +124,13 @@ 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]].
 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:
@@ -153,38 +154,40 @@ 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 that supports random access
-iterators ([[random.access.iterators]]) and whose member types
-`iterator` and `const_iterator` are contiguous iterators (
-[[iterator.requirements.general]]).
-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.
-[*Note 6*: The algorithm `lexicographical_compare()` is defined in
-Clause  [[algorithms]]. — *end note*]
 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 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:
-- `T` is *`DefaultInsertable` 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
@@ -193,71 +196,71 @@ user specializations of `allocator<T>` are not instantiated:
   allocator_traits<A>::construct(m, p)
   ```
   where `p` is the address of the uninitialized storage for the element
   allocated within `X`.
-- `T` is *`MoveInsertable` 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 7*: `rv` remains a valid object. Its state is
   unspecified — *end note*]
-- `T` is *`CopyInsertable` into `X`* means that, in addition to `T`
-  being `MoveInsertable` 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 *`EmplaceConstructible` 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 *`Erasable` from `X`* means that the following expression is
-  well-formed:
   ``` cpp
   allocator_traits<A>::destroy(m, p)
   ```
 [*Note 8*: 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*]
-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`, and `m` is a
-value of type `A`.
 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:
-- 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.
 ### Container data races <a id="container.requirements.dataraces">[[container.requirements.dataraces]]</a>
-For purposes of avoiding data races ([[res.on.data.races]]),
 implementations shall consider the following functions to be `const`:
 `begin`, `end`, `rbegin`, `rend`, `front`, `back`, `data`, `find`,
 `lower_bound`, `upper_bound`, `equal_range`, `at` and, except in
 associative or unordered associative containers, `operator[]`.
@@ -283,38 +286,43 @@ which provides limited sequence operations because it has a fixed number
 of elements. The library also provides container adaptors that make it
 easy to construct abstract data types, such as `stack`s or `queue`s, out
 of the basic sequence container kinds (or out of other kinds of sequence
 containers that the user might define).
-The sequence containers offer the programmer different complexity
-trade-offs and should be used accordingly. `vector` or `array` is the
-type of sequence container that should be used by default. `list` or
-`forward_list` should be used when there are frequent insertions and
-deletions from the middle of the sequence. `deque` is the data structure
-of choice when most insertions and deletions take place at the beginning
-or at the end of the sequence.
-In Tables  [[tab:containers.sequence.requirements]] and
-[[tab:containers.sequence.optional]], `X` denotes a sequence container
-class, `a` denotes a value of type `X` containing elements of type `T`,
-`u` denotes the name of a variable being declared, `A` denotes
-`X::allocator_type` if the *qualified-id* `X::allocator_type` is valid
-and denotes a type ([[temp.deduct]]) and `allocator<T>` if it doesn’t,
-`i` and `j` denote iterators satisfying input iterator requirements and
-refer to elements implicitly convertible to `value_type`, `[i, j)`
-denotes a valid range, `il` designates an object of type
-`initializer_list<value_type>`, `n` denotes a value of type
-`X::size_type`, `p` denotes a valid constant iterator to `a`, `q`
-denotes a valid dereferenceable constant iterator to `a`, `[q1, q2)`
-denotes a valid range of constant iterators in `a`, `t` denotes an
-lvalue or a const rvalue of `X::value_type`, and `rv` denotes a
-non-const rvalue of `X::value_type`. `Args` denotes a template parameter
-pack; `args` denotes a function parameter pack with the pattern
-`Args&&`.
 The complexities of the expressions are sequence dependent.
 The iterator returned from `a.insert(p, t)` points to the copy of `t`
 inserted into `a`.
 The iterator returned from `a.insert(p, rv)` points to the copy of `rv`
 inserted into `a`.
@@ -337,12 +345,11 @@ element exists, `a.end()` is returned.
 The iterator returned by `a.erase(q1, q2)` points to the element pointed
 to by `q2` prior to any elements being erased. If no such element
 exists, `a.end()` is returned.
-For every sequence container defined in this Clause and in Clause
-[[strings]]:
 - If the constructor
   ``` cpp
   template<class InputIterator>
     X(InputIterator first, InputIterator last,
@@ -374,32 +381,31 @@ For every sequence container defined in this Clause and in Clause
   and a type that does not qualify as an input iterator is deduced for
   that parameter, or if it has an `Allocator` template parameter and a
   type that does not qualify as an allocator is deduced for that
   parameter.
-Table  [[tab:containers.sequence.optional]] lists operations that are
-provided for some types of sequence containers but not others. An
-implementation shall provide these operations for all container types
-shown in the “container” column, and shall implement them so as to take
-amortized constant time.
 The member function `at()` provides bounds-checked access to container
 elements. `at()` throws `out_of_range` if `n >= a.size()`.
 ### Node handles <a id="container.node">[[container.node]]</a>
-#### `node_handle` overview <a id="container.node.overview">[[container.node.overview]]</a>
 A *node handle* is an object that accepts ownership of a single element
-from an associative container ([[associative.reqmts]]) or an unordered
-associative container ([[unord.req]]). It may be used to transfer that
 ownership to another container with compatible nodes. Containers with
 compatible nodes have the same node handle type. Elements may be
 transferred in either direction between container types in the same row
-of Table  [[tab:containers.node.compat]].
-**Table: Container types with compatible nodes** <a id="tab:containers.node.compat">[tab:containers.node.compat]</a>
 |                                  |                                       |
 | -------------------------------- | ------------------------------------- |
 | `map<K, T, C1, A>`               | `map<K, T, C2, A>`                    |
 | `map<K, T, C1, A>`               | `multimap<K, T, C2, A>`               |
@@ -413,122 +419,126 @@ of Table  [[tab:containers.node.compat]].
 If a node handle is not empty, then it contains an allocator that is
 equal to the allocator of the container when the element was extracted.
 If a node handle is empty, it contains no allocator.
-Class `node_handle` is for exposition only. An implementation is
-permitted to provide equivalent functionality without providing a class
-with this name.
 If a user-defined specialization of `pair` exists for
 `pair<const Key, T>` or `pair<Key, T>`, where `Key` is the container’s
 `key_type` and `T` is the container’s `mapped_type`, the behavior of
 operations involving node handles is undefined.
 ``` cpp
 template<unspecified>
- class node_handle {
 public:
- // These type declarations are described in Tables [tab:containers.associative.requirements] and [tab:HashRequirements].
   using value_type     = see below;     // not present for map containers
   using key_type       = see below;     // not present for set containers
   using mapped_type    = see below;     // not present for set containers
   using allocator_type = see below;
 private:
   using container_node_type = unspecified;
   using ator_traits = allocator_traits<allocator_type>;
- typename ator_traits::rebind_traits<container_node_type>::pointer ptr_;
   optional<allocator_type> alloc_;
 public:
-    constexpr node_handle() noexcept : ptr_(), alloc_() {}
-    ~node_handle();
-    node_handle(node_handle&&) noexcept;
-    node_handle& operator=(node_handle&&);
   value_type& value() const;            // not present for map containers
   key_type& key() const;                // not present for set containers
   mapped_type& mapped() const;          // not present for set containers
   allocator_type get_allocator() const;
   explicit operator bool() const noexcept;
- bool empty() const noexcept;
-    void swap(node_handle&)
     noexcept(ator_traits::propagate_on_container_swap::value ||
              ator_traits::is_always_equal::value);
- friend void swap(node_handle& x, node_handle& y) noexcept(noexcept(x.swap(y))) {
     x.swap(y);
   }
 };
 ```
-#### `node_handle` constructors, copy, and assignment <a id="container.node.cons">[[container.node.cons]]</a>
 ``` cpp
-node_handle(node_handle&& nh) noexcept;
 ```
-*Effects:* Constructs a *`node_handle`* object initializing `ptr_` with
 `nh.ptr_`. Move constructs `alloc_` with `nh.alloc_`. Assigns `nullptr`
 to `nh.ptr_` and assigns `nullopt` to `nh.alloc_`.
 ``` cpp
-node_handle& operator=(node_handle&& nh);
 ```
-*Requires:* Either `!alloc_`, or
-`ator_traits::propagate_on_container_move_assignment` is `true`, or
-`alloc_ == nh.alloc_`.
 *Effects:*
 - If `ptr_ != nullptr`, destroys the `value_type` subobject in the
   `container_node_type` object pointed to by `ptr_` by calling
   `ator_traits::destroy`, then deallocates `ptr_` by calling
-  `ator_traits::rebind_traits<container_node_type>::deallocate`.
 - Assigns `nh.ptr_` to `ptr_`.
-- If `!alloc` or `ator_traits::propagate_on_container_move_assignment`
- is `true`, move assigns `nh.alloc_` to `alloc_`.
 - Assigns `nullptr` to `nh.ptr_` and assigns `nullopt` to `nh.alloc_`.
 *Returns:* `*this`.
 *Throws:* Nothing.
-#### `node_handle` destructor <a id="container.node.dtor">[[container.node.dtor]]</a>
 ``` cpp
-~node_handle();
 ```
 *Effects:* If `ptr_ != nullptr`, destroys the `value_type` subobject in
 the `container_node_type` object pointed to by `ptr_` by calling
 `ator_traits::destroy`, then deallocates `ptr_` by calling
-`ator_traits::rebind_traits<container_node_type>::deallocate`.
-#### `node_handle` observers <a id="container.node.observers">[[container.node.observers]]</a>
 ``` cpp
 value_type& value() const;
 ```
-*Requires:* `empty() == false`.
 *Returns:* A reference to the `value_type` subobject in the
 `container_node_type` object pointed to by `ptr_`.
 *Throws:* Nothing.
 ``` cpp
 key_type& key() const;
 ```
-*Requires:* `empty() == false`.
 *Returns:* A non-const reference to the `key_type` member of the
 `value_type` subobject in the `container_node_type` object pointed to by
 `ptr_`.
@@ -539,22 +549,22 @@ permitted.
 ``` cpp
 mapped_type& mapped() const;
 ```
-*Requires:* `empty() == false`.
 *Returns:* A reference to the `mapped_type` member of the `value_type`
 subobject in the `container_node_type` object pointed to by `ptr_`.
 *Throws:* Nothing.
 ``` cpp
 allocator_type get_allocator() const;
 ```
-*Requires:* `empty() == false`.
 *Returns:* `*alloc_`.
 *Throws:* Nothing.
@@ -563,70 +573,75 @@ explicit operator bool() const noexcept;
 ```
 *Returns:* `ptr_ != nullptr`.
 ``` cpp
-bool empty() const noexcept;
 ```
 *Returns:* `ptr_ == nullptr`.
-#### `node_handle` modifiers <a id="container.node.modifiers">[[container.node.modifiers]]</a>
 ``` cpp
-void swap(node_handle& nh)
   noexcept(ator_traits::propagate_on_container_swap::value ||
            ator_traits::is_always_equal::value);
 ```
-*Requires:* `!alloc_`, or `!nh.alloc_`, or
-`ator_traits::propagate_on_container_swap` is `true`, or
 `alloc_ == nh.alloc_`.
 *Effects:* Calls `swap(ptr_, nh.ptr_)`. If `!alloc_`, or `!nh.alloc_`,
-or `ator_traits::propagate_on_container_swap` is `true` calls
 `swap(alloc_, nh.alloc_)`.
 ### Insert return type <a id="container.insert.return">[[container.insert.return]]</a>
 The associative containers with unique keys and the unordered containers
 with unique keys have a member function `insert` that returns a nested
 type `insert_return_type`. That return type is a specialization of the
-type specified in this subclause.
 ``` cpp
 template<class Iterator, class NodeType>
-struct INSERT_RETURN_TYPE
 {
   Iterator position;
   bool     inserted;
   NodeType node;
 };
 ```
-The name `INSERT_RETURN_TYPE` is exposition only. `INSERT_RETURN_TYPE`
-has the template parameters, data members, and special members specified
-above. It has no base classes or members other than those specified.
 ### Associative containers <a id="associative.reqmts">[[associative.reqmts]]</a>
 Associative containers provide fast retrieval of data based on keys. The
 library provides four basic kinds of associative containers: `set`,
 `multiset`, `map` and `multimap`.
 Each associative container is parameterized on `Key` and an ordering
-relation `Compare` that induces a strict weak ordering (
-[[alg.sorting]]) on elements of `Key`. In addition, `map` and `multimap`
-associate an arbitrary *mapped type* `T` with the `Key`. The object of
-type `Compare` is called the *comparison object* of a container.
 The phrase “equivalence of keys” means the equivalence relation imposed
-by the comparison and *not* the `operator==` on keys. That is, two keys
-`k1` and `k2` are considered to be equivalent if for the comparison
-object `comp`, `comp(k1, k2) == false && comp(k2, k1) == false`. For any
-two keys `k1` and `k2` in the same container, calling `comp(k1, k2)`
-shall always return the same value.
 An associative container supports *unique keys* if it may contain at
 most one element for each key. Otherwise, it supports *equivalent keys*.
 The `set` and `map` classes support unique keys; the `multiset` and
 `multimap` classes support equivalent keys. For `multiset` and
@@ -642,45 +657,44 @@ of an associative container is of the bidirectional iterator category.
 For associative containers where the value type is the same as the key
 type, both `iterator` and `const_iterator` are constant iterators. It is
 unspecified whether or not `iterator` and `const_iterator` are the same
 type.
-[*Note 1*: `iterator` and `const_iterator` have identical semantics in
 this case, and `iterator` is convertible to `const_iterator`. Users can
 avoid violating the one-definition rule by always using `const_iterator`
 in their function parameter lists. — *end note*]
 The associative containers meet all the requirements of Allocator-aware
-containers ([[container.requirements.general]]), except that for `map`
-and `multimap`, the requirements placed on `value_type` in Table
-[[tab:containers.container.requirements]] apply instead to `key_type`
-and `mapped_type`.
-[*Note 2*: For example, in some cases `key_type` and `mapped_type` are
-required to be `CopyAssignable` even though the associated `value_type`,
-`pair<const key_type, mapped_type>`, is not
-`CopyAssignable`. — *end note*]
-In Table  [[tab:containers.associative.requirements]], `X` denotes an
-associative container class, `a` denotes a value of type `X`, `a2`
-denotes a value of a type with nodes compatible with type `X` (Table
-[[tab:containers.node.compat]]), `b` denotes a possibly `const` value of
-type `X`, `u` denotes the name of a variable being declared, `a_uniq`
-denotes a value of type `X` when `X` supports unique keys, `a_eq`
-denotes a value of type `X` when `X` supports multiple keys, `a_tran`
-denotes a possibly `const` value of type `X` when the *qualified-id*
-`X::key_compare::is_transparent` is valid and denotes a type (
-[[temp.deduct]]), `i` and `j` satisfy input iterator requirements and
-refer to elements implicitly convertible to `value_type`, \[`i`, `j`)
-denotes a valid range, `p` denotes a valid constant iterator to `a`, `q`
-denotes a valid dereferenceable constant iterator to `a`, `r` denotes a
-valid dereferenceable iterator to `a`, `[q1, q2)` denotes a valid range
-of constant iterators in `a`, `il` designates an object of type
 `initializer_list<value_type>`, `t` denotes a value of type
 `X::value_type`, `k` denotes a value of type `X::key_type` and `c`
 denotes a possibly `const` value of type `X::key_compare`; `kl` is a
-value such that `a` is partitioned ([[alg.sorting]]) with respect to
 `c(r, kl)`, with `r` the key value of `e` and `e` in `a`; `ku` is a
 value such that `a` is partitioned with respect to `!c(ku, r)`; `ke` is
 a value such that `a` is partitioned with respect to `c(r, ke)` and
 `!c(ke, r)`, with `c(r, ke)` implying `!c(ke, r)`. `A` denotes the
 storage allocator used by `X`, if any, or `allocator<X::value_type>`
@@ -717,19 +731,19 @@ value_comp(*i, *j) != false
 ```
 When an associative container is constructed by passing a comparison
 object the container shall not store a pointer or reference to the
 passed object, even if that object is passed by reference. When an
-associative container is copied, either through a copy constructor or an
 assignment operator, the target container shall then use the comparison
 object from the container being copied, as if that comparison object had
 been passed to the target container in its constructor.
-The member function templates `find`, `count`, `lower_bound`,
-`upper_bound`, and `equal_range` shall not participate in overload
-resolution unless the *qualified-id* `Compare::is_transparent` is valid
-and denotes a type ([[temp.deduct]]).
 A deduction guide for an associative container shall not participate in
 overload resolution if any of the following are true:
 - It has an `InputIterator` template parameter and a type that does not
@@ -760,31 +774,31 @@ of data based on keys. The worst-case complexity for most operations is
 linear, but the average case is much faster. The library provides four
 unordered associative containers: `unordered_set`, `unordered_map`,
 `unordered_multiset`, and `unordered_multimap`.
 Unordered associative containers conform to the requirements for
-Containers ([[container.requirements]]), except that the expressions
 `a == b` and `a != b` have different semantics than for the other
 container types.
 Each unordered associative container is parameterized by `Key`, by a
-function object type `Hash` that meets the `Hash` requirements (
-[[hash.requirements]]) and acts as a hash function for argument values
-of type `Key`, and by a binary predicate `Pred` that induces an
-equivalence relation on values of type `Key`. Additionally,
-`unordered_map` and `unordered_multimap` associate an arbitrary *mapped
-type* `T` with the `Key`.
 The container’s object of type `Hash` — denoted by `hash` — is called
 the *hash function* of the container. The container’s object of type
 `Pred` — denoted by `pred` — is called the *key equality predicate* of
 the container.
-Two values `k1` and `k2` of type `Key` are considered equivalent if the
-container’s key equality predicate returns `true` when passed those
-values. If `k1` and `k2` are equivalent, the container’s hash function
-shall return the same value for both.
 [*Note 1*: Thus, when an unordered associative container is
 instantiated with a non-default `Pred` parameter it usually needs a
 non-default `Hash` parameter as well. — *end note*]
@@ -829,64 +843,78 @@ changes ordering between elements, and changes which buckets elements
 appear in, but does not invalidate pointers or references to elements.
 For `unordered_multiset` and `unordered_multimap`, rehashing preserves
 the relative ordering of equivalent elements.
 The unordered associative containers meet all the requirements of
-Allocator-aware containers ([[container.requirements.general]]), except
 that for `unordered_map` and `unordered_multimap`, the requirements
-placed on `value_type` in Table
-[[tab:containers.container.requirements]] apply instead to `key_type`
-and `mapped_type`.
 [*Note 3*: For example, `key_type` and `mapped_type` are sometimes
-required to be `CopyAssignable` even though the associated `value_type`,
-`pair<const key_type, mapped_type>`, is not
-`CopyAssignable`. — *end note*]
-In Table  [[tab:HashRequirements]]: `X` denotes an unordered associative
-container class, `a` denotes a value of type `X`, `a2` denotes a value
-of a type with nodes compatible with type `X` (Table
-[[tab:containers.node.compat]]), `b` denotes a possibly const value of
-type `X`, `a_uniq` denotes a value of type `X` when `X` supports unique
-keys, `a_eq` denotes a value of type `X` when `X` supports equivalent
-keys, `i` and `j` denote input iterators that refer to `value_type`,
-`[i, j)` denotes a valid range, `p` and `q2` denote valid constant
-iterators to `a`, `q` and `q1` denote valid dereferenceable constant
-iterators to `a`, `r` denotes a valid dereferenceable iterator to `a`,
-`[q1, q2)` denotes a valid range in `a`, `il` denotes a value of type
-`initializer_list<value_type>`, `t` denotes a value of type
-`X::value_type`, `k` denotes a value of type `key_type`, `hf` denotes a
-possibly const value of type `hasher`, `eq` denotes a possibly const
-value of type `key_equal`, `n` denotes a value of type `size_type`, `z`
-denotes a value of type `float`, and `nh` denotes a non-const rvalue of
-type `X::node_type`.
 Two unordered containers `a` and `b` compare equal if
 `a.size() == b.size()` and, for every equivalent-key group \[`Ea1`,
 `Ea2`) obtained from `a.equal_range(Ea1)`, there exists an
 equivalent-key group \[`Eb1`, `Eb2`) obtained from `b.equal_range(Ea1)`,
 such that `is_permutation(Ea1, Ea2, Eb1, Eb2)` returns `true`. For
 `unordered_set` and `unordered_map`, the complexity of `operator==`
 (i.e., the number of calls to the `==` operator of the `value_type`, to
 the predicate returned by `key_eq()`, and to the hasher returned by
 `hash_function()`) is proportional to N in the average case and to N² in
-the worst case, where N is a.size(). For `unordered_multiset` and
 `unordered_multimap`, the complexity of `operator==` is proportional to
 $\sum E_i^2$ in the average case and to N² in the worst case, where N is
 `a.size()`, and Eᵢ is the size of the iᵗʰ equivalent-key group in `a`.
 However, if the respective elements of each corresponding pair of
 equivalent-key groups Eaᵢ and Ebᵢ are arranged in the same order (as is
 commonly the case, e.g., if `a` and `b` are unmodified copies of the
 same container), then the average-case complexity for
 `unordered_multiset` and `unordered_multimap` becomes proportional to N
 (but worst-case complexity remains 𝑂(N^2), e.g., for a pathologically
 bad hash function). The behavior of a program that uses `operator==` or
-`operator!=` on unordered containers is undefined unless the `Hash` and
-`Pred` function objects respectively have the same behavior for both
-containers and the equality comparison function for `Key` is a
-refinement[^1] of the partition into equivalent-key groups produced by
-`Pred`.
 The iterator types `iterator` and `const_iterator` of an unordered
 associative container are of at least the forward iterator category. For
 unordered associative containers where the key type and value type are
 the same, both `iterator` and `const_iterator` are constant iterators.
@@ -909,10 +937,15 @@ pointers and references to the removed element remain valid. However,
 accessing the element through such pointers and references while the
 element is owned by a `node_type` is undefined behavior. References and
 pointers to an element obtained while it is owned by a `node_type` are
 invalidated if the element is successfully inserted.
 A deduction guide for an unordered associative container shall not
 participate in overload resolution if any of the following are true:
 - It has an `InputIterator` template parameter and a type that does not
   qualify as an input iterator is deduced for that parameter.

 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`
+[[allocator.traits.members]], 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 1*: 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:container.req]], [[tab:container.rev.req]], and
+[[tab:container.opt]] `X` denotes a container class containing objects
+of type `T`, `a` and `b` denote values of type `X`, `i` and `j` denote
+values of type (possibly const) `X::iterator`, `u` denotes an
+identifier, `r` denotes a non-const value of type `X`, and `rv` denotes
+a non-const rvalue of type `X`.
 Those entries marked “(Note A)” or “(Note B)” have linear complexity for
 `array` and have constant complexity for all other standard containers.
+[*Note 2*: The algorithm `equal()` is defined in
 [[algorithms]]. — *end note*]
 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.
 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
 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 4*: 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
 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 meets the additional requirements
+in [[container.rev.req]].
 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:
 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]].
+[[container.opt]] 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
+[[container.opt]] unless otherwise stated. If the iterators passed to
+`lexicographical_compare_three_way` meet the constexpr iterator
+requirements [[iterator.requirements.general]] then the operations
+described in [[container.opt]] are implemented by constexpr functions.
+[*Note 6*: The algorithm `lexicographical_compare_three_way` is defined
+in [[algorithms]]. — *end note*]
 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 [[container.alloc.req]].
 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:
+- `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
   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 7*: `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 8*: 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*]
+In [[container.alloc.req]], `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`.
 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.
 ### Container data races <a id="container.requirements.dataraces">[[container.requirements.dataraces]]</a>
+For purposes of avoiding data races [[res.on.data.races]],
 implementations shall consider the following functions to be `const`:
 `begin`, `end`, `rbegin`, `rend`, `front`, `back`, `data`, `find`,
 `lower_bound`, `upper_bound`, `equal_range`, `at` and, except in
 associative or unordered associative containers, `operator[]`.
 of elements. The library also provides container adaptors that make it
 easy to construct abstract data types, such as `stack`s or `queue`s, out
 of the basic sequence container kinds (or out of other kinds of sequence
 containers that the user might define).
+[*Note 1*: The sequence containers offer the programmer different
+complexity trade-offs and should be used accordingly. `vector` is the
+type of sequence container that should be used by default. `array`
+should be used when the container has a fixed size known during
+translation. `list` or `forward_list` should be used when there are
+frequent insertions and deletions from the middle of the sequence.
+`deque` is the data structure of choice when most insertions and
+deletions take place at the beginning or at the end of the sequence.
+When choosing a container, remember `vector` is best; leave a comment to
+explain if you choose from the rest! — *end note*]
+In Tables  [[tab:container.seq.req]] and [[tab:container.seq.opt]], `X`
+denotes a sequence container class, `a` denotes a value of type `X`
+containing elements of type `T`, `u` denotes the name of a variable
+being declared, `A` denotes `X::allocator_type` if the *qualified-id*
+`X::allocator_type` is valid and denotes a type [[temp.deduct]] and
+`allocator<T>` if it doesn’t, `i` and `j` denote iterators that meet the
+*Cpp17InputIterator* requirements and refer to elements implicitly
+convertible to `value_type`, `[i, j)` denotes a valid range, `il`
+designates an object of type `initializer_list<value_type>`, `n` denotes
+a value of type `X::size_type`, `p` denotes a valid constant iterator to
+`a`, `q` denotes a valid dereferenceable constant iterator to `a`,
+`[q1, q2)` denotes a valid range of constant iterators in `a`, `t`
+denotes an lvalue or a const rvalue of `X::value_type`, and `rv` denotes
+a non-const rvalue of `X::value_type`. `Args` denotes a template
+parameter pack; `args` denotes a function parameter pack with the
+pattern `Args&&`.
 The complexities of the expressions are sequence dependent.
+[*Note 2*: `args` may directly or indirectly refer to a value in
+`a`. — *end note*]
 The iterator returned from `a.insert(p, t)` points to the copy of `t`
 inserted into `a`.
 The iterator returned from `a.insert(p, rv)` points to the copy of `rv`
 inserted into `a`.
 The iterator returned by `a.erase(q1, q2)` points to the element pointed
 to by `q2` prior to any elements being erased. If no such element
 exists, `a.end()` is returned.
+For every sequence container defined in this Clause and in [[strings]]:
 - If the constructor
   ``` cpp
   template<class InputIterator>
     X(InputIterator first, InputIterator last,
   and a type that does not qualify as an input iterator is deduced for
   that parameter, or if it has an `Allocator` template parameter and a
   type that does not qualify as an allocator is deduced for that
   parameter.
+[[container.seq.opt]] lists operations that are provided for some types
+of sequence containers but not others. An implementation shall provide
+these operations for all container types shown in the “container”
+column, and shall implement them so as to take amortized constant time.
 The member function `at()` provides bounds-checked access to container
 elements. `at()` throws `out_of_range` if `n >= a.size()`.
 ### Node handles <a id="container.node">[[container.node]]</a>
+#### Overview <a id="container.node.overview">[[container.node.overview]]</a>
 A *node handle* is an object that accepts ownership of a single element
+from an associative container [[associative.reqmts]] or an unordered
+associative container [[unord.req]]. It may be used to transfer that
 ownership to another container with compatible nodes. Containers with
 compatible nodes have the same node handle type. Elements may be
 transferred in either direction between container types in the same row
+of [[container.node.compat]].
+**Table: Container types with compatible nodes** <a id="container.node.compat">[container.node.compat]</a>
 |                                  |                                       |
 | -------------------------------- | ------------------------------------- |
 | `map<K, T, C1, A>`               | `map<K, T, C2, A>`                    |
 | `map<K, T, C1, A>`               | `multimap<K, T, C2, A>`               |
 If a node handle is not empty, then it contains an allocator that is
 equal to the allocator of the container when the element was extracted.
 If a node handle is empty, it contains no allocator.
+Class *`node-handle`* is for exposition only.
 If a user-defined specialization of `pair` exists for
 `pair<const Key, T>` or `pair<Key, T>`, where `Key` is the container’s
 `key_type` and `T` is the container’s `mapped_type`, the behavior of
 operations involving node handles is undefined.
 ``` cpp
 template<unspecified>
+class node-handle {
 public:
+ // These type declarations are described in Tables [tab:container.assoc.req] and [tab:container.hash.req].
   using value_type     = see below;     // not present for map containers
   using key_type       = see below;     // not present for set containers
   using mapped_type    = see below;     // not present for set containers
   using allocator_type = see below;
 private:
   using container_node_type = unspecified;
   using ator_traits = allocator_traits<allocator_type>;
+ typename ator_traits::template rebind_traits<container_node_type>::pointer ptr_;
   optional<allocator_type> alloc_;
 public:
+  // [container.node.cons], constructors, copy, and assignment
+  constexpr node-handle() noexcept : ptr_(), alloc_() {}
+  node-handle(node-handle&&) noexcept;
+  node-handle& operator=(node-handle&&);
+  // [container.node.dtor], destructor
+  ~node-handle();
+  // [container.node.observers], observers
   value_type& value() const;            // not present for map containers
   key_type& key() const;                // not present for set containers
   mapped_type& mapped() const;          // not present for set containers
   allocator_type get_allocator() const;
   explicit operator bool() const noexcept;
+  [[nodiscard]] bool empty() const noexcept;
+  // [container.node.modifiers], modifiers
+  void swap(node-handle&)
     noexcept(ator_traits::propagate_on_container_swap::value ||
              ator_traits::is_always_equal::value);
+ friend void swap(node-handle& x, node-handle& y) noexcept(noexcept(x.swap(y))) {
     x.swap(y);
   }
 };
 ```
+#### Constructors, copy, and assignment <a id="container.node.cons">[[container.node.cons]]</a>
 ``` cpp
+node-handle(node-handle&& nh) noexcept;
 ```
+*Effects:* Constructs a *node-handle* object initializing `ptr_` with
 `nh.ptr_`. Move constructs `alloc_` with `nh.alloc_`. Assigns `nullptr`
 to `nh.ptr_` and assigns `nullopt` to `nh.alloc_`.
 ``` cpp
+node-handle& operator=(node-handle&& nh);
 ```
+*Preconditions:* Either `!alloc_`, or
+`ator_traits::propagate_on_container_move_assignment::value` is `true`,
+or `alloc_ == nh.alloc_`.
 *Effects:*
 - If `ptr_ != nullptr`, destroys the `value_type` subobject in the
   `container_node_type` object pointed to by `ptr_` by calling
   `ator_traits::destroy`, then deallocates `ptr_` by calling
+  `ator_traits::template rebind_traits<container_node_type>::deallocate`.
 - Assigns `nh.ptr_` to `ptr_`.
+- If `!alloc` or
+  `ator_traits::propagate_on_container_move_assignment::value` is
+  `true`, move assigns `nh.alloc_` to `alloc_`.
 - Assigns `nullptr` to `nh.ptr_` and assigns `nullopt` to `nh.alloc_`.
 *Returns:* `*this`.
 *Throws:* Nothing.
+#### Destructor <a id="container.node.dtor">[[container.node.dtor]]</a>
 ``` cpp
+~node-handle();
 ```
 *Effects:* If `ptr_ != nullptr`, destroys the `value_type` subobject in
 the `container_node_type` object pointed to by `ptr_` by calling
 `ator_traits::destroy`, then deallocates `ptr_` by calling
+`ator_traits::template rebind_traits<container_node_type>::deallocate`.
+#### Observers <a id="container.node.observers">[[container.node.observers]]</a>
 ``` cpp
 value_type& value() const;
 ```
+*Preconditions:* `empty() == false`.
 *Returns:* A reference to the `value_type` subobject in the
 `container_node_type` object pointed to by `ptr_`.
 *Throws:* Nothing.
 ``` cpp
 key_type& key() const;
 ```
+*Preconditions:* `empty() == false`.
 *Returns:* A non-const reference to the `key_type` member of the
 `value_type` subobject in the `container_node_type` object pointed to by
 `ptr_`.
 ``` cpp
 mapped_type& mapped() const;
 ```
+*Preconditions:* `empty() == false`.
 *Returns:* A reference to the `mapped_type` member of the `value_type`
 subobject in the `container_node_type` object pointed to by `ptr_`.
 *Throws:* Nothing.
 ``` cpp
 allocator_type get_allocator() const;
 ```
+*Preconditions:* `empty() == false`.
 *Returns:* `*alloc_`.
 *Throws:* Nothing.
 ```
 *Returns:* `ptr_ != nullptr`.
 ``` cpp
+[[nodiscard]] bool empty() const noexcept;
 ```
 *Returns:* `ptr_ == nullptr`.
+#### Modifiers <a id="container.node.modifiers">[[container.node.modifiers]]</a>
 ``` cpp
+void swap(node-handle& nh)
   noexcept(ator_traits::propagate_on_container_swap::value ||
            ator_traits::is_always_equal::value);
 ```
+*Preconditions:* `!alloc_`, or `!nh.alloc_`, or
+`ator_traits::propagate_on_container_swap::value` is `true`, or
 `alloc_ == nh.alloc_`.
 *Effects:* Calls `swap(ptr_, nh.ptr_)`. If `!alloc_`, or `!nh.alloc_`,
+or `ator_traits::propagate_on_container_swap::value` is `true` calls
 `swap(alloc_, nh.alloc_)`.
 ### Insert return type <a id="container.insert.return">[[container.insert.return]]</a>
 The associative containers with unique keys and the unordered containers
 with unique keys have a member function `insert` that returns a nested
 type `insert_return_type`. That return type is a specialization of the
+template specified in this subclause.
 ``` cpp
 template<class Iterator, class NodeType>
+struct insert-return-type
 {
   Iterator position;
   bool     inserted;
   NodeType node;
 };
 ```
+The name *`insert-return-type`* is exposition only.
+*`insert-return-type`* has the template parameters, data members, and
+special members specified above. It has no base classes or members other
+than those specified.
 ### Associative containers <a id="associative.reqmts">[[associative.reqmts]]</a>
 Associative containers provide fast retrieval of data based on keys. The
 library provides four basic kinds of associative containers: `set`,
 `multiset`, `map` and `multimap`.
 Each associative container is parameterized on `Key` and an ordering
+relation `Compare` that induces a strict weak ordering [[alg.sorting]]
+on elements of `Key`. In addition, `map` and `multimap` associate an
+arbitrary *mapped type* `T` with the `Key`. The object of type `Compare`
+is called the *comparison object* of a container.
 The phrase “equivalence of keys” means the equivalence relation imposed
+by the comparison object. That is, two keys `k1` and `k2` are considered
+to be equivalent if for the comparison object `comp`,
+`comp(k1, k2) == false && comp(k2, k1) == false`.
+[*Note 1*: This is not necessarily the same as the result of
+`k1 == k2`. — *end note*]
+For any two keys `k1` and `k2` in the same container, calling
+`comp(k1, k2)` shall always return the same value.
 An associative container supports *unique keys* if it may contain at
 most one element for each key. Otherwise, it supports *equivalent keys*.
 The `set` and `map` classes support unique keys; the `multiset` and
 `multimap` classes support equivalent keys. For `multiset` and
 For associative containers where the value type is the same as the key
 type, both `iterator` and `const_iterator` are constant iterators. It is
 unspecified whether or not `iterator` and `const_iterator` are the same
 type.
+[*Note 2*: `iterator` and `const_iterator` have identical semantics in
 this case, and `iterator` is convertible to `const_iterator`. Users can
 avoid violating the one-definition rule by always using `const_iterator`
 in their function parameter lists. — *end note*]
 The associative containers meet all the requirements of Allocator-aware
+containers [[container.requirements.general]], except that for `map` and
+`multimap`, the requirements placed on `value_type` in
+[[container.alloc.req]] apply instead to `key_type` and `mapped_type`.
+[*Note 3*: For example, in some cases `key_type` and `mapped_type` are
+required to be *Cpp17CopyAssignable* even though the associated
+`value_type`, `pair<const key_type, mapped_type>`, is not
+*Cpp17CopyAssignable*. — *end note*]
+In [[container.assoc.req]], `X` denotes an associative container class,
+`a` denotes a value of type `X`, `a2` denotes a value of a type with
+nodes compatible with type `X` ([[container.node.compat]]), `b` denotes
+a possibly `const` value of type `X`, `u` denotes the name of a variable
+being declared, `a_uniq` denotes a value of type `X` when `X` supports
+unique keys, `a_eq` denotes a value of type `X` when `X` supports
+multiple keys, `a_tran` denotes a possibly `const` value of type `X`
+when the *qualified-id* `X::key_compare::is_transparent` is valid and
+denotes a type [[temp.deduct]], `i` and `j` meet the
+*Cpp17InputIterator* requirements and refer to elements implicitly
+convertible to `value_type`, \[`i`, `j`) denotes a valid range, `p`
+denotes a valid constant iterator to `a`, `q` denotes a valid
+dereferenceable constant iterator to `a`, `r` denotes a valid
+dereferenceable iterator to `a`, `[q1, q2)` denotes a valid range of
+constant iterators in `a`, `il` designates an object of type
 `initializer_list<value_type>`, `t` denotes a value of type
 `X::value_type`, `k` denotes a value of type `X::key_type` and `c`
 denotes a possibly `const` value of type `X::key_compare`; `kl` is a
+value such that `a` is partitioned [[alg.sorting]] with respect to
 `c(r, kl)`, with `r` the key value of `e` and `e` in `a`; `ku` is a
 value such that `a` is partitioned with respect to `!c(ku, r)`; `ke` is
 a value such that `a` is partitioned with respect to `c(r, ke)` and
 `!c(ke, r)`, with `c(r, ke)` implying `!c(ke, r)`. `A` denotes the
 storage allocator used by `X`, if any, or `allocator<X::value_type>`
 ```
 When an associative container is constructed by passing a comparison
 object the container shall not store a pointer or reference to the
 passed object, even if that object is passed by reference. When an
+associative container is copied, through either a copy constructor or an
 assignment operator, the target container shall then use the comparison
 object from the container being copied, as if that comparison object had
 been passed to the target container in its constructor.
+The member function templates `find`, `count`, `contains`,
+`lower_bound`, `upper_bound`, and `equal_range` shall not participate in
+overload resolution unless the *qualified-id* `Compare::is_transparent`
+is valid and denotes a type [[temp.deduct]].
 A deduction guide for an associative container shall not participate in
 overload resolution if any of the following are true:
 - It has an `InputIterator` template parameter and a type that does not
 linear, but the average case is much faster. The library provides four
 unordered associative containers: `unordered_set`, `unordered_map`,
 `unordered_multiset`, and `unordered_multimap`.
 Unordered associative containers conform to the requirements for
+Containers [[container.requirements]], except that the expressions
 `a == b` and `a != b` have different semantics than for the other
 container types.
 Each unordered associative container is parameterized by `Key`, by a
+function object type `Hash` that meets the *Cpp17Hash* requirements
+[[hash.requirements]] and acts as a hash function for argument values of
+type `Key`, and by a binary predicate `Pred` that induces an equivalence
+relation on values of type `Key`. Additionally, `unordered_map` and
+`unordered_multimap` associate an arbitrary *mapped type* `T` with the
+`Key`.
 The container’s object of type `Hash` — denoted by `hash` — is called
 the *hash function* of the container. The container’s object of type
 `Pred` — denoted by `pred` — is called the *key equality predicate* of
 the container.
+Two values `k1` and `k2` are considered equivalent if the container’s
+key equality predicate `pred(k1, k2)` is valid and returns `true` when
+passed those values. If `k1` and `k2` are equivalent, the container’s
+hash function shall return the same value for both.
 [*Note 1*: Thus, when an unordered associative container is
 instantiated with a non-default `Pred` parameter it usually needs a
 non-default `Hash` parameter as well. — *end note*]
 appear in, but does not invalidate pointers or references to elements.
 For `unordered_multiset` and `unordered_multimap`, rehashing preserves
 the relative ordering of equivalent elements.
 The unordered associative containers meet all the requirements of
+Allocator-aware containers [[container.requirements.general]], except
 that for `unordered_map` and `unordered_multimap`, the requirements
+placed on `value_type` in [[container.alloc.req]] apply instead to
+`key_type` and `mapped_type`.
 [*Note 3*: For example, `key_type` and `mapped_type` are sometimes
+required to be *Cpp17CopyAssignable* even though the associated
+`value_type`, `pair<const key_type, mapped_type>`, is not
+*Cpp17CopyAssignable*. — *end note*]
+In [[container.hash.req]]:
+- `X` denotes an unordered associative container class,
+- `a` denotes a value of type `X`,
+- `a2` denotes a value of a type with nodes compatible with type `X` (
+  [[container.node.compat]]),
+- `b` denotes a possibly const value of type `X`,
+- `a_uniq` denotes a value of type `X` when `X` supports unique keys,
+- `a_eq` denotes a value of type `X` when `X` supports equivalent keys,
+- `a_tran` denotes a possibly const value of type `X` when the
+  *qualified-id*s `X::key_equal::is_transparent` and
+ `X::hasher::is_transparent` are both valid and denote types
+  [[temp.deduct]],
+- `i` and `j` denote input iterators that refer to `value_type`,
+- `[i, j)` denotes a valid range,
+- `p` and `q2` denote valid constant iterators to `a`,
+- `q` and `q1` denote valid dereferenceable constant iterators to `a`,
+- `r` denotes a valid dereferenceable iterator to `a`,
+- `[q1, q2)` denotes a valid range in `a`,
+- `il` denotes a value of type `initializer_list<value_type>`,
+- `t` denotes a value of type `X::value_type`,
+- `k` denotes a value of type `key_type`,
+- `hf` denotes a possibly const value of type `hasher`,
+- `eq` denotes a possibly const value of type `key_equal`,
+- `ke` is a value such that
+  - `eq(r1, ke) == eq(ke, r1)`
+  - `hf(r1) == hf(ke)` if `eq(r1, ke)` is `true`, and
+  - `(eq(r1, ke) && eq(r1, r2)) == eq(r2, ke)`
+  where `r1` and `r2` are keys of elements in `a_tran`,
+- `n` denotes a value of type `size_type`,
+- `z` denotes a value of type `float`, and
+- `nh` denotes a non-const rvalue of type `X::node_type`.
 Two unordered containers `a` and `b` compare equal if
 `a.size() == b.size()` and, for every equivalent-key group \[`Ea1`,
 `Ea2`) obtained from `a.equal_range(Ea1)`, there exists an
 equivalent-key group \[`Eb1`, `Eb2`) obtained from `b.equal_range(Ea1)`,
 such that `is_permutation(Ea1, Ea2, Eb1, Eb2)` returns `true`. For
 `unordered_set` and `unordered_map`, the complexity of `operator==`
 (i.e., the number of calls to the `==` operator of the `value_type`, to
 the predicate returned by `key_eq()`, and to the hasher returned by
 `hash_function()`) is proportional to N in the average case and to N² in
+the worst case, where N is `a.size()`. For `unordered_multiset` and
 `unordered_multimap`, the complexity of `operator==` is proportional to
 $\sum E_i^2$ in the average case and to N² in the worst case, where N is
 `a.size()`, and Eᵢ is the size of the iᵗʰ equivalent-key group in `a`.
 However, if the respective elements of each corresponding pair of
 equivalent-key groups Eaᵢ and Ebᵢ are arranged in the same order (as is
 commonly the case, e.g., if `a` and `b` are unmodified copies of the
 same container), then the average-case complexity for
 `unordered_multiset` and `unordered_multimap` becomes proportional to N
 (but worst-case complexity remains 𝑂(N^2), e.g., for a pathologically
 bad hash function). The behavior of a program that uses `operator==` or
+`operator!=` on unordered containers is undefined unless the `Pred`
+function object has the same behavior for both containers and the
+equality comparison function for `Key` is a refinement[^1] of the
+partition into equivalent-key groups produced by `Pred`.
 The iterator types `iterator` and `const_iterator` of an unordered
 associative container are of at least the forward iterator category. For
 unordered associative containers where the key type and value type are
 the same, both `iterator` and `const_iterator` are constant iterators.
 accessing the element through such pointers and references while the
 element is owned by a `node_type` is undefined behavior. References and
 pointers to an element obtained while it is owned by a `node_type` are
 invalidated if the element is successfully inserted.
+The member function templates `find`, `count`, `equal_range`, and
+`contains` shall not participate in overload resolution unless the
+*qualified-id*s `Pred::is_transparent` and `Hash::is_transparent` are
+both valid and denote types [[temp.deduct]].
 A deduction guide for an unordered associative container shall not
 participate in overload resolution if any of the following are true:
 - It has an `InputIterator` template parameter and a type that does not
   qualify as an input iterator is deduced for that parameter.

Diff to HTML by rtfpessoa