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

Files changed (1) hide show

tmp/tmp0xvk2od7/{from.md → to.md} +2700 -226

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

@@ -1,8 +1,8 @@
-## Container requirements <a id="container.requirements">[[container.requirements]]</a>
-### General container requirements <a id="container.requirements.general">[[container.requirements.general]]</a>
 Containers are objects that store other objects. They control allocation
 and deallocation of these objects through constructors, destructors,
 insert and erase operations.
@@ -11,47 +11,299 @@ terms of the number of operations on the contained objects.
 [*Example 1*: The copy constructor of type `vector<vector<int>>` has
 linear complexity, even though the complexity of copying each contained
 `vector<int>` is itself linear. — *end example*]
-For the components affected by this subclause that declare an
-`allocator_type`, objects stored in these components shall be
-constructed using the 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.
-`begin()`
-returns an iterator referring to the first element in the container.
-`end()` returns an iterator which is the past-the-end value for the
-container. If the container is empty, then `begin() == end()`.
 In the expressions
 ``` cpp
 i == j
@@ -67,14 +319,14 @@ 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 3*: 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*]
@@ -85,72 +337,69 @@ 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 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
 allocator is replaced. The allocator may be replaced only via assignment
 or `swap()`. Allocator replacement is performed by copy assignment, move
 assignment, or swapping of the allocator only if
-`allocator_traits<allocator_type>::propagate_on_container_copy_assignment::value`,
-`allocator_traits<allocator_type>::propagate_on_container_move_assignment::value`,
   or
-`allocator_traits<allocator_type>::propagate_on_container_swap::value`
 is `true` within the implementation of the corresponding container
 operation. In all container types defined in this Clause, the member
 `get_allocator()` returns a copy of the allocator used to construct the
 container or, if that allocator has been replaced, a copy of the most
 recent replacement.
 The expression `a.swap(b)`, for containers `a` and `b` of a standard
 container type other than `array`, shall exchange the values of `a` and
 `b` without invoking any move, copy, or swap operations on the
-individual container elements. Lvalues of any `Compare`, `Pred`, or
-`Hash` types belonging to `a` and `b` shall be swappable and shall be
-exchanged by calling `swap` as described in  [[swappable.requirements]].
-If
 `allocator_traits<allocator_type>::propagate_on_container_swap::value`
-is `true`, then lvalues of type `allocator_type` shall be swappable and
-the allocators of `a` and `b` shall also be exchanged by calling `swap`
-as described in  [[swappable.requirements]]. Otherwise, the allocators
-shall not be swapped, and the behavior is undefined unless
-`a.get_allocator() == b.get_allocator()`. Every iterator referring to an
-element in one container before the swap shall refer to the same element
-in the other container after the swap. It is unspecified whether an
-iterator with value `a.end()` before the swap will have value `b.end()`
-after the swap.
-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:
-- 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 5*: The `end()` iterator does not refer to any element, so it
- may be invalidated. — *end note*]
 Unless otherwise specified (either explicitly or by defining a function
 in terms of other functions), invoking a container member function or
 passing a container as an argument to a library function shall not
 invalidate iterators to, or change the values of, objects within that
@@ -159,33 +408,129 @@ 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)
@@ -205,11 +550,11 @@ user specializations of `allocator<T>` are not instantiated:
   ```
   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
@@ -228,35 +573,138 @@ user specializations of `allocator<T>` are not instantiated:
   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`:
@@ -270,84 +718,324 @@ elements in the same container, excepting `vector<bool>`, are modified
 concurrently.
 [*Note 1*: For a `vector<int> x` with a size greater than one,
 `x[1] = 5` and `*x.begin() = 10` can be executed concurrently without a
 data race, but `x[0] = 5` and `*x.begin() = 10` executed concurrently
-may result in a data race. As an exception to the general rule, for a
-`vector<bool> y`, `y[0] = true` may race with
 `y[1] = true`. — *end note*]
 ### Sequence containers <a id="sequence.reqmts">[[sequence.reqmts]]</a>
 A sequence container organizes a finite set of objects, all of the same
 type, into a strictly linear arrangement. The library provides four
 basic kinds of sequence containers: `vector`, `forward_list`, `list`,
 and `deque`. In addition, `array` is provided as a sequence container
 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).
 [*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 from `a.insert(p, n, t)` points to the copy of the
-first element inserted into `a`, or `p` if `n == 0`.
-The iterator returned from `a.insert(p, i, j)` points to the copy of the
-first element inserted into `a`, or `p` if `i == j`.
-The iterator returned from `a.insert(p, il)` points to the copy of the
-first element inserted into `a`, or `p` if `il` is empty.
-The iterator returned from `a.emplace(p, args)` points to the new
-element constructed from `args` into `a`.
-The iterator returned from `a.erase(q)` points to the element
-immediately following `q` prior to the element being erased. If no such
-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 [[strings]]:
 - If the constructor
   ``` cpp
@@ -381,17 +1069,202 @@ For every sequence container defined in this Clause and in [[strings]]:
   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>
@@ -430,22 +1303,23 @@ 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;
@@ -618,13 +1492,19 @@ The name *`insert-return-type`* is exposition only.
 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`
@@ -662,50 +1542,729 @@ 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>`
-otherwise, `m` denotes an allocator of a type convertible to `A`, and
-`nh` denotes a non-const rvalue of type `X::node_type`.
-The `insert` and `emplace` members shall not affect the validity of
-iterators and references to the container, and the `erase` members shall
-invalidate only iterators and references to the erased elements.
 The `extract` members invalidate only iterators to the removed element;
 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
@@ -737,13 +2296,18 @@ 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
@@ -767,10 +2331,12 @@ For associative containers, no `swap` function throws an exception
 unless that exception is thrown by the swap of the container’s `Compare`
 object (if any).
 ### Unordered associative containers <a id="unord.req">[[unord.req]]</a>
 Unordered associative containers provide an ability for fast retrieval
 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`.
@@ -842,54 +2408,956 @@ per bucket is kept below a bound. Rehashing invalidates iterators,
 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 [[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)`,
@@ -909,42 +3377,48 @@ 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.
-The `insert` and `emplace` members shall not affect the validity of
-references to container elements, but may invalidate all iterators to
-the container. The `erase` members shall invalidate only iterators and
-references to the erased elements, and preserve the relative order of
-the elements that are not erased.
-The `insert` and `emplace` members shall not affect the validity of
-iterators if `(N+n) <= z * B`, where `N` is the number of elements in
-the container prior to the insert operation, `n` is the number of
-elements inserted, `B` is the container’s bucket count, and `z` is the
-container’s maximum load factor.
 The `extract` members invalidate only iterators to the removed element,
 and preserve the relative order of the elements that are not erased;
 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.
-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

+## Requirements <a id="container.requirements">[[container.requirements]]</a>
+### Preamble <a id="container.requirements.pre">[[container.requirements.pre]]</a>
 Containers are objects that store other objects. They control allocation
 and deallocation of these objects through constructors, destructors,
 insert and erase operations.
 [*Example 1*: The copy constructor of type `vector<vector<int>>` has
 linear complexity, even though the complexity of copying each contained
 `vector<int>` is itself linear. — *end example*]
+Allocator-aware containers [[container.alloc.reqmts]] other than
+`basic_string` construct elements using the function
 `allocator_traits<allocator_type>::rebind_traits<U>::{}construct` and
+destroy elements 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 would
 need to construct nodes containing aligned buffers and call `construct`
 to place the element into the buffer. — *end note*]
+### 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
 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*]
 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
 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)
   ```
   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
   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.
 ### 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`:
 concurrently.
 [*Note 1*: For a `vector<int> x` with a size greater than one,
 `x[1] = 5` and `*x.begin() = 10` can be executed concurrently without a
 data race, but `x[0] = 5` and `*x.begin() = 10` executed concurrently
+can result in a data race. As an exception to the general rule, for a
+`vector<bool> y`, `y[0] = true` can race with
 `y[1] = true`. — *end note*]
 ### Sequence containers <a id="sequence.reqmts">[[sequence.reqmts]]</a>
 A sequence container organizes a finite set of objects, all of the same
 type, into a strictly linear arrangement. The library provides four
 basic kinds of sequence containers: `vector`, `forward_list`, `list`,
 and `deque`. In addition, `array` is provided as a sequence container
 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, `queue`s,
