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

Files changed (1) hide show

tmp/tmp9l4jhjm7/{from.md → to.md} +477 -155

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

@@ -5,46 +5,53 @@
 Containers are objects that store other objects. They control allocation
 and deallocation of these objects through constructors, destructors,
 insert and erase operations.
 All of the complexity requirements in this Clause are stated solely in
-terms of the number of operations on the contained objects. the copy
-constructor of type `vector <vector<int> >` has linear complexity, even
-though the complexity of copying each contained `vector<int>` is itself
-linear.
 For the components affected by this subclause that declare an
 `allocator_type`, objects stored in these components shall be
-constructed using the `allocator_traits<allocator_type>::construct`
-function and destroyed using the
-`allocator_traits<allocator_type>::destroy` function (
-[[allocator.traits.members]]). These functions are called only for the
-container’s element type, not for internal types used by the container.
-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.
 In Tables  [[tab:containers.container.requirements]],
 [[tab:containers.reversible.requirements]], and
 [[tab:containers.optional.operations]] `X` denotes a container class
 containing objects of type `T`, `a` and `b` denote values of type `X`,
 `u` denotes an identifier, `r` denotes a non-const value of type `X`,
 and `rv` denotes a non-const rvalue of type `X`.
-Notes: the algorithm `equal()` is defined in Clause  [[algorithms]].
 Those entries marked “(Note A)” or “(Note B)” have linear complexity for
 `array` and have constant complexity for all other standard containers.
 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
@@ -60,50 +67,59 @@ 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]]). Copy
-constructors for these container types obtain an allocator by calling
 `allocator_traits<allocator_type>::select_on_container_copy_construction`
 on the allocator belonging to the container being copied. Move
 constructors obtain an allocator by move construction from the allocator
 belonging to the container being moved. Such move construction of the
 allocator shall not exit via an exception. All other constructors for
-these container types take a `const allocator_type&` argument. If an
-invocation of a constructor uses the default value of an optional
-allocator argument, then the `Allocator` type must support value
-initialization. A copy of this allocator is used for any memory
-allocation 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. The behavior of a call to a container’s `swap` function is
-undefined unless the objects being swapped have allocators that compare
-equal or
-`allocator_traits<allocator_type>::propagate_on_container_swap::value`
-is true. 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` objects
-belonging to `a` and `b` shall be swappable and shall be exchanged by
-unqualified calls to non-member `swap`. If
 `allocator_traits<allocator_type>::propagate_on_container_swap::value`
-is `true`, then the allocators of `a` and `b` shall also be exchanged
-using an unqualified call to non-member `swap`. Otherwise, they 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.
@@ -128,39 +144,45 @@ requirements:
 - 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.
-  The `end()` iterator does not refer to any element, so it may be
-  invalidated.
 Unless otherwise specified (either explicitly or by defining a function
 in terms of other functions), invoking a container member function or
 passing a container as an argument to a library function shall not
 invalidate iterators to, or change the values of, objects within that
 container.
 Table  [[tab:containers.optional.operations]] lists operations that are
 provided for some types of containers but not others. Those containers
 for which the listed operations are provided shall implement the
 semantics described in Table  [[tab:containers.optional.operations]]
 unless otherwise stated.
-Note: the algorithm `lexicographical_compare()` is defined in Clause
-[[algorithms]].
-All of the containers defined in this Clause and in ([[basic.string]])
 except `array` meet the additional requirements of an allocator-aware
 container, as described in Table  [[tab:containers.allocatoraware]].
-Given a container type `X` having an `allocator_type` identical to `A`
-and a `value_type` identical to `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
-`std::allocator<T>` — no allocator object needs to be created and user
-specializations of `std::allocator<T>` are not instantiated:
 - `T` is *`DefaultInsertable` into `X`* means that the following
   expression is well-formed:
   ``` cpp
   allocator_traits<A>::construct(m, p)
@@ -179,11 +201,13 @@ specializations of `std::allocator<T>` are not instantiated:
   allocator_traits<A>::construct(m, p, rv)
   ```
   and its evaluation causes the following postcondition to hold: The
   value of `*p` is equivalent to the value of `rv` before the
-  evaluation. rv remains a valid object. Its state is unspecified
 - `T` is *`CopyInsertable` into `X`* means that, in addition to `T`
   being `MoveInsertable` into `X`, the following expression is
   well-formed:
   ``` cpp
   allocator_traits<A>::construct(m, p, v)
@@ -200,40 +224,56 @@ specializations of `std::allocator<T>` are not instantiated:
   well-formed:
   ``` cpp
   allocator_traits<A>::destroy(m, p)
   ```
-A container calls `allocator_traits<A>::construct(m, p, args)` to
-construct an element at `p` using `args`. The default `construct` in
-`std::allocator` will call `::new((void*)p) T(args)`, but specialized
-allocators may choose a different definition.
 In Table  [[tab:containers.allocatoraware]], `X` denotes an
 allocator-aware container class with a `value_type` of `T` using
 allocator of type `A`, `u` denotes a variable, `a` and `b` denote
 non-const lvalues of type `X`, `t` denotes an lvalue or a const rvalue
 of type `X`, `rv` denotes a non-const rvalue of type `X`, and `m` is a
 value of type `A`.
 ### Container data races <a id="container.requirements.dataraces">[[container.requirements.dataraces]]</a>
 For purposes of avoiding data races ([[res.on.data.races]]),
 implementations shall consider the following functions to be `const`:
 `begin`, `end`, `rbegin`, `rend`, `front`, `back`, `data`, `find`,
 `lower_bound`, `upper_bound`, `equal_range`, `at` and, except in
 associative or unordered associative containers, `operator[]`.
-Notwithstanding ([[res.on.data.races]]), implementations are required
-to avoid data races when the contents of the contained object in
-different elements in the same container, excepting `vector<bool>`, are
-modified concurrently.
-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`.
 ### 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
@@ -253,30 +293,28 @@ deletions from the middle of the sequence. `deque` is the data structure
 of choice when most insertions and deletions take place at the beginning
 or at the end of the sequence.
 In Tables  [[tab:containers.sequence.requirements]] and
 [[tab:containers.sequence.optional]], `X` denotes a sequence container
-class, `a` denotes a value of `X` containing elements of type `T`, `A`
-denotes `X::allocator_type` if it exists and `std::allocator<T>` if it
-doesn’t, `i` and `j` denote iterators satisfying input iterator
-requirements and refer to elements implicitly convertible to
-`value_type`, `[i, j)` denotes a valid range, `il` designates an object
-of type `initializer_list<value_type>`, `n` denotes a value of
-`X::size_type`, `p` denotes a valid const iterator to `a`, `q` denotes a
-valid dereferenceable const iterator to `a`, `[q1, q2)` denotes a valid
-range of const 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.
-`iterator`
-and `const_iterator` types for sequence containers shall be at least of
-the forward iterator category.
 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`.
@@ -306,45 +344,271 @@ For every sequence container defined in this Clause and in Clause
 - If the constructor
   ``` cpp
   template <class InputIterator>
     X(InputIterator first, InputIterator last,
- const allocator_type& alloc = allocator_type())
   ```
   is called with a type `InputIterator` that does not qualify as an
   input iterator, then the constructor shall not participate in overload
   resolution.
 - If the member functions of the forms:
   ``` cpp
-  template <class InputIterator>          // such as insert()
-  rt fx1(const_iterator p, InputIterator first, InputIterator last);
-  template <class InputIterator>          // such as append(), assign()
-  rt fx2(InputIterator first, InputIterator last);
-  template <class InputIterator>          // such as replace()
-  rt fx3(const_iterator i1, const_iterator i2, InputIterator first, InputIterator last);
   ```
   are called with a type `InputIterator` that does not qualify as an
   input iterator, then these functions shall not participate in overload
   resolution.
-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.
 Table  [[tab:containers.sequence.optional]] lists operations that are
 provided for some types of sequence containers but not others. An
 implementation shall provide these operations for all container types
 shown in the “container” column, and shall implement them so as to take
 amortized constant time.
 The member function `at()` provides bounds-checked access to container
 elements. `at()` throws `out_of_range` if `n >= a.size()`.
 ### 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`.
@@ -376,65 +640,82 @@ For `set` and `multiset` the value type is the same as the key type. For
 of an associative container is of the bidirectional iterator category.
 For associative containers where the value type is the same as the key
 type, both `iterator` and `const_iterator` are constant iterators. It is
 unspecified whether or not `iterator` and `const_iterator` are the same
-type. `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.
 The associative containers meet all the requirements of Allocator-aware
 containers ([[container.requirements.general]]), except that for `map`
 and `multimap`, the requirements placed on `value_type` in Table
 [[tab:containers.container.requirements]] apply instead to `key_type`
-and `mapped_type`. For example, in some cases `key_type` and
-`mapped_type` are required to be `CopyAssignable` even though the
-associated `value_type`, `pair<const key_type, mapped_type>`, is not
-`CopyAssignable`.
 In Table  [[tab:containers.associative.requirements]], `X` denotes an
-associative container class, `a` denotes a value of `X`, `a_uniq`
-denotes a value of `X` when `X` supports unique keys, `a_eq` denotes a
-value of `X` when `X` supports multiple keys, `a_tran` denotes a value
-of `X` when the qualified-id `X::key_compare::is_transparent` is valid
-and denotes a type ([[temp.deduct]]), `i` and `j` satisfy input
-iterator requirements and refer to elements implicitly convertible to
-`value_type`, \[`i`, `j`) denotes a valid range, `p` denotes a valid
-const iterator to `a`, `q` denotes a valid dereferenceable const
-iterator to `a`, `[q1, q2)` denotes a valid range of const iterators in
-`a`, `il` designates an object of type `initializer_list<value_type>`,
-`t` denotes a value of `X::value_type`, `k` denotes a value of
-`X::key_type` and `c` denotes a 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
-`std::allocator<X::value_type>` otherwise, and `m` denotes an allocator
-of a type convertible to `A`.
 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 fundamental property of iterators of associative containers is that
 they iterate through the containers in the non-descending order of keys
 where non-descending is defined by the comparison that was used to
 construct them. For any two dereferenceable iterators `i` and `j` such
-that distance from `i` to `j` is positive,
 ``` cpp
 value_comp(*j, *i) == false
 ```
 For associative containers with unique keys the stronger condition
-holds,
 ``` cpp