+`flat_map`s, `flat_multimap`s, `flat_set`s, or `flat_multiset`s, out of
+the basic sequence container kinds (or out of other program-defined
+sequence containers).
 [*Note 1*: The sequence containers offer the programmer different
+complexity trade-offs. `vector` is appropriate in most circumstances.
+`array` has a fixed size known during translation. `list` or
+`forward_list` support frequent insertions and deletions from the middle
+of the sequence. `deque` supports efficient insertions and deletions
+taking 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 this subclause,
+- `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,
+- `rg` denotes a value of a type `R` that models
+ `container-compatible-range<T>`,
+- `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.
+A type `X` meets the *sequence container* requirements if `X` meets the
+container requirements and the following statements and expressions are
+well-formed and have the specified semantics.
+``` cpp
+X u(n, t);
+```
+*Preconditions:* `T` is *Cpp17CopyInsertable* into `X`.
+*Effects:* Constructs a sequence container with `n` copies of `t`.
+*Ensures:* `distance(u.begin(), u.end()) == n` is `true`.
+``` cpp
+X u(i, j);
+```
+*Preconditions:* `T` is *Cpp17EmplaceConstructible* into `X` from `*i`.
+For `vector`, if the iterator does not meet the *Cpp17ForwardIterator*
+requirements [[forward.iterators]], `T` is also *Cpp17MoveInsertable*
+into `X`.
+*Effects:* Constructs a sequence container equal to the range `[i, j)`.
+Each iterator in the range \[`i`, `j`) is dereferenced exactly once.
+*Ensures:* `distance(u.begin(), u.end()) == distance(i, j)` is `true`.
+``` cpp
+X(from_range, rg)
+```
+*Preconditions:* `T` is *Cpp17EmplaceConstructible* into `X` from
+`*ranges::begin(rg)`. For `vector`, if `R` models neither
+`ranges::sized_range` nor `ranges::forward_range`, `T` is also
+*Cpp17MoveInsertable* into `X`.
+*Effects:* Constructs a sequence container equal to the range `rg`. Each
+iterator in the range `rg` is dereferenced exactly once.
+*Ensures:* `distance(begin(), end()) == ranges::distance(rg)` is `true`.
+``` cpp
+X(il)
+```
+*Effects:* Equivalent to `X(il.begin(), il.end())`.
+``` cpp
+a = il
+```
+*Result:* `X&`.
+*Preconditions:* `T` is *Cpp17CopyInsertable* into `X` and
+*Cpp17CopyAssignable*.
+*Effects:* Assigns the range \[`il.begin()`, `il.end()`) into `a`. All
+existing elements of `a` are either assigned to or destroyed.
+*Returns:* `*this`.
+``` cpp
+a.emplace(p, args)
+```
+*Result:* `iterator`.
+*Preconditions:* `T` is *Cpp17EmplaceConstructible* into `X` from
+`args`. For `vector` and `deque`, `T` is also *Cpp17MoveInsertable* into
+`X` and *Cpp17MoveAssignable*.
+*Effects:* Inserts an object of type `T` constructed with
+`std::forward<Args>(args)...` before `p`.
+[*Note 1*: `args` can directly or indirectly refer to a value in
 `a`. — *end note*]
+*Returns:* An iterator that points to the new element constructed from
+`args` into `a`.
+``` cpp
+a.insert(p, t)
+```
+*Result:* `iterator`.
+*Preconditions:* `T` is *Cpp17CopyInsertable* into `X`. For `vector` and
+`deque`, `T` is also *Cpp17CopyAssignable*.
+*Effects:* Inserts a copy of `t` before `p`.
+*Returns:* An iterator that points to the copy of `t` inserted into `a`.
+``` cpp
+a.insert(p, rv)
+```
+*Result:* `iterator`.
+*Preconditions:* `T` is *Cpp17MoveInsertable* into `X`. For `vector` and
+`deque`, `T` is also *Cpp17MoveAssignable*.
+*Effects:* Inserts a copy of `rv` before `p`.
+*Returns:* An iterator that points to the copy of `rv` inserted into
+`a`.
+``` cpp
+a.insert(p, n, t)
+```
+*Result:* `iterator`.
+*Preconditions:* `T` is *Cpp17CopyInsertable* into `X` and
+*Cpp17CopyAssignable*.
+*Effects:* Inserts `n` copies of `t` before `p`.
+*Returns:* An iterator that points to the copy of the first element
+inserted into `a`, or `p` if `n == 0`.
+``` cpp
+a.insert(p, i, j)
+```
+*Result:* `iterator`.
+*Preconditions:* `T` is *Cpp17EmplaceConstructible* into `X` from `*i`.
+For `vector` and `deque`, `T` is also *Cpp17MoveInsertable* into `X`,
+and `T` meets the *Cpp17MoveConstructible*, *Cpp17MoveAssignable*, and
+*Cpp17Swappable*[[swappable.requirements]] requirements. Neither `i` nor
+`j` are iterators into `a`.
+*Effects:* Inserts copies of elements in `[i, j)` before `p`. Each
+iterator in the range \[`i`, `j`) shall be dereferenced exactly once.
+*Returns:* An iterator that points to the copy of the first element
+inserted into `a`, or `p` if `i == j`.
+``` cpp
+a.insert_range(p, rg)
+```
+*Result:* `iterator`.
+*Preconditions:* `T` is *Cpp17EmplaceConstructible* into `X` from
+`*ranges::begin(rg)`. For `vector` and `deque`, `T` is also
+*Cpp17MoveInsertable* into `X`, and `T` meets the
+*Cpp17MoveConstructible*, *Cpp17MoveAssignable*, and
+*Cpp17Swappable*[[swappable.requirements]] requirements. `rg` and `a` do
+not overlap.
+*Effects:* Inserts copies of elements in `rg` before `p`. Each iterator
+in the range `rg` is dereferenced exactly once.
+*Returns:* An iterator that points to the copy of the first element
+inserted into `a`, or `p` if `rg` is empty.
+``` cpp
+a.insert(p, il)
+```
+*Effects:* Equivalent to `a.insert(p, il.begin(), il.end())`.
+``` cpp
+a.erase(q)
+```
+*Result:* `iterator`.
+*Preconditions:* For `vector` and `deque`, `T` is *Cpp17MoveAssignable*.
+*Effects:* Erases the element pointed to by `q`.
+*Returns:* An iterator that points to the element immediately following
+`q` prior to the element being erased. If no such element exists,
+`a.end()` is returned.
+``` cpp
+a.erase(q1, q2)
+```
+*Result:* `iterator`.
+*Preconditions:* For `vector` and `deque`, `T` is *Cpp17MoveAssignable*.
+*Effects:* Erases the elements in the range `[q1, q2)`.
+*Returns:* An iterator that points to the element pointed to by `q2`
+prior to any elements being erased. If no such element exists, `a.end()`
+is returned.
+``` cpp
+a.clear()
+```
+*Result:* `void`
+*Effects:* Destroys all elements in `a`. Invalidates all references,
+pointers, and iterators referring to the elements of `a` and may
+invalidate the past-the-end iterator.
+*Ensures:* `a.empty()` is `true`.
+*Complexity:* Linear.
+``` cpp
+a.assign(i, j)
+```
+*Result:* `void`
+*Preconditions:* `T` is *Cpp17EmplaceConstructible* into `X` from `*i`
+and assignable from `*i`. For `vector`, if the iterator does not meet
+the forward iterator requirements [[forward.iterators]], `T` is also
+*Cpp17MoveInsertable* into `X`. Neither `i` nor `j` are iterators into
+`a`.
+*Effects:* Replaces elements in `a` with a copy of `[i, j)`. Invalidates
+all references, pointers and iterators referring to the elements of `a`.
+For `vector` and `deque`, also invalidates the past-the-end iterator.
+Each iterator in the range \[`i`, `j`) is dereferenced exactly once.
+``` cpp
+a.assign_range(rg)
+```
+*Result:* `void`
+*Mandates:* `assignable_from<T&, ranges::range_reference_t<R>>` is
+modeled.
+*Preconditions:* `T` is *Cpp17EmplaceConstructible* into `X` from
+`*ranges::begin(rg)`. For `vector`, if `R` models neither
+`ranges::sized_range` nor `ranges::forward_range`, `T` is also
+*Cpp17MoveInsertable* into `X`. `rg` and `a` do not overlap.
+*Effects:* Replaces elements in `a` with a copy of each element in `rg`.
+Invalidates all references, pointers, and iterators referring to the
+elements of `a`. For `vector` and `deque`, also invalidates the
+past-the-end iterator. Each iterator in the range `rg` is dereferenced
+exactly once.
+``` cpp
+a.assign(il)
+```
+*Effects:* Equivalent to `a.assign(il.begin(), il.end())`.
+``` cpp
+a.assign(n, t)
+```
+*Result:* `void`
+*Preconditions:* `T` is *Cpp17CopyInsertable* into `X` and
+*Cpp17CopyAssignable*. `t` is not a reference into `a`.
+*Effects:* Replaces elements in `a` with `n` copies of `t`. Invalidates
+all references, pointers and iterators referring to the elements of `a`.
+For `vector` and `deque`, also invalidates the past-the-end iterator.
 For every sequence container defined in this Clause and in [[strings]]:
 - If the constructor
   ``` cpp
   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.
+The following operations are provided for some types of sequence
+containers but not others. Operations other than `prepend_range` and
+`append_range` are implemented so as to take amortized constant time.
+``` cpp
+a.front()
+```
+*Result:* `reference; const_reference` for constant `a`.
+*Returns:* `*a.begin()`
+*Remarks:* Required for `basic_string`, `array`, `deque`,
+`forward_list`, `list`, and `vector`.
+``` cpp
+a.back()
+```
+*Result:* `reference; const_reference` for constant `a`.
+*Effects:* Equivalent to:
+``` cpp
+auto tmp = a.end();
+--tmp;
+return *tmp;
+```
+*Remarks:* Required for `basic_string`, `array`, `deque`, `list`, and
+`vector`.
+``` cpp
+a.emplace_front(args)
+```
+*Result:* `reference`
+*Preconditions:* `T` is *Cpp17EmplaceConstructible* into `X` from
+`args`.
+*Effects:* Prepends an object of type `T` constructed with
+`std::forward<Args>(args)...`.
+*Returns:* `a.front()`.
+*Remarks:* Required for `deque`, `forward_list`, and `list`.
+``` cpp
+a.emplace_back(args)
+```
+*Result:* `reference`
+*Preconditions:* `T` is *Cpp17EmplaceConstructible* into `X` from
+`args`. For `vector`, `T` is also *Cpp17MoveInsertable* into `X`.
+*Effects:* Appends an object of type `T` constructed with
+`std::forward<Args>(args)...`.
+*Returns:* `a.back()`.
+*Remarks:* Required for `deque`, `list`, and `vector`.
+``` cpp
+a.push_front(t)
+```
+*Result:* `void`
+*Preconditions:* `T` is *Cpp17CopyInsertable* into `X`.
+*Effects:* Prepends a copy of `t`.
+*Remarks:* Required for `deque`, `forward_list`, and `list`.
+``` cpp
+a.push_front(rv)
+```
+*Result:* `void`
+*Preconditions:* `T` is *Cpp17MoveInsertable* into `X`.
+*Effects:* Prepends a copy of `rv`.
+*Remarks:* Required for `deque`, `forward_list`, and `list`.
+``` cpp
+a.prepend_range(rg)
+```
+*Result:* `void`
+*Preconditions:* `T` is *Cpp17EmplaceConstructible* into `X` from
+`*ranges::begin(rg)`. For `deque`, `T` is also *Cpp17MoveInsertable*
+into `X`, and `T` meets the *Cpp17MoveConstructible*,
+*Cpp17MoveAssignable*, and *Cpp17Swappable*[[swappable.requirements]]
+requirements.
+*Effects:* Inserts copies of elements in `rg` before `begin()`. Each
+iterator in the range `rg` is dereferenced exactly once.
+[*Note 2*: The order of elements in `rg` is not
+reversed. — *end note*]
+*Remarks:* Required for `deque`, `forward_list`, and `list`.
+``` cpp
+a.push_back(t)
+```
+*Result:* `void`
+*Preconditions:* `T` is *Cpp17CopyInsertable* into `X`.
+*Effects:* Appends a copy of `t`.
+*Remarks:* Required for `basic_string`, `deque`, `list`, and `vector`.
+``` cpp
+a.push_back(rv)
+```
+*Result:* `void`
+*Preconditions:* `T` is *Cpp17MoveInsertable* into `X`.
+*Effects:* Appends a copy of `rv`.
+*Remarks:* Required for `basic_string`, `deque`, `list`, and `vector`.
+``` cpp
+a.append_range(rg)
+```
+*Result:* `void`
+*Preconditions:* `T` is *Cpp17EmplaceConstructible* into `X` from
+`*ranges::begin(rg)`. For `vector`, `T` is also *Cpp17MoveInsertable*
+into `X`.
+*Effects:* Inserts copies of elements in `rg` before `end()`. Each
+iterator in the range `rg` is dereferenced exactly once.
+*Remarks:* Required for `deque`, `list`, and `vector`.
+``` cpp
+a.pop_front()
+```
+*Result:* `void`
+*Preconditions:* `a.empty()` is `false`.
+*Effects:* Destroys the first element.
+*Remarks:* Required for `deque`, `forward_list`, and `list`.
+``` cpp
+a.pop_back()
+```
+*Result:* `void`
+*Preconditions:* `a.empty()` is `false`.
+*Effects:* Destroys the last element.
+*Remarks:* Required for `basic_string`, `deque`, `list`, and `vector`.
+``` cpp
+a[n]
+```
+*Result:* `reference; const_reference` for constant `a`
+*Returns:* `*(a.begin() + n)`
+*Remarks:* Required for `basic_string`, `array`, `deque`, and `vector`.
+``` cpp
+a.at(n)
+```
+*Result:* `reference; const_reference` for constant `a`
+*Returns:* `*(a.begin() + n)`
+*Throws:* `out_of_range` if `n >= a.size()`.
+*Remarks:* Required for `basic_string`, `array`, `deque`, and `vector`.
 ### Node handles <a id="container.node">[[container.node]]</a>
 #### Overview <a id="container.node.overview">[[container.node.overview]]</a>
 ``` cpp
 template<unspecified>
 class node-handle {
 public:
+  // These type declarations are described in [associative.reqmts] and [unord.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;                  // exposition only
+  using ator_traits = allocator_traits<allocator_type>;     // exposition only
+  typename ator_traits::template
+    rebind_traits<container_node_type>::pointer ptr_;       // exposition only
+  optional<allocator_type> alloc_;                          // exposition only
 public:
   // [container.node.cons], constructors, copy, and assignment
   constexpr node-handle() noexcept : ptr_(), alloc_() {}
   node-handle(node-handle&&) noexcept;
 special members specified above. It has no base classes or members other
 than those specified.
 ### Associative containers <a id="associative.reqmts">[[associative.reqmts]]</a>
+#### General <a id="associative.reqmts.general">[[associative.reqmts.general]]</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`. The library also provides container
+adaptors that make it easy to construct abstract data types, such as
+`flat_map`s, `flat_multimap`s, `flat_set`s, or `flat_multiset`s, out of
+the basic sequence container kinds (or out of other program-defined
+sequence containers).
 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`
 [*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*]
+In this subclause,
+- `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 value or type `X` or `const 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 value of type `X` or `const 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,
+- `rg` denotes a value of a type `R` that models
+  `container-compatible-range<value_type>`,
+- `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 value of type `X::key_compare` or
+  `const X::key_compare`;
+- `kl` is a value such that `a` is partitioned [[alg.sorting]] with
+  respect to `c(x, kl)`, with `x` the key value of `e` and `e` in `a`;
+- `ku` is a value such that `a` is partitioned with respect to
+  `!c(ku, x)`, with `x` the key value of `e` and `e` in `a`;
+- `ke` is a value such that `a` is partitioned with respect to
+  `c(x, ke)` and `!c(ke, x)`, with `c(x, ke)` implying `!c(ke, x)` and
+  with `x` the key value of `e` and `e` in `a`;
+- `kx` is a value such that
+  - `a` is partitioned with respect to `c(x, kx)` and `!c(kx, x)`, with
+    `c(x, kx)` implying `!c(kx, x)` and with `x` the key value of `e`
+    and `e` in `a`, and
+  - `kx` is not convertible to either `iterator` or `const_iterator`;
+    and
+- `A` denotes the storage allocator used by `X`, if any, or
+  `allocator<X::value_type>` otherwise,
+- `m` denotes an allocator of a type convertible to `A`, and `nh`
+  denotes a non-const rvalue of type `X::node_type`.
+A type `X` meets the *associative container* requirements if `X` meets
+all the requirements of an allocator-aware container
+[[container.requirements.general]] and the following types, statements,
+and expressions are well-formed and have the specified semantics, except
+that for `map` and `multimap`, the requirements placed on `value_type`
+in [[container.alloc.reqmts]] 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*]
+``` cpp
+typename X::key_type
+```
+*Result:* `Key`.
+``` cpp
+typename X::mapped_type
+```
+*Result:* `T`.
+*Remarks:* For `map` and `multimap` only.
+``` cpp
+typename X::value_type
+```
+*Result:* `Key` for `set` and `multiset` only; `pair<const Key, T>` for
+`map` and `multimap` only.
+*Preconditions:* `X::value_type` is *Cpp17Erasable* from `X`.
+``` cpp
+typename X::key_compare
+```
+*Result:* `Compare`.
+*Preconditions:* `key_compare` is *Cpp17CopyConstructible*.
+``` cpp
+typename X::value_compare
+```
+*Result:* A binary predicate type. It is the same as `key_compare` for
+`set` and `multiset`; is an ordering relation on pairs induced by the
+first component (i.e., `Key`) for `map` and `multimap`.
+``` cpp
+typename X::node_type
+```
+*Result:* A specialization of the *node-handle* class
+template [[container.node]], such that the public nested types are the
+same types as the corresponding types in `X`.
+``` cpp
+X(c)
+```
+*Effects:* Constructs an empty container. Uses a copy of `c` as a
+comparison object.
+*Complexity:* Constant.
+``` cpp
+X u = X();
+X u;
+```
+*Preconditions:* `key_compare` meets the *Cpp17DefaultConstructible*
+requirements.
+*Effects:* Constructs an empty container. Uses `Compare()` as a
+comparison object.
+*Complexity:* Constant.
+``` cpp
+X(i, j, c)
+```
+*Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `X`
+from `*i`.
+*Effects:* Constructs an empty container and inserts elements from the
+range \[`i`, `j`) into it; uses `c` as a comparison object.
+*Complexity:* N log N in general, where N has the value
+`distance(i, j)`; linear if \[`i`, `j`) is sorted with respect to
+`value_comp()`.
+``` cpp
+X(i, j)
+```
+*Preconditions:* `key_compare` meets the *Cpp17DefaultConstructible*
+requirements. `value_type` is *Cpp17EmplaceConstructible* into `X` from
+`*i`.
+*Effects:* Constructs an empty container and inserts elements from the
+range \[`i`, `j`) into it; uses `Compare()` as a comparison object.
+*Complexity:* N log N in general, where N has the value
+`distance(i, j)`; linear if \[`i`, `j`) is sorted with respect to
+`value_comp()`.
+``` cpp
+X(from_range, rg, c)
+```
+*Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `X`
+from `*ranges::begin(rg)`.
+*Effects:* Constructs an empty container and inserts each element from
+`rg` into it. Uses `c` as the comparison object.
+*Complexity:* N log N in general, where N has the value
+`ranges::distance(rg)`; linear if `rg` is sorted with respect to
+`value_comp()`.
+``` cpp
+X(from_range, rg)
+```
+*Preconditions:* `key_compare` meets the *Cpp17DefaultConstructible*
+requirements. `value_type` is *Cpp17EmplaceConstructible* into `X` from
+`*ranges::begin(rg)`.
+*Effects:* Constructs an empty container and inserts each element from
+`rg` into it. Uses `Compare()` as the comparison object.
+*Complexity:* Same as `X(from_range, rg, c)`.
+``` cpp
+X(il, c)
+```
+*Effects:* Equivalent to `X(il.begin(), il.end(), c)`.
+``` cpp
+X(il)
+```
+*Effects:* Equivalent to `X(il.begin(), il.end())`.
+``` cpp
+a = il
+```
+*Result:* `X&`
+*Preconditions:* `value_type` is *Cpp17CopyInsertable* into `X` and
+*Cpp17CopyAssignable*.
+*Effects:* Assigns the range \[`il.begin()`, `il.end()`) into `a`. All
+existing elements of `a` are either assigned to or destroyed.
+*Complexity:* N log N in general, where N has the value
+`il.size() + a.size()`; linear if \[`il.begin()`, `il.end()`) is sorted
+with respect to `value_comp()`.
+``` cpp
+b.key_comp()
+```
+*Result:* `X::key_compare`
+*Returns:* The comparison object out of which `b` was constructed.
+*Complexity:* Constant.
+``` cpp
+b.value_comp()
+```
+*Result:* `X::value_compare`
+*Returns:* An object of `value_compare` constructed out of the
+comparison object.
+*Complexity:* Constant.
+``` cpp
+a_uniq.emplace(args)
+```
+*Result:* `pair<iterator, bool>`
+*Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `X`
+from `args`.
+*Effects:* Inserts a `value_type` object `t` constructed with
+`std::forward<Args>(args)...` if and only if there is no element in the
+container with key equivalent to the key of `t`.
+*Returns:* The `bool` component of the returned pair is `true` if and
+only if the insertion takes place, and the iterator component of the
+pair points to the element with key equivalent to the key of `t`.
+*Complexity:* Logarithmic.
+``` cpp
+a_eq.emplace(args)
+```
+*Result:* `iterator`
+*Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `X`
+from `args`.
+*Effects:* Inserts a `value_type` object `t` constructed with
+`std::forward<Args>(args)...`. If a range containing elements equivalent
+to `t` exists in `a_eq`, `t` is inserted at the end of that range.
+*Returns:* An iterator pointing to the newly inserted element.
+*Complexity:* Logarithmic.
+``` cpp
+a.emplace_hint(p, args)
+```
+*Result:* `iterator`
+*Effects:* Equivalent to `a.emplace(std::forward<Args>(args)...)`,
+except that the element is inserted as close as possible to the position
+just prior to `p`.
+*Returns:* An iterator pointing to the element with the key equivalent
+to the newly inserted element.
+*Complexity:* Logarithmic in general, but amortized constant if the
+element is inserted right before `p`.
+``` cpp
+a_uniq.insert(t)
+```
+*Result:* `pair<iterator, bool>`
+*Preconditions:* If `t` is a non-const rvalue, `value_type` is
+*Cpp17MoveInsertable* into `X`; otherwise, `value_type` is
+*Cpp17CopyInsertable* into `X`.
+*Effects:* Inserts `t` if and only if there is no element in the
+container with key equivalent to the key of `t`.
+*Returns:* The `bool` component of the returned pair is `true` if and
+only if the insertion takes place, and the `iterator` component of the
+pair points to the element with key equivalent to the key of `t`.
+*Complexity:* Logarithmic.
+``` cpp
+a_eq.insert(t)
+```
+*Result:* `iterator`
+*Preconditions:* If `t` is a non-const rvalue, `value_type` is
+*Cpp17MoveInsertable* into `X`; otherwise, `value_type` is
+*Cpp17CopyInsertable* into `X`.
+*Effects:* Inserts `t` and returns the iterator pointing to the newly
+inserted element. If a range containing elements equivalent to `t`
+exists in `a_eq`, `t` is inserted at the end of that range.
+*Complexity:* Logarithmic.
+``` cpp
+a.insert(p, t)
+```
+*Result:* `iterator`
+*Preconditions:* If `t` is a non-const rvalue, `value_type` is
+*Cpp17MoveInsertable* into `X`; otherwise, `value_type` is
+*Cpp17CopyInsertable* into `X`.
+*Effects:* Inserts `t` if and only if there is no element with key
+equivalent to the key of `t` in containers with unique keys; always
+inserts `t` in containers with equivalent keys. `t` is inserted as close
+as possible to the position just prior to `p`.
+*Returns:* An iterator pointing to the element with key equivalent to
+the key of `t`.
+*Complexity:* Logarithmic in general, but amortized constant if `t` is
+inserted right before `p`.
+``` cpp
+a.insert(i, j)
+```
+*Result:* `void`
+*Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `X`
+from `*i`. Neither `i` nor `j` are iterators into `a`.
+*Effects:* Inserts each element from the range \[`i`, `j`) if and only
+if there is no element with key equivalent to the key of that element in
+containers with unique keys; always inserts that element in containers
+with equivalent keys.
+*Complexity:* N log (`a.size()` + N), where N has the value
+`distance(i, j)`.
+``` cpp
+a.insert_range(rg)
+```
+*Result:* `void`
+*Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `X`
+from `*ranges::begin(rg)`. `rg` and `a` do not overlap.
+*Effects:* Inserts each element from `rg` if and only if there is no
+element with key equivalent to the key of that element in containers
+with unique keys; always inserts that element in containers with
+equivalent keys.
+*Complexity:* N log (`a.size()` + N), where N has the value
+`ranges::distance(rg)`.
+``` cpp
+a.insert(il)
+```
+*Effects:* Equivalent to `a.insert(il.begin(), il.end())`.
+``` cpp
+a_uniq.insert(nh)
+```
+*Result:* `insert_return_type`
+*Preconditions:* `nh` is empty or
+`a_uniq.get_allocator() == nh.get_allocator()` is `true`.
+*Effects:* If `nh` is empty, has no effect. Otherwise, inserts the
+element owned by `nh` if and only if there is no element in the
+container with a key equivalent to `nh.key()`.
+*Returns:* If `nh` is empty, `inserted` is `false`, `position` is
+`end()`, and `node` is empty. Otherwise if the insertion took place,
+`inserted` is `true`, `position` points to the inserted element, and
+`node` is empty; if the insertion failed, `inserted` is `false`, `node`
+has the previous value of `nh`, and `position` points to an element with
+a key equivalent to `nh.key()`.
+*Complexity:* Logarithmic.
+``` cpp
+a_eq.insert(nh)
+```
+*Result:* `iterator`
+*Preconditions:* `nh` is empty or
+`a_eq.get_allocator() == nh.get_allocator()` is `true`.
+*Effects:* If `nh` is empty, has no effect and returns `a_eq.end()`.
+Otherwise, inserts the element owned by `nh` and returns an iterator
+pointing to the newly inserted element. If a range containing elements
+with keys equivalent to `nh.key()` exists in `a_eq`, the element is
+inserted at the end of that range.
+*Ensures:* `nh` is empty.
+*Complexity:* Logarithmic.
+``` cpp
+a.insert(p, nh)
+```
+*Result:* `iterator`
+*Preconditions:* `nh` is empty or
+`a.get_allocator() == nh.get_allocator()` is `true`.
+*Effects:* If `nh` is empty, has no effect and returns `a.end()`.
+Otherwise, inserts the element owned by `nh` if and only if there is no
+element with key equivalent to `nh.key()` in containers with unique
+keys; always inserts the element owned by `nh` in containers with
+equivalent keys. The element is inserted as close as possible to the
+position just prior to `p`.
+*Ensures:* `nh` is empty if insertion succeeds, unchanged if insertion
+fails.
+*Returns:* An iterator pointing to the element with key equivalent to
+`nh.key()`.
+*Complexity:* Logarithmic in general, but amortized constant if the
+element is inserted right before `p`.
+``` cpp
+a.extract(k)
+```
+*Result:* `node_type`
+*Effects:* Removes the first element in the container with key
+equivalent to `k`.
+*Returns:* A `node_type` owning the element if found, otherwise an empty
+`node_type`.
+*Complexity:* log (`a.size()`)
+``` cpp
+a_tran.extract(kx)
+```
+*Result:* `node_type`
+*Effects:* Removes the first element in the container with key `r` such
+that `!c(r, kx) && !c(kx, r)` is `true`.
+*Returns:* A `node_type` owning the element if found, otherwise an empty
+`node_type`.
+*Complexity:* log(`a_tran.size()`)
+``` cpp
+a.extract(q)
+```
+*Result:* `node_type`
+*Effects:* Removes the element pointed to by `q`.
+*Returns:* A `node_type` owning that element.
+*Complexity:* Amortized constant.
+``` cpp
+a.merge(a2)
+```
+*Result:* `void`
+*Preconditions:* `a.get_allocator() == a2.get_allocator()`.
+*Effects:* Attempts to extract each element in `a2` and insert it into
+`a` using the comparison object of `a`. In containers with unique keys,
+if there is an element in `a` with key equivalent to the key of an
+element from `a2`, then that element is not extracted from `a2`.
+*Ensures:* Pointers and references to the transferred elements of `a2`
+refer to those same elements but as members of `a`. Iterators referring
+to the transferred elements will continue to refer to their elements,
+but they now behave as iterators into `a`, not into `a2`.
+*Throws:* Nothing unless the comparison object throws.
+*Complexity:* N log(`a.size()+` N), where N has the value `a2.size()`.
+``` cpp
+a.erase(k)
+```
+*Result:* `size_type`
+*Effects:* Erases all elements in the container with key equivalent to
+`k`.
+*Returns:* The number of erased elements.
+*Complexity:* log (`a.size()`) + `a.count(k)`
+``` cpp
+a_tran.erase(kx)
+```
+*Result:* `size_type`
+*Effects:* Erases all elements in the container with key `r` such that
+`!c(r, kx) && !c(kx, r)` is `true`.
+*Returns:* The number of erased elements.
+*Complexity:* log(`a_tran.size())` + `a_tran.count(kx)`
+``` cpp
+a.erase(q)
+```
+*Result:* `iterator`
+*Effects:* Erases the element pointed to by `q`.
+*Returns:* An iterator pointing to the element immediately following `q`
+prior to the element being erased. If no such element exists, returns
+`a.end()`.
+*Complexity:* Amortized constant.
+``` cpp
+a.erase(r)
+```
+*Result:* `iterator`
+*Effects:* Erases the element pointed to by `r`.
+*Returns:* An iterator pointing to the element immediately following `r`
+prior to the element being erased. If no such element exists, returns
+`a.end()`.
+*Complexity:* Amortized constant.
+``` cpp
+a.erase(q1, q2)
+```
+*Result:* `iterator`
+*Effects:* Erases all the elements in the range \[`q1`, `q2`).
+*Returns:* An iterator pointing to the element pointed to by `q2` prior
+to any elements being erased. If no such element exists, `a.end()` is
+returned.
+*Complexity:* log(`a.size()`) + N, where N has the value
+`distance(q1, q2)`.
+``` cpp
+a.clear()
+```
+*Effects:* Equivalent to `a.erase(a.begin(), a.end())`.
+*Ensures:* `a.empty()` is `true`.
+*Complexity:* Linear in `a.size()`.
+``` cpp
+b.find(k)
+```
+*Result:* `iterator`; `const_iterator` for constant `b`.
+*Returns:* An iterator pointing to an element with the key equivalent to
+`k`, or `b.end()` if such an element is not found.
+*Complexity:* Logarithmic.
+``` cpp
+a_tran.find(ke)
+```
+*Result:* `iterator`; `const_iterator` for constant `a_tran`.
+*Returns:* An iterator pointing to an element with key `r` such that
+`!c(r, ke) && !c(ke, r)` is `true`, or `a_tran.end()` if such an element
+is not found.
+*Complexity:* Logarithmic.
+``` cpp
+b.count(k)
+```
+*Result:* `size_type`
+*Returns:* The number of elements with key equivalent to `k`.
+*Complexity:* log (`b.size()`) + `b.count(k)`
+``` cpp
+a_tran.count(ke)
+```
+*Result:* `size_type`
+*Returns:* The number of elements with key `r` such that
+`!c(r, ke) && !c(ke, r)`.
+*Complexity:* log (`a_tran.size()`) + `a_tran.count(ke)`
+``` cpp
+b.contains(k)
+```
+*Result:* `bool`
+*Effects:* Equivalent to: `return b.find(k) != b.end();`
+``` cpp
+a_tran.contains(ke)
+```
+*Result:* `bool`
+*Effects:* Equivalent to: `return a_tran.find(ke) != a_tran.end();`
+``` cpp
+b.lower_bound(k)
+```
+*Result:* `iterator`; `const_iterator` for constant `b`.
+*Returns:* An iterator pointing to the first element with key not less
+than `k`, or `b.end()` if such an element is not found.
+*Complexity:* Logarithmic.
+``` cpp
+a_tran.lower_bound(kl)
+```
+*Result:* `iterator`; `const_iterator` for constant `a_tran`.
+*Returns:* An iterator pointing to the first element with key `r` such
+that `!c(r, kl)`, or `a_tran.end()` if such an element is not found.
+*Complexity:* Logarithmic.
+``` cpp
+b.upper_bound(k)
+```
+*Result:* `iterator`; `const_iterator` for constant `b`.
+*Returns:* An iterator pointing to the first element with key greater
+than `k`, or `b.end()` if such an element is not found.
+*Complexity:* Logarithmic,
+``` cpp
+a_tran.upper_bound(ku)
+```
+*Result:* `iterator`; `const_iterator` for constant `a_tran`.
+*Returns:* An iterator pointing to the first element with key `r` such
+that `c(ku, r)`, or `a_tran.end()` if such an element is not found.
+*Complexity:* Logarithmic.
+``` cpp
+b.equal_range(k)
+```
+*Result:* `pair<iterator, iterator>`;
+`pair<const_iterator, const_iterator>` for constant `b`.
+*Effects:* Equivalent to:
+`return make_pair(b.lower_bound(k), b.upper_bound(k));`
+*Complexity:* Logarithmic.
+``` cpp
+a_tran.equal_range(ke)
+```
+*Result:* `pair<iterator, iterator>`;
+`pair<const_iterator, const_iterator>` for constant `a_tran`.
+*Effects:* Equivalent to:
+`return make_pair(a_tran.lower_bound(ke), a_tran.upper_bound(ke));`
+*Complexity:* Logarithmic.
+The `insert`, `insert_range`, and `emplace` members shall not affect the
+validity of iterators and references to the container, and the `erase`
+members shall invalidate only iterators and references to the erased
+elements.
 The `extract` members invalidate only iterators to the removed element;
 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
 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`, `equal_range`, `erase`, and `extract`
+shall not participate in overload resolution unless the *qualified-id*
+`Compare::is_transparent` is valid and denotes a type [[temp.deduct]].
+Additionally, the member function templates `extract` and `erase` shall
+not participate in overload resolution if
+`is_convertible_v<K&&, iterator> || is_convertible_v<K&&, const_iterator>`
+is `true`, where `K` is the type substituted as the first template
+argument.
 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
 unless that exception is thrown by the swap of the container’s `Compare`
 object (if any).
 ### Unordered associative containers <a id="unord.req">[[unord.req]]</a>
+#### General <a id="unord.req.general">[[unord.req.general]]</a>
 Unordered associative containers provide an ability for fast retrieval
 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`.
 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.
+In this subclause,
 - `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 value of type `X` or `const 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 value of type `X` or `const 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,
+- `rg` denotes a value of a type `R` that models
+  `container-compatible-range<value_type>`,
 - `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 value of type `hasher` or `const hasher`,
+- `eq` denotes a value of type `key_equal` or `const 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
+  - if any two of `eq(r1, ke)`, `eq(r2, ke)`, and `eq(r1, r2)` are
+    `true`, then all three are `true`,
+  where `r1` and `r2` are keys of elements in `a_tran`,
+- `kx` is a value such that
+  - `eq(r1, kx) == eq(kx, r1)`,
+  - `hf(r1) == hf(kx)` if `eq(r1, kx)` is `true`,
+  - if any two of `eq(r1, kx)`, `eq(r2, kx)`, and `eq(r1, r2)` are
+    `true`, then all three are `true`, and
+  - `kx` is not convertible to either `iterator` or `const_iterator`,
   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 an rvalue of type `X::node_type`.
+A type `X` meets the *unordered associative container* requirements if
+`X` meets all the requirements of an allocator-aware container
+[[container.requirements.general]] and the following types, statements,
+and expressions are well-formed and have the specified semantics, except
+that for `unordered_map` and `unordered_multimap`, the requirements
+placed on `value_type` in [[container.alloc.reqmts]] 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*]
+``` cpp
+typename X::key_type
+```
+*Result:* `Key`.
+``` cpp
+typename X::mapped_type
+```
+*Result:* `T`.
+*Remarks:* For `unordered_map` and `unordered_multimap` only.
+``` cpp
+typename X::value_type
+```
+*Result:* `Key` for `unordered_set` and `unordered_multiset` only;
+`pair<const Key, T>` for `unordered_map` and `unordered_multimap` only.
+*Preconditions:* `value_type` is *Cpp17Erasable* from `X`.
+``` cpp
+typename X::hasher
+```
+*Result:* `Hash`.
+*Preconditions:* `Hash` is a unary function object type such that the
+expression `hf(k)` has type `size_t`.
+``` cpp
+typename X::key_equal
+```
+*Result:* `Pred`.
+*Preconditions:* `Pred` meets the *Cpp17CopyConstructible* requirements.
+`Pred` is a binary predicate that takes two arguments of type `Key`.
+`Pred` is an equivalence relation.
+``` cpp
+typename X::local_iterator
+```
+*Result:* An iterator type whose category, value type, difference type,
+and pointer and reference types are the same as `X::iterator`’s.
+[*Note 1*: A `local_iterator` object can be used to iterate through a
+single bucket, but cannot be used to iterate across
+buckets. — *end note*]
+``` cpp
+typename X::const_local_iterator
+```
+*Result:* An iterator type whose category, value type, difference type,
+and pointer and reference types are the same as `X::const_iterator`’s.
+[*Note 2*: A `const_local_iterator` object can be used to iterate
+through a single bucket, but cannot be used to iterate across
+buckets. — *end note*]
+``` cpp
+typename X::node_type
+```
+*Result:* A specialization of a *node-handle* class
+template [[container.node]], such that the public nested types are the
+same types as the corresponding types in `X`.
+``` cpp
+X(n, hf, eq)
+```
+*Effects:* Constructs an empty container with at least `n` buckets,
+using `hf` as the hash function and `eq` as the key equality predicate.
+*Complexity:* 𝑂(`n`)
+``` cpp
+X(n, hf)
+```
+*Preconditions:* `key_equal` meets the *Cpp17DefaultConstructible*
+requirements.
+*Effects:* Constructs an empty container with at least `n` buckets,
+using `hf` as the hash function and `key_equal()` as the key equality
+predicate.
+*Complexity:* 𝑂(`n`)
+``` cpp
+X(n)
+```
+*Preconditions:* `hasher` and `key_equal` meet the
+*Cpp17DefaultConstructible* requirements.
+*Effects:* Constructs an empty container with at least `n` buckets,
+using `hasher()` as the hash function and `key_equal()` as the key
+equality predicate.
+*Complexity:* 𝑂(`n`)
+``` cpp
+X a = X();
+X a;
+```
+*Preconditions:* `hasher` and `key_equal` meet the
+*Cpp17DefaultConstructible* requirements.
+*Effects:* Constructs an empty container with an unspecified number of
+buckets, using `hasher()` as the hash function and `key_equal()` as the
+key equality predicate.
+*Complexity:* Constant.
+``` cpp
+X(i, j, n, hf, eq)
+```
+*Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `X`
+from `*i`.
+*Effects:* Constructs an empty container with at least `n` buckets,
+using `hf` as the hash function and `eq` as the key equality predicate,
+and inserts elements from \[`i`, `j`) into it.
+*Complexity:* Average case 𝑂(N) (N is `distance(i, j)`), worst case
+𝑂(N^2).
+``` cpp
+X(i, j, n, hf)
+```
+*Preconditions:* `key_equal` meets the *Cpp17DefaultConstructible*
+requirements. `value_type` is *Cpp17EmplaceConstructible* into `X` from
+`*i`.
+*Effects:* Constructs an empty container with at least `n` buckets,
+using `hf` as the hash function and `key_equal()` as the key equality
+predicate, and inserts elements from \[`i`, `j`) into it.
+*Complexity:* Average case 𝑂(N) (N is `distance(i, j)`), worst case
+𝑂(N^2).
+``` cpp
+X(i, j, n)
+```
+*Preconditions:* `hasher` and `key_equal` meet the
+*Cpp17DefaultConstructible* requirements. `value_type` is
+*Cpp17EmplaceConstructible* into `X` from `*i`.
+*Effects:* Constructs an empty container with at least `n` buckets,
+using `hasher()` as the hash function and `key_equal()` as the key
+equality predicate, and inserts elements from \[`i`, `j`) into it.
+*Complexity:* Average case 𝑂(N) (N is `distance(i, j)`), worst case
+𝑂(N^2).
+``` cpp
+X(i, j)
+```
+*Preconditions:* `hasher` and `key_equal` meet the
+*Cpp17DefaultConstructible* requirements. `value_type` is
+*Cpp17EmplaceConstructible* into `X` from `*i`.
+*Effects:* Constructs an empty container with an unspecified number of
+buckets, using `hasher()` as the hash function and `key_equal()` as the
+key equality predicate, and inserts elements from \[`i`, `j`) into it.
+*Complexity:* Average case 𝑂(N) (N is `distance(i, j)`), worst case
+𝑂(N^2).
+``` cpp
+X(from_range, rg, n, hf, eq)
+```
+*Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `X`
+from `*ranges::begin(rg)`.
+*Effects:* Constructs an empty container with at least `n` buckets,
+using `hf` as the hash function and `eq` as the key equality predicate,
+and inserts elements from `rg` into it.
+*Complexity:* Average case 𝑂(N) (N is `ranges::distance(rg)`), worst
+case 𝑂(N^2).
+``` cpp
+X(from_range, rg, n, hf)
+```
+*Preconditions:* `key_equal` meets the *Cpp17DefaultConstructible*
+requirements. `value_type` is *Cpp17EmplaceConstructible* into `X` from
+`*ranges::begin(rg)`.
+*Effects:* Constructs an empty container with at least `n` buckets,
+using `hf` as the hash function and `key_equal()` as the key equality
+predicate, and inserts elements from `rg` into it.
+*Complexity:* Average case 𝑂(N) (N is `ranges::distance(rg)`), worst
+case 𝑂(N^2).
+``` cpp
+X(from_range, rg, n)
+```
+*Preconditions:* `hasher` and `key_equal` meet the
+*Cpp17DefaultConstructible* requirements. `value_type` is
+*Cpp17EmplaceConstructible* into `X` from `*ranges::begin(rg)`.
+*Effects:* Constructs an empty container with at least `n` buckets,
+using `hasher()` as the hash function and `key_equal()` as the key
+equality predicate, and inserts elements from `rg` into it.
+*Complexity:* Average case 𝑂(N) (N is `ranges::distance(rg)`), worst
+case 𝑂(N^2).
+``` cpp
+X(from_range, rg)
+```
+*Preconditions:* `hasher` and `key_equal` meet the
+*Cpp17DefaultConstructible* requirements. `value_type` is
+*Cpp17EmplaceConstructible* into `X` from `*ranges::begin(rg)`.
+*Effects:* Constructs an empty container with an unspecified number of
+buckets, using `hasher()` as the hash function and `key_equal()` as the
+key equality predicate, and inserts elements from `rg` into it.
+*Complexity:* Average case 𝑂(N) (N is `ranges::distance(rg)`), worst
+case 𝑂(N^2).
+``` cpp
+X(il)
+```
+*Effects:* Equivalent to `X(il.begin(), il.end())`.
+``` cpp
+X(il, n)
+```
+*Effects:* Equivalent to `X(il.begin(), il.end(), n)`.
+``` cpp
+X(il, n, hf)
+```
+*Effects:* Equivalent to `X(il.begin(), il.end(), n, hf)`.
+``` cpp
+X(il, n, hf, eq)
+```
+*Effects:* Equivalent to `X(il.begin(), il.end(), n, hf, eq)`.
+``` cpp
+X(b)
+```
+*Effects:* In addition to the container
+requirements [[container.requirements.general]], copies the hash
+function, predicate, and maximum load factor.
+*Complexity:* Average case linear in `b.size()`, worst case quadratic.
+``` cpp
+a = b
+```
+*Result:* `X&`
+*Effects:* In addition to the container requirements, copies the hash
+function, predicate, and maximum load factor.
+*Complexity:* Average case linear in `b.size()`, worst case quadratic.
+``` cpp
+a = il
+```
+*Result:* `X&`
+*Preconditions:* `value_type` is *Cpp17CopyInsertable* into `X` and
+*Cpp17CopyAssignable*.
+*Effects:* Assigns the range \[`il.begin()`, `il.end()`) into `a`. All
+existing elements of `a` are either assigned to or destroyed.
+*Complexity:* Average case linear in `il.size()`, worst case quadratic.
+``` cpp
+b.hash_function()
+```
+*Result:* `hasher`
+*Returns:* `b`’s hash function.
+*Complexity:* Constant.
+``` cpp
+b.key_eq()
+```
+*Result:* `key_equal`
+*Returns:* `b`’s key equality predicate.
+*Complexity:* Constant.
+``` cpp
+a_uniq.emplace(args)
+```
+*Result:* `pair<iterator,` `bool>`
+*Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `X`
+from `args`.
+*Effects:* Inserts a `value_type` object `t` constructed with
+`std::forward<Args>(args)...` if and only if there is no element in the
+container with key equivalent to the key of `t`.
+*Returns:* The `bool` component of the returned pair is `true` if and
+only if the insertion takes place, and the iterator component of the
+pair points to the element with key equivalent to the key of `t`.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a_uniq.size()`).
+``` cpp
+a_eq.emplace(args)
+```
+*Result:* `iterator`
+*Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `X`
+from `args`.
+*Effects:* Inserts a `value_type` object `t` constructed with
+`std::forward<Args>(args)...`.
+*Returns:* An iterator pointing to the newly inserted element.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a_eq.size()`).
+``` cpp
+a.emplace_hint(p, args)
+```
+*Result:* `iterator`
+*Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `X`
+from `args`.
+*Effects:* Equivalent to `a.emplace(std::forward<Args>(args)...)`.
+*Returns:* An iterator pointing to the element with the key equivalent
+to the newly inserted element. The `const_iterator` `p` is a hint
+pointing to where the search should start. Implementations are permitted
+to ignore the hint.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a.size()`).
+``` cpp
+a_uniq.insert(t)
+```
+*Result:* `pair<iterator, bool>`
+*Preconditions:* If `t` is a non-const rvalue, `value_type` is
+*Cpp17MoveInsertable* into `X`; otherwise, `value_type` is
+*Cpp17CopyInsertable* into `X`.
+*Effects:* Inserts `t` if and only if there is no element in the
+container with key equivalent to the key of `t`.
+*Returns:* The `bool` component of the returned pair indicates whether
+the insertion takes place, and the `iterator` component points to the
+element with key equivalent to the key of `t`.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a_uniq.size()`).
+``` cpp
+a_eq.insert(t)
+```
+*Result:* `iterator`
+*Preconditions:* If `t` is a non-const rvalue, `value_type` is
+*Cpp17MoveInsertable* into `X`; otherwise, `value_type` is
+*Cpp17CopyInsertable* into `X`.
+*Effects:* Inserts `t`.
+*Returns:* An iterator pointing to the newly inserted element.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a_eq.size()`).
+``` cpp
+a.insert(p, t)
+```
+*Result:* `iterator`
+*Preconditions:* If `t` is a non-const rvalue, `value_type` is
+*Cpp17MoveInsertable* into `X`; otherwise, `value_type` is
+*Cpp17CopyInsertable* into `X`.
+*Effects:* Equivalent to `a.insert(t)`. The iterator `p` is a hint
+pointing to where the search should start. Implementations are permitted
+to ignore the hint.
+*Returns:* An iterator pointing to the element with the key equivalent
+to that of `t`.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a.size()`).
+``` cpp
+a.insert(i, j)
+```
+*Result:* `void`
+*Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `X`
+from `*i`. Neither `i` nor `j` are iterators into `a`.
+*Effects:* Equivalent to `a.insert(t)` for each element in `[i,j)`.
+*Complexity:* Average case 𝑂(N), where N is `distance(i, j)`, worst case
+𝑂(N(`a.size()` + 1)).
+``` cpp
+a.insert_range(rg)
+```
+*Result:* `void`
+*Preconditions:* `value_type` is *Cpp17EmplaceConstructible* into `X`
+from `*ranges::begin(rg)`. `rg` and `a` do not overlap.
+*Effects:* Equivalent to `a.insert(t)` for each element `t` in `rg`.
+*Complexity:* Average case 𝑂(N), where N is `ranges::distance(rg)`,
+worst case 𝑂(N(`a.size()` + 1)).
+``` cpp
+a.insert(il)
+```
+*Effects:* Equivalent to `a.insert(il.begin(), il.end())`.
+``` cpp
+a_uniq.insert(nh)
+```
+*Result:* `insert_return_type`
+*Preconditions:* `nh` is empty or
+`a_uniq.get_allocator() == nh.get_allocator()` is `true`.
+*Effects:* If `nh` is empty, has no effect. Otherwise, inserts the
+element owned by `nh` if and only if there is no element in the
+container with a key equivalent to `nh.key()`.
+*Ensures:* If `nh` is empty, `inserted` is `false`, `position` is
+`end()`, and `node` is empty. Otherwise if the insertion took place,
+`inserted` is `true`, `position` points to the inserted element, and
+`node` is empty; if the insertion failed, `inserted` is `false`, `node`
+has the previous value of `nh`, and `position` points to an element with
+a key equivalent to `nh.key()`.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a_uniq.size()`).
+``` cpp
+a_eq.insert(nh)
+```
+*Result:* `iterator`
+*Preconditions:* `nh` is empty or
+`a_eq.get_allocator() == nh.get_allocator()` is `true`.
+*Effects:* If `nh` is empty, has no effect and returns `a_eq.end()`.
+Otherwise, inserts the element owned by `nh` and returns an iterator
+pointing to the newly inserted element.
+*Ensures:* `nh` is empty.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a_eq.size()`).
+``` cpp
+a.insert(q, nh)
+```
+*Result:* `iterator`
+*Preconditions:* `nh` is empty or
+`a.get_allocator() == nh.get_allocator()` is `true`.
+*Effects:* If `nh` is empty, has no effect and returns `a.end()`.
+Otherwise, inserts the element owned by `nh` if and only if there is no
+element with key equivalent to `nh.key()` in containers with unique
+keys; always inserts the element owned by `nh` in containers with
+equivalent keys. The iterator `q` is a hint pointing to where the search
+should start. Implementations are permitted to ignore the hint.
+*Ensures:* `nh` is empty if insertion succeeds, unchanged if insertion
+fails.
+*Returns:* An iterator pointing to the element with key equivalent to
+`nh.key()`.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a.size()`).
+``` cpp
+a.extract(k)
+```
+*Result:* `node_type`
+*Effects:* Removes an element in the container with key equivalent to
+`k`.
+*Returns:* A `node_type` owning the element if found, otherwise an empty
+`node_type`.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a.size()`).
+``` cpp
+a_tran.extract(kx)
+```
+*Result:* `node_type`
+*Effects:* Removes an element in the container with key equivalent to
+`kx`.
+*Returns:* A `node_type` owning the element if found, otherwise an empty
+`node_type`.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a_tran.size()`).
+``` cpp
+a.extract(q)
+```
+*Result:* `node_type`
+*Effects:* Removes the element pointed to by `q`.
+*Returns:* A `node_type` owning that element.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a.size()`).
+``` cpp
+a.merge(a2)
+```
+*Result:* `void`
+*Preconditions:* `a.get_allocator() == a2.get_allocator()`.
+*Effects:* Attempts to extract each element in `a2` and insert it into
+`a` using the hash function and key equality predicate of `a`. In
+containers with unique keys, if there is an element in `a` with key
+equivalent to the key of an element from `a2`, then that element is not
+extracted from `a2`.
+*Ensures:* Pointers and references to the transferred elements of `a2`
+refer to those same elements but as members of `a`. Iterators referring
+to the transferred elements and all iterators referring to `a` will be
+invalidated, but iterators to elements remaining in `a2` will remain
+valid.
+*Complexity:* Average case 𝑂(N), where N is `a2.size()`, worst case
+𝑂(N`*a.size() + N`).
+``` cpp
+a.erase(k)
+```
+*Result:* `size_type`
+*Effects:* Erases all elements with key equivalent to `k`.
+*Returns:* The number of elements erased.
+*Complexity:* Average case 𝑂(`a.count(k)`), worst case 𝑂(`a.size()`).
+``` cpp
+a_tran.erase(kx)
+```
+*Result:* `size_type`
+*Effects:* Erases all elements with key equivalent to `kx`.
+*Returns:* The number of elements erased.
+*Complexity:* Average case 𝑂(`a_tran.count(kx)`), worst case
+𝑂(`a_tran.size()`).
+``` cpp
+a.erase(q)
+```
+*Result:* `iterator`
+*Effects:* Erases the element pointed to by `q`.
+*Returns:* The iterator immediately following `q` prior to the erasure.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a.size()`).
+``` cpp
+a.erase(r)
+```
+*Result:* `iterator`
+*Effects:* Erases the element pointed to by `r`.
+*Returns:* The iterator immediately following `r` prior to the erasure.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a.size()`).
+``` cpp
+a.erase(q1, q2)
+```
+*Result:* `iterator`
+*Effects:* Erases all elements in the range `[q1, q2)`.
+*Returns:* The iterator immediately following the erased elements prior
+to the erasure.
+*Complexity:* Average case linear in `distance(q1, q2)`, worst case
+𝑂(`a.size()`).
+``` cpp
+a.clear()
+```
+*Result:* `void`
+*Effects:* Erases all elements in the container.
+*Ensures:* `a.empty()` is `true`.
+*Complexity:* Linear in `a.size()`.
+``` cpp
+b.find(k)
+```
+*Result:* `iterator`; `const_iterator` for constant `b`.
+*Returns:* An iterator pointing to an element with key equivalent to
+`k`, or `b.end()` if no such element exists.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`b.size()`).
+``` cpp
+a_tran.find(ke)
+```
+*Result:* `iterator`; `const_iterator` for constant `a_tran`.
+*Returns:* An iterator pointing to an element with key equivalent to
+`ke`, or `a_tran.end()` if no such element exists.
+*Complexity:* Average case 𝑂(1), worst case 𝑂(`a_tran.size()`).
+``` cpp
+b.count(k)
+```
+*Result:* `size_type`
+*Returns:* The number of elements with key equivalent to `k`.
+*Complexity:* Average case 𝑂(`b.count(k)`), worst case 𝑂(`b.size()`).
+``` cpp
+a_tran.count(ke)
+```
+*Result:* `size_type`
+*Returns:* The number of elements with key equivalent to `ke`.
+*Complexity:* Average case 𝑂(`a_tran.count(ke)`), worst case
+𝑂(`a_tran.size()`).
+``` cpp
+b.contains(k)
+```
+*Effects:* Equivalent to `b.find(k) != b.end()`.
+``` cpp
+a_tran.contains(ke)
+```
+*Effects:* Equivalent to `a_tran.find(ke) != a_tran.end()`.
+``` cpp
+b.equal_range(k)
+```
+*Result:* `pair<iterator, iterator>`;
+`pair<const_iterator, const_iterator>` for constant `b`.
+*Returns:* A range containing all elements with keys equivalent to `k`.
+Returns `make_pair(b.end(), b.end())` if no such elements exist.
+*Complexity:* Average case 𝑂(`b.count(k)`), worst case 𝑂(`b.size()`).
+``` cpp
+a_tran.equal_range(ke)
+```
+*Result:* `pair<iterator, iterator>`;
+`pair<const_iterator, const_iterator>` for constant `a_tran`.
+*Returns:* A range containing all elements with keys equivalent to `ke`.
+Returns `make_pair(a_tran.end(), a_tran.end())` if no such elements
+exist.
+*Complexity:* Average case 𝑂(`a_tran.count(ke)`), worst case
+𝑂(`a_tran.size()`).
+``` cpp
+b.bucket_count()
+```
+*Result:* `size_type`
+*Returns:* The number of buckets that `b` contains.
+*Complexity:* Constant.
+``` cpp
+b.max_bucket_count()
+```
+*Result:* `size_type`
+*Returns:* An upper bound on the number of buckets that `b` can ever
+contain.
+*Complexity:* Constant.
+``` cpp
+b.bucket(k)
+```
+*Result:* `size_type`
+*Preconditions:* `b.bucket_count() > 0`.
+*Returns:* The index of the bucket in which elements with keys
+equivalent to `k` would be found, if any such element existed. The
+return value is in the range `[0, b.bucket_count())`.
+*Complexity:* Constant.
+``` cpp
+b.bucket_size(n)
+```
+*Result:* `size_type`
+*Preconditions:* `n` shall be in the range `[0, b.bucket_count())`.
+*Returns:* The number of elements in the `n`ᵗʰ bucket.
+*Complexity:* 𝑂(`b.bucket_size(n)`)
+``` cpp
+b.begin(n)
+```
+*Result:* `local_iterator`; `const_local_iterator` for constant `b`.
+*Preconditions:* `n` is in the range `[0, b.bucket_count())`.
+*Returns:* An iterator referring to the first element in the bucket. If
+the bucket is empty, then `b.begin(n) == b.end(n)`.
+*Complexity:* Constant.
+``` cpp
+b.end(n)
+```
+*Result:* `local_iterator`; `const_local_iterator` for constant `b`.
+*Preconditions:* `n` is in the range `[0, b.bucket_count())`.
+*Returns:* An iterator which is the past-the-end value for the bucket.
+*Complexity:* Constant.
+``` cpp
+b.cbegin(n)
+```
+*Result:* `const_local_iterator`
+*Preconditions:* `n` shall be in the range `[0, b.bucket_count())`.
+*Returns:* An iterator referring to the first element in the bucket. If
+the bucket is empty, then `b.cbegin(n) == b.cend(n)`.
+*Complexity:* Constant.
+``` cpp
+b.cend(n)
+```
+*Result:* `const_local_iterator`
+*Preconditions:* `n` is in the range `[0, b.bucket_count())`.
+*Returns:* An iterator which is the past-the-end value for the bucket.
+*Complexity:* Constant.
+``` cpp
+b.load_factor()
+```
+*Result:* `float`
+*Returns:* The average number of elements per bucket.
+*Complexity:* Constant.
+``` cpp
+b.max_load_factor()
+```
+*Result:* `float`
+*Returns:* A positive number that the container attempts to keep the
+load factor less than or equal to. The container automatically increases
+the number of buckets as necessary to keep the load factor below this
+number.
+*Complexity:* Constant.
+``` cpp
+a.max_load_factor(z)
+```
+*Result:* `void`
+*Preconditions:* `z` is positive. May change the container’s maximum
+load factor, using `z` as a hint.
+*Complexity:* Constant.
+``` cpp
+a.rehash(n)
+```
+*Result:* `void`
+*Ensures:* `a.bucket_count() >= a.size() / a.max_load_factor()` and
+`a.bucket_count() >= n`.
+*Complexity:* Average case linear in `a.size()`, worst case quadratic.
+``` cpp
+a.reserve(n)
+```
+*Effects:* Equivalent to `a.rehash(ceil(n / a.max_load_factor()))`.
 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)`,
 `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.
+The `insert`, `insert_range`, and `emplace` members shall not affect the
+validity of references to container elements, but may invalidate all
+iterators to the container. The `erase` members shall invalidate only
+iterators and references to the erased elements, and preserve the
+relative order of the elements that are not erased.
+The `insert`, `insert_range`, and `emplace` members shall not affect the
+validity of iterators if `(N+n) <= z * B`, where `N` is the number of
+elements in the container prior to the insert operation, `n` is the
+number of elements inserted, `B` is the container’s bucket count, and
+`z` is the container’s maximum load factor.
 The `extract` members invalidate only iterators to the removed element,
 and preserve the relative order of the elements that are not erased;
 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.
+The member function templates `find`, `count`, `equal_range`,
+`contains`, `extract`, and `erase` 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]].
+Additionally, the member function templates `extract` and `erase` shall
+not participate in overload resolution if
+`is_convertible_v<K&&, iterator> || is_convertible_v<K&&, const_iterator>`
+is `true`, where `K` is the type substituted as the first template
+argument.
 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

Diff to HTML by rtfpessoa