-value_comp(*i, *j) != false.
 ```
 When an associative container is constructed by passing a comparison
 object the container shall not store a pointer or reference to the
 passed object, even if that object is passed by reference. When an
@@ -443,13 +724,23 @@ assignment operator, the target container shall then use the comparison
 object from the container being copied, as if that comparison object had
 been passed to the target container in its constructor.
 The member function templates `find`, `count`, `lower_bound`,
 `upper_bound`, and `equal_range` shall not participate in overload
-resolution unless the qualified-id `Compare::is_transparent` is valid
 and denotes a type ([[temp.deduct]]).
 #### Exception safety guarantees <a id="associative.reqmts.except">[[associative.reqmts.except]]</a>
 For associative containers, no `clear()` function throws an exception.
 `erase(k)` does not throw an exception unless that exception is thrown
 by the container’s `Compare` object (if any).
@@ -489,42 +780,47 @@ the *hash function* of the container. The container’s object of type
 the container.
 Two values `k1` and `k2` of type `Key` are considered equivalent if the
 container’s key equality predicate returns `true` when passed those
 values. If `k1` and `k2` are equivalent, the container’s hash function
-shall return the same value for both. Thus, when an unordered
-associative container is instantiated with a non-default `Pred`
-parameter it usually needs a non-default `Hash` parameter as well. For
-any two keys `k1` and `k2` in the same container, calling `pred(k1, k2)`
-shall always return the same value. For any key `k` in a container,
-calling `hash(k)` shall always return the same value.
 An unordered associative container supports *unique keys* if it may
 contain at most one element for each key. Otherwise, it supports
 *equivalent keys*. `unordered_set` and `unordered_map` support unique
 keys. `unordered_multiset` and `unordered_multimap` support equivalent
 keys. In containers that support equivalent keys, elements with
 equivalent keys are adjacent to each other in the iteration order of the
 container. Thus, although the absolute order of elements in an unordered
 container is not specified, its elements are grouped into
-*equivalent-key group*s such that all elements of each group have
 equivalent keys. Mutating operations on unordered containers shall
 preserve the relative order of elements within each equivalent-key group
 unless otherwise specified.
 For `unordered_set` and `unordered_multiset` the value type is the same
 as the key type. For `unordered_map` and `unordered_multimap` it is
-`std::pair<const Key,
 T>`.
 For unordered containers where the value type is the same as the key
 type, both `iterator` and `const_iterator` are constant iterators. It is
 unspecified whether or not `iterator` and `const_iterator` are the same
-type. `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.
 The elements of an unordered associative container are organized into
 *buckets*. Keys with the same hash code appear in the same bucket. The
 number of buckets is automatically increased as elements are added to an
 unordered associative container, so that the average number of elements
@@ -537,37 +833,43 @@ the relative ordering of equivalent elements.
 The unordered associative containers meet all the requirements of
 Allocator-aware containers ([[container.requirements.general]]), except
 that for `unordered_map` and `unordered_multimap`, the requirements
 placed on `value_type` in Table
 [[tab:containers.container.requirements]] apply instead to `key_type`
-and `mapped_type`. For example, `key_type` and `mapped_type` are
-sometimes required to be `CopyAssignable` even though the associated
-`value_type`, `pair<const key_type, mapped_type>`, is not
-`CopyAssignable`.
-In table  [[tab:HashRequirements]]: `X` is an unordered associative
-container class, `a` is an object of type `X`, `b` is a possibly const
-object of type `X`, `a_uniq` is an object of type `X` when `X` supports
-unique keys, `a_eq` is an object of type `X` when `X` supports
-equivalent keys, `i` and `j` are input iterators that refer to
-`value_type`, `[i, j)` is a valid range, `p` and `q2` are valid const
-iterators to `a`, `q` and `q1` are valid dereferenceable const iterators
-to `a`, `[q1, q2)` is a valid range in `a`, `il` designates an object of
-type `initializer_list<value_type>`, `t` is a value of type
-`X::value_type`, `k` is a value of type `key_type`, `hf` is a possibly
-const value of type `hasher`, `eq` is a possibly const value of type
-`key_equal`, `n` is a value of type `size_type`, and `z` is a value of
-type `float`.
 Two unordered containers `a` and `b` compare equal if
 `a.size() == b.size()` and, for every equivalent-key group \[`Ea1`,
 `Ea2`) obtained from `a.equal_range(Ea1)`, there exists an
 equivalent-key group \[`Eb1`, `Eb2`) obtained from `b.equal_range(Ea1)`,
 such that `is_permutation(Ea1, Ea2, Eb1, Eb2)` returns `true`. For
 `unordered_set` and `unordered_map`, the complexity of `operator==`
 (i.e., the number of calls to the `==` operator of the `value_type`, to
-the predicate returned by `key_equal()`, and to the hasher returned by
 `hash_function()`) is proportional to N in the average case and to N² in
 the worst case, where N is a.size(). For `unordered_multiset` and
 `unordered_multimap`, the complexity of `operator==` is proportional to
 $\sum E_i^2$ in the average case and to N² in the worst case, where N is
 `a.size()`, and Eᵢ is the size of the iᵗʰ equivalent-key group in `a`.
@@ -578,31 +880,51 @@ same container), then the average-case complexity for
 `unordered_multiset` and `unordered_multimap` becomes proportional to N
 (but worst-case complexity remains 𝑂(N^2), e.g., for a pathologically
 bad hash function). The behavior of a program that uses `operator==` or
 `operator!=` on unordered containers is undefined unless the `Hash` and
 `Pred` function objects respectively have the same behavior for both
-containers and the equality comparison operator 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 const 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.
 #### Exception safety guarantees <a id="unord.req.except">[[unord.req.except]]</a>
 For unordered associative containers, no `clear()` function throws an
 exception. `erase(k)` does not throw an exception unless that exception
 is thrown by the container’s `Hash` or `Pred` object (if any).
@@ -612,11 +934,11 @@ operation other than the container’s hash function from within an
 `insert` or `emplace` function inserting a single element, the insertion
 has no effect.
 For unordered associative containers, no `swap` function throws an
 exception unless that exception is thrown by the swap of the container’s
-Hash or Pred object (if any).
 For unordered associative containers, if an exception is thrown from
 within a `rehash()` function other than by the container’s hash function
 or comparison function, the `rehash()` function has no effect.

 Containers are objects that store other objects. They control allocation
 and deallocation of these objects through constructors, destructors,
 insert and erase operations.
 All of the complexity requirements in this Clause are stated solely in
+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:containers.container.requirements]],
 [[tab:containers.reversible.requirements]], and
 [[tab:containers.optional.operations]] `X` denotes a container class
 containing objects of type `T`, `a` and `b` denote values of type `X`,
 `u` denotes an identifier, `r` denotes a non-const value of type `X`,
 and `rv` denotes a non-const rvalue of type `X`.
 Those entries marked “(Note A)” or “(Note B)” have linear complexity for
 `array` and have constant complexity for all other standard containers.
+[*Note 2*: The algorithm `equal()` is defined in Clause
+[[algorithms]]. — *end note*]
 The member function `size()` returns the number of elements in the
 container. The number of elements is defined by the rules of
 constructors, inserts, and erases.
 `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
 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*]
+Copy constructors for these container types obtain an allocator by
+calling
 `allocator_traits<allocator_type>::select_on_container_copy_construction`
 on the allocator belonging to the container being copied. Move
 constructors obtain an allocator by move construction from the allocator
 belonging to the container being moved. Such move construction of the
 allocator shall not exit via an exception. All other constructors for
+these container types take a `const allocator_type&` argument.
+[*Note 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.
 - 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
 container.
+A *contiguous container* is a container that supports random access
+iterators ([[random.access.iterators]]) and whose member types
+`iterator` and `const_iterator` are contiguous iterators (
+[[iterator.requirements.general]]).
 Table  [[tab:containers.optional.operations]] lists operations that are
 provided for some types of containers but not others. Those containers
 for which the listed operations are provided shall implement the
 semantics described in Table  [[tab:containers.optional.operations]]
 unless otherwise stated.
+[*Note 6*: The algorithm `lexicographical_compare()` is defined in
+Clause  [[algorithms]]. — *end note*]
+All of the containers defined in this Clause and in  [[basic.string]]
 except `array` meet the additional requirements of an allocator-aware
 container, as described in Table  [[tab:containers.allocatoraware]].
+Given an allocator type `A` and given a container type `X` having a
+`value_type` identical to `T` and an `allocator_type` identical to
+`allocator_traits<A>::rebind_alloc<T>` and given an lvalue `m` of type
+`A`, a pointer `p` of type `T*`, an expression `v` of type (possibly
+`const`) `T`, and an rvalue `rv` of type `T`, the following terms are
+defined. If `X` is not allocator-aware, the terms below are defined as
+if `A` were `allocator<T>` — no allocator object needs to be created and
+user specializations of `allocator<T>` are not instantiated:
 - `T` is *`DefaultInsertable` into `X`* means that the following
   expression is well-formed:
   ``` cpp
   allocator_traits<A>::construct(m, p)
   allocator_traits<A>::construct(m, p, rv)
   ```
   and its evaluation causes the following postcondition to hold: The
   value of `*p` is equivalent to the value of `rv` before the
+  evaluation.
+  \[*Note 7*: `rv` remains a valid object. Its state is
+  unspecified — *end note*]
 - `T` is *`CopyInsertable` into `X`* means that, in addition to `T`
   being `MoveInsertable` into `X`, the following expression is
   well-formed:
   ``` cpp
   allocator_traits<A>::construct(m, p, v)
   well-formed:
   ``` cpp
   allocator_traits<A>::destroy(m, p)
   ```
+[*Note 8*: A container calls
+`allocator_traits<A>::construct(m, p, args)` to construct an element at
+`p` using `args`, with `m == get_allocator()`. The default `construct`
+in `allocator` will call `::new((void*)p) T(args)`, but specialized
+allocators may choose a different definition. — *end note*]
 In Table  [[tab:containers.allocatoraware]], `X` denotes an
 allocator-aware container class with a `value_type` of `T` using
 allocator of type `A`, `u` denotes a variable, `a` and `b` denote
 non-const lvalues of type `X`, `t` denotes an lvalue or a const rvalue
 of type `X`, `rv` denotes a non-const rvalue of type `X`, and `m` is a
 value of type `A`.
+The behavior of certain container member functions and deduction guides
+depends on whether types qualify as input iterators or allocators. The
+extent to which an implementation determines that a type cannot be an
+input iterator is unspecified, except that as a minimum integral types
+shall not qualify as input iterators. Likewise, the extent to which an
+implementation determines that a type cannot be an allocator is
+unspecified, except that as a minimum a type `A` shall not qualify as an
+allocator unless it satisfies both of the following conditions:
+- The *qualified-id* `A::value_type` is valid and denotes a type (
+  [[temp.deduct]]).
+- The expression `declval<A&>().allocate(size_t{})` is well-formed when
+  treated as an unevaluated operand.
 ### Container data races <a id="container.requirements.dataraces">[[container.requirements.dataraces]]</a>
 For purposes of avoiding data races ([[res.on.data.races]]),
 implementations shall consider the following functions to be `const`:
 `begin`, `end`, `rbegin`, `rend`, `front`, `back`, `data`, `find`,
 `lower_bound`, `upper_bound`, `equal_range`, `at` and, except in
 associative or unordered associative containers, `operator[]`.
+Notwithstanding  [[res.on.data.races]], implementations are required to
+avoid data races when the contents of the contained object in different
+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
 of choice when most insertions and deletions take place at the beginning
 or at the end of the sequence.
 In Tables  [[tab:containers.sequence.requirements]] and
 [[tab:containers.sequence.optional]], `X` denotes a sequence container
+class, `a` denotes a value of type `X` containing elements of type `T`,
+`u` denotes the name of a variable being declared, `A` denotes
+`X::allocator_type` if the *qualified-id* `X::allocator_type` is valid
+and denotes a type ([[temp.deduct]]) and `allocator<T>` if it doesn’t,
+`i` and `j` denote iterators satisfying input iterator requirements and
+refer to elements implicitly convertible to `value_type`, `[i, j)`
+denotes a valid range, `il` designates an object of type
+`initializer_list<value_type>`, `n` denotes a value of type
+`X::size_type`, `p` denotes a valid constant iterator to `a`, `q`
+denotes a valid dereferenceable constant iterator to `a`, `[q1, q2)`
+denotes a valid range of constant iterators in `a`, `t` denotes an
+lvalue or a const rvalue of `X::value_type`, and `rv` denotes a
+non-const rvalue of `X::value_type`. `Args` denotes a template parameter
+pack; `args` denotes a function parameter pack with the pattern
+`Args&&`.
 The complexities of the expressions are sequence dependent.
 The iterator returned from `a.insert(p, t)` points to the copy of `t`
 inserted into `a`.
 The iterator returned from `a.insert(p, rv)` points to the copy of `rv`
 inserted into `a`.
 - If the constructor
   ``` cpp
   template <class InputIterator>
     X(InputIterator first, InputIterator last,
+ const allocator_type& alloc = allocator_type());
   ```
   is called with a type `InputIterator` that does not qualify as an
   input iterator, then the constructor shall not participate in overload
   resolution.
 - If the member functions of the forms:
   ``` cpp
+  template <class InputIterator>
+    return-type F(const_iterator p,
+                  InputIterator first, InputIterator last);       // such as insert
+  template <class InputIterator>
+    return-type F(InputIterator first, InputIterator last);       // such as append, assign
+  template <class InputIterator>
+    return-type F(const_iterator i1, const_iterator i2,
+                  InputIterator first, InputIterator last);       // such as replace
   ```
   are called with a type `InputIterator` that does not qualify as an
   input iterator, then these functions shall not participate in overload
   resolution.
+- A deduction guide for a sequence container shall not participate in
+  overload resolution if it has an `InputIterator` template parameter
+  and a type that does not qualify as an input iterator is deduced for
+  that parameter, or if it has an `Allocator` template parameter and a
+  type that does not qualify as an allocator is deduced for that
+  parameter.
 Table  [[tab:containers.sequence.optional]] lists operations that are
 provided for some types of sequence containers but not others. An
 implementation shall provide these operations for all container types
 shown in the “container” column, and shall implement them so as to take
 amortized constant time.
 The member function `at()` provides bounds-checked access to container
 elements. `at()` throws `out_of_range` if `n >= a.size()`.
+### Node handles <a id="container.node">[[container.node]]</a>
+#### `node_handle` overview <a id="container.node.overview">[[container.node.overview]]</a>
+A *node handle* is an object that accepts ownership of a single element
+from an associative container ([[associative.reqmts]]) or an unordered
+associative container ([[unord.req]]). It may be used to transfer that
+ownership to another container with compatible nodes. Containers with
+compatible nodes have the same node handle type. Elements may be
+transferred in either direction between container types in the same row
+of Table  [[tab:containers.node.compat]].
+**Table: Container types with compatible nodes** <a id="tab:containers.node.compat">[tab:containers.node.compat]</a>
+|                                  |                                       |
+| -------------------------------- | ------------------------------------- |
+| `map<K, T, C1, A>`               | `map<K, T, C2, A>`                    |
+| `map<K, T, C1, A>`               | `multimap<K, T, C2, A>`               |
+| `set<K, C1, A>`                  | `set<K, C2, A>`                       |
+| `set<K, C1, A>`                  | `multiset<K, C2, A>`                  |
+| `unordered_map<K, T, H1, E1, A>` | `unordered_map<K, T, H2, E2, A>`      |
+| `unordered_map<K, T, H1, E1, A>` | `unordered_multimap<K, T, H2, E2, A>` |
+| `unordered_set<K, H1, E1, A>`    | `unordered_set<K, H2, E2, A>`         |
+| `unordered_set<K, H1, E1, A>`    | `unordered_multiset<K, H2, E2, A>`    |
+If a node handle is not empty, then it contains an allocator that is
+equal to the allocator of the container when the element was extracted.
+If a node handle is empty, it contains no allocator.
+Class `node_handle` is for exposition only. An implementation is
+permitted to provide equivalent functionality without providing a class
+with this name.
+If a user-defined specialization of `pair` exists for
+`pair<const Key, T>` or `pair<Key, T>`, where `Key` is the container’s
+`key_type` and `T` is the container’s `mapped_type`, the behavior of
+operations involving node handles is undefined.
+``` cpp
+template<unspecified>
+  class node_handle {
+  public:
+    // These type declarations are described in Tables [tab:containers.associative.requirements] and [tab:HashRequirements].
+    using value_type     = see below;   // not present for map containers
+    using key_type       = see below;   // not present for set containers
+    using mapped_type    = see below;   // not present for set containers
+    using allocator_type = see below;
+  private:
+    using container_node_type = unspecified;
+    using ator_traits = allocator_traits<allocator_type>;
+    typename ator_traits::rebind_traits<container_node_type>::pointer ptr_;
+    optional<allocator_type> alloc_;
+  public:
+    constexpr node_handle() noexcept : ptr_(), alloc_() {}
+    ~node_handle();
+    node_handle(node_handle&&) noexcept;
+    node_handle& operator=(node_handle&&);
+    value_type& value() const;          // not present for map containers
+    key_type& key() const;              // not present for set containers
+    mapped_type& mapped() const;        // not present for set containers
+    allocator_type get_allocator() const;
+    explicit operator bool() const noexcept;
+    bool empty() const noexcept;
+    void swap(node_handle&)
+      noexcept(ator_traits::propagate_on_container_swap::value ||
+               ator_traits::is_always_equal::value);
+    friend void swap(node_handle& x, node_handle& y) noexcept(noexcept(x.swap(y))) {
+      x.swap(y);
+    }
+};
+```
+#### `node_handle` constructors, copy, and assignment <a id="container.node.cons">[[container.node.cons]]</a>
+``` cpp
+node_handle(node_handle&& nh) noexcept;
+```
+*Effects:* Constructs a *`node_handle`* object initializing `ptr_` with
+`nh.ptr_`. Move constructs `alloc_` with `nh.alloc_`. Assigns `nullptr`
+to `nh.ptr_` and assigns `nullopt` to `nh.alloc_`.
+``` cpp
+node_handle& operator=(node_handle&& nh);
+```
+*Requires:* Either `!alloc_`, or
+`ator_traits::propagate_on_container_move_assignment` is `true`, or
+`alloc_ == nh.alloc_`.
+*Effects:*
+- If `ptr_ != nullptr`, destroys the `value_type` subobject in the
+  `container_node_type` object pointed to by `ptr_` by calling
+  `ator_traits::destroy`, then deallocates `ptr_` by calling
+  `ator_traits::rebind_traits<container_node_type>::deallocate`.
+- Assigns `nh.ptr_` to `ptr_`.
+- If `!alloc` or `ator_traits::propagate_on_container_move_assignment`
+  is `true`, move assigns `nh.alloc_` to `alloc_`.
+- Assigns `nullptr` to `nh.ptr_` and assigns `nullopt` to `nh.alloc_`.
+*Returns:* `*this`.
+*Throws:* Nothing.
+#### `node_handle` destructor <a id="container.node.dtor">[[container.node.dtor]]</a>
+``` cpp
+~node_handle();
+```
+*Effects:* If `ptr_ != nullptr`, destroys the `value_type` subobject in
+the `container_node_type` object pointed to by `ptr_` by calling
+`ator_traits::destroy`, then deallocates `ptr_` by calling
+`ator_traits::rebind_traits<container_node_type>::deallocate`.
+#### `node_handle` observers <a id="container.node.observers">[[container.node.observers]]</a>
+``` cpp
+value_type& value() const;
+```
+*Requires:* `empty() == false`.
+*Returns:* A reference to the `value_type` subobject in the
+`container_node_type` object pointed to by `ptr_`.
+*Throws:* Nothing.
+``` cpp
+key_type& key() const;
+```
+*Requires:* `empty() == false`.
+*Returns:* A non-const reference to the `key_type` member of the
+`value_type` subobject in the `container_node_type` object pointed to by
+`ptr_`.
+*Throws:* Nothing.
+*Remarks:* Modifying the key through the returned reference is
+permitted.
+``` cpp
+mapped_type& mapped() const;
+```
+*Requires:* `empty() == false`.
+*Returns:* A reference to the `mapped_type` member of the `value_type`
+subobject in the `container_node_type` object pointed to by `ptr_`.
+*Throws:* Nothing.
+``` cpp
+allocator_type get_allocator() const;
+```
+*Requires:* `empty() == false`.
+*Returns:* `*alloc_`.
+*Throws:* Nothing.
+``` cpp
+explicit operator bool() const noexcept;
+```
+*Returns:* `ptr_ != nullptr`.
+``` cpp
+bool empty() const noexcept;
+```
+*Returns:* `ptr_ == nullptr`.
+#### `node_handle` modifiers <a id="container.node.modifiers">[[container.node.modifiers]]</a>
+``` cpp
+void swap(node_handle& nh)
+  noexcept(ator_traits::propagate_on_container_swap::value ||
+           ator_traits::is_always_equal::value);
+```
+*Requires:* `!alloc_`, or `!nh.alloc_`, or
+`ator_traits::propagate_on_container_swap` is `true`, or
+`alloc_ == nh.alloc_`.
+*Effects:* Calls `swap(ptr_, nh.ptr_)`. If `!alloc_`, or `!nh.alloc_`,
+or `ator_traits::propagate_on_container_swap` is `true` calls
+`swap(alloc_, nh.alloc_)`.
+### Insert return type <a id="container.insert.return">[[container.insert.return]]</a>
+The associative containers with unique keys and the unordered containers
+with unique keys have a member function `insert` that returns a nested
+type `insert_return_type`. That return type is a specialization of the
+type specified in this subclause.
+``` cpp
+template <class Iterator, class NodeType>
+struct INSERT_RETURN_TYPE
+{
+  Iterator position;
+  bool     inserted;
+  NodeType node;
+};
+```
+The name `INSERT_RETURN_TYPE` is exposition only. `INSERT_RETURN_TYPE`
+has the template parameters, data members, and special members specified
+above. It has no base classes or members other than those specified.
 ### Associative containers <a id="associative.reqmts">[[associative.reqmts]]</a>
 Associative containers provide fast retrieval of data based on keys. The
 library provides four basic kinds of associative containers: `set`,
 `multiset`, `map` and `multimap`.
 of an associative container is of the bidirectional iterator category.
 For associative containers where the value type is the same as the key
 type, both `iterator` and `const_iterator` are constant iterators. It is
 unspecified whether or not `iterator` and `const_iterator` are the same
+type.
+[*Note 1*: `iterator` and `const_iterator` have identical semantics in
+this case, and `iterator` is convertible to `const_iterator`. Users can
+avoid violating the one-definition rule by always using `const_iterator`
+in their function parameter lists. — *end note*]
 The associative containers meet all the requirements of Allocator-aware
 containers ([[container.requirements.general]]), except that for `map`
 and `multimap`, the requirements placed on `value_type` in Table
 [[tab:containers.container.requirements]] apply instead to `key_type`
+and `mapped_type`.
+[*Note 2*: For example, in some cases `key_type` and `mapped_type` are
+required to be `CopyAssignable` even though the associated `value_type`,
+`pair<const key_type, mapped_type>`, is not
+`CopyAssignable`. — *end note*]
 In Table  [[tab:containers.associative.requirements]], `X` denotes an
+associative container class, `a` denotes a value of type `X`, `a2`
+denotes a value of a type with nodes compatible with type `X` (Table
+[[tab:containers.node.compat]]), `b` denotes a possibly `const` value of
+type `X`, `u` denotes the name of a variable being declared, `a_uniq`
+denotes a value of type `X` when `X` supports unique keys, `a_eq`
+denotes a value of type `X` when `X` supports multiple keys, `a_tran`
+denotes a possibly `const` value of type `X` when the *qualified-id*
+`X::key_compare::is_transparent` is valid and denotes a type (
+[[temp.deduct]]), `i` and `j` satisfy input iterator requirements and
+refer to elements implicitly convertible to `value_type`, \[`i`, `j`)
+denotes a valid range, `p` denotes a valid constant iterator to `a`, `q`
+denotes a valid dereferenceable constant iterator to `a`, `r` denotes a
+valid dereferenceable iterator to `a`, `[q1, q2)` denotes a valid range
+of constant iterators in `a`, `il` designates an object of type
+`initializer_list<value_type>`, `t` denotes a value of type
+`X::value_type`, `k` denotes a value of type `X::key_type` and `c`
+denotes a possibly `const` value of type `X::key_compare`; `kl` is a
+value such that `a` is partitioned ([[alg.sorting]]) with respect to
 `c(r, kl)`, with `r` the key value of `e` and `e` in `a`; `ku` is a
 value such that `a` is partitioned with respect to `!c(ku, r)`; `ke` is
 a value such that `a` is partitioned with respect to `c(r, ke)` and
 `!c(ke, r)`, with `c(r, ke)` implying `!c(ke, r)`. `A` denotes the
+storage allocator used by `X`, if any, or `allocator<X::value_type>`
+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
+pointers to an element obtained while it is owned by a `node_type` are
+invalidated if the element is successfully inserted.
 The fundamental property of iterators of associative containers is that
 they iterate through the containers in the non-descending order of keys
 where non-descending is defined by the comparison that was used to
 construct them. For any two dereferenceable iterators `i` and `j` such
+that distance from `i` to `j` is positive, the following condition
+holds:
 ``` cpp
 value_comp(*j, *i) == false
 ```
 For associative containers with unique keys the stronger condition
+holds:
 ``` cpp
+value_comp(*i, *j) != false
 ```
 When an associative container is constructed by passing a comparison
 object the container shall not store a pointer or reference to the
 passed object, even if that object is passed by reference. When an
 object from the container being copied, as if that comparison object had
 been passed to the target container in its constructor.
 The member function templates `find`, `count`, `lower_bound`,
 `upper_bound`, and `equal_range` shall not participate in overload
+resolution unless the *qualified-id* `Compare::is_transparent` is valid
 and denotes a type ([[temp.deduct]]).
+A deduction guide for an associative container shall not participate in
+overload resolution if any of the following are true:
+- It has an `InputIterator` template parameter and a type that does not
+  qualify as an input iterator is deduced for that parameter.
+- It has an `Allocator` template parameter and a type that does not
+  qualify as an allocator is deduced for that parameter.
+- It has a `Compare` template parameter and a type that qualifies as an
+  allocator is deduced for that parameter.
 #### Exception safety guarantees <a id="associative.reqmts.except">[[associative.reqmts.except]]</a>
 For associative containers, no `clear()` function throws an exception.
 `erase(k)` does not throw an exception unless that exception is thrown
 by the container’s `Compare` object (if any).
 the container.
 Two values `k1` and `k2` of type `Key` are considered equivalent if the
 container’s key equality predicate returns `true` when passed those
 values. If `k1` and `k2` are equivalent, the container’s hash function
+shall return the same value for both.
+[*Note 1*: Thus, when an unordered associative container is
+instantiated with a non-default `Pred` parameter it usually needs a
+non-default `Hash` parameter as well. — *end note*]
+For any two keys `k1` and `k2` in the same container, calling
+`pred(k1, k2)` shall always return the same value. For any key `k` in a
+container, calling `hash(k)` shall always return the same value.
 An unordered associative container supports *unique keys* if it may
 contain at most one element for each key. Otherwise, it supports
 *equivalent keys*. `unordered_set` and `unordered_map` support unique
 keys. `unordered_multiset` and `unordered_multimap` support equivalent
 keys. In containers that support equivalent keys, elements with
 equivalent keys are adjacent to each other in the iteration order of the
 container. Thus, although the absolute order of elements in an unordered
 container is not specified, its elements are grouped into
+*equivalent-key groups* such that all elements of each group have
 equivalent keys. Mutating operations on unordered containers shall
 preserve the relative order of elements within each equivalent-key group
 unless otherwise specified.
 For `unordered_set` and `unordered_multiset` the value type is the same
 as the key type. For `unordered_map` and `unordered_multimap` it is
+`pair<const Key,
 T>`.
 For unordered containers where the value type is the same as the key
 type, both `iterator` and `const_iterator` are constant iterators. It is
 unspecified whether or not `iterator` and `const_iterator` are the same
+type.
+[*Note 2*: `iterator` and `const_iterator` have identical semantics in
+this case, and `iterator` is convertible to `const_iterator`. Users can
+avoid violating the one-definition rule by always using `const_iterator`
+in their function parameter lists. — *end note*]
 The elements of an unordered associative container are organized into
 *buckets*. Keys with the same hash code appear in the same bucket. The
 number of buckets is automatically increased as elements are added to an
 unordered associative container, so that the average number of elements
 The unordered associative containers meet all the requirements of
 Allocator-aware containers ([[container.requirements.general]]), except
 that for `unordered_map` and `unordered_multimap`, the requirements
 placed on `value_type` in Table
 [[tab:containers.container.requirements]] apply instead to `key_type`
+and `mapped_type`.
+[*Note 3*: For example, `key_type` and `mapped_type` are sometimes
+required to be `CopyAssignable` even though the associated `value_type`,
+`pair<const key_type, mapped_type>`, is not
+`CopyAssignable`. — *end note*]
+In Table  [[tab:HashRequirements]]: `X` denotes an unordered associative
+container class, `a` denotes a value of type `X`, `a2` denotes a value
+of a type with nodes compatible with type `X` (Table
+[[tab:containers.node.compat]]), `b` denotes a possibly const value of
+type `X`, `a_uniq` denotes a value of type `X` when `X` supports unique
+keys, `a_eq` denotes a value of type `X` when `X` supports equivalent
+keys, `i` and `j` denote input iterators that refer to `value_type`,
+`[i, j)` denotes a valid range, `p` and `q2` denote valid constant
+iterators to `a`, `q` and `q1` denote valid dereferenceable constant
+iterators to `a`, `r` denotes a valid dereferenceable iterator to `a`,
+`[q1, q2)` denotes a valid range in `a`, `il` denotes a value of type
+`initializer_list<value_type>`, `t` denotes a value of type
+`X::value_type`, `k` denotes a value of type `key_type`, `hf` denotes a
+possibly const value of type `hasher`, `eq` denotes a possibly const
+value of type `key_equal`, `n` denotes a value of type `size_type`, `z`
+denotes a value of type `float`, and `nh` denotes a non-const rvalue of
+type `X::node_type`.
 Two unordered containers `a` and `b` compare equal if
 `a.size() == b.size()` and, for every equivalent-key group \[`Ea1`,
 `Ea2`) obtained from `a.equal_range(Ea1)`, there exists an
 equivalent-key group \[`Eb1`, `Eb2`) obtained from `b.equal_range(Ea1)`,
 such that `is_permutation(Ea1, Ea2, Eb1, Eb2)` returns `true`. For
 `unordered_set` and `unordered_map`, the complexity of `operator==`
 (i.e., the number of calls to the `==` operator of the `value_type`, to
+the predicate returned by `key_eq()`, and to the hasher returned by
 `hash_function()`) is proportional to N in the average case and to N² in
 the worst case, where N is a.size(). For `unordered_multiset` and
 `unordered_multimap`, the complexity of `operator==` is proportional to
 $\sum E_i^2$ in the average case and to N² in the worst case, where N is
 `a.size()`, and Eᵢ is the size of the iᵗʰ equivalent-key group in `a`.
 `unordered_multiset` and `unordered_multimap` becomes proportional to N
 (but worst-case complexity remains 𝑂(N^2), e.g., for a pathologically
 bad hash function). The behavior of a program that uses `operator==` or
 `operator!=` on unordered containers is undefined unless the `Hash` and
 `Pred` function objects respectively have the same behavior for both
+containers and the equality comparison function for `Key` is a
 refinement[^1] of the partition into equivalent-key groups produced by
 `Pred`.
 The iterator types `iterator` and `const_iterator` of an unordered
 associative container are of at least the forward iterator category. For
 unordered associative containers where the key type and value type are
+the same, both `iterator` and `const_iterator` are constant iterators.
 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.
+A deduction guide for an unordered associative container shall not
+participate in overload resolution if any of the following are true:
+- It has an `InputIterator` template parameter and a type that does not
+  qualify as an input iterator is deduced for that parameter.
+- It has an `Allocator` template parameter and a type that does not
+  qualify as an allocator is deduced for that parameter.
+- It has a `Hash` template parameter and an integral type or a type that
+  qualifies as an allocator is deduced for that parameter.
+- It has a `Pred` template parameter and a type that qualifies as an
+  allocator is deduced for that parameter.
 #### Exception safety guarantees <a id="unord.req.except">[[unord.req.except]]</a>
 For unordered associative containers, no `clear()` function throws an
 exception. `erase(k)` does not throw an exception unless that exception
 is thrown by the container’s `Hash` or `Pred` object (if any).
 `insert` or `emplace` function inserting a single element, the insertion
 has no effect.
 For unordered associative containers, no `swap` function throws an
 exception unless that exception is thrown by the swap of the container’s
+`Hash` or `Pred` object (if any).
 For unordered associative containers, if an exception is thrown from
 within a `rehash()` function other than by the container’s hash function
 or comparison function, the `rehash()` function has no effect.

Diff to HTML by rtfpessoa