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

Files changed (1) hide show

tmp/tmpwbvjh_nc/{from.md → to.md} +134 -65

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

@@ -21,15 +21,16 @@ function and destroyed using 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]] and
-[[tab:containers.reversible.requirements]], `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.
@@ -41,28 +42,44 @@ constructors, inserts, and erases.
 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()`;
 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 their first parameters. 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 an `Allocator&`
-argument ([[allocator.requirements]]), an allocator whose value type is
-the same as the container’s value type. 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
@@ -101,12 +118,13 @@ Unless otherwise specified (see  [[associative.reqmts.except]],
 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()` or `push_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.
@@ -134,29 +152,56 @@ 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 `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>`.)
-- `T` is *`CopyInsertable` into `X`* means that the following expression
-  is well-formed:
   ``` cpp
-  allocator_traits<A>::construct(m, p, v);
   ```
 - `T` is *`MoveInsertable` into `X`* means that the following expression
   is well-formed:
   ``` cpp
-  allocator_traits<A>::construct(m, p, rv);
   ```
 - `T` is *`EmplaceConstructible` into `X` from `args`*, for zero or more
   arguments `args`, means that the following expression is well-formed:
   ``` cpp
-  allocator_traits<A>::construct(m, p, args);
   ```
 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
@@ -164,12 +209,12 @@ 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`, `m` is a value
-of type `A`, and `Q` is an allocator type.
 ### 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`:
@@ -177,11 +222,11 @@ implementations shall consider the following functions to be `const`:
 `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 sequence, 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
@@ -240,12 +285,12 @@ 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, i1)` points to the copy of the
-first element inserted into `a`, or `p` if `i1` 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
@@ -305,12 +350,12 @@ 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 type `T` with the `Key`. The object of type
-`Compare` is called the *comparison object* of a container.
 The phrase “equivalence of keys” means the equivalence relation imposed
 by the comparison and *not* the `operator==` on keys. That is, two keys
 `k1` and `k2` are considered to be equivalent if for the comparison
 object `comp`, `comp(k1, k2) == false && comp(k2, k1) == false`. For any
@@ -323,12 +368,11 @@ The `set` and `map` classes support unique keys; the `multiset` and
 `multimap` classes support equivalent keys. For `multiset` and
 `multimap`, `insert`, `emplace`, and `erase` preserve the relative
 ordering of equivalent elements.
 For `set` and `multiset` the value type is the same as the key type. For
-`map` and `multimap` it is equal to `pair<const Key, T>`. Keys in an
-associative container are immutable.
 `iterator`
 of an associative container is of the bidirectional iterator category.
 For associative containers where the value type is the same as the key
@@ -349,24 +393,31 @@ 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, `u` denotes an identifier,
-`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`. `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
@@ -390,10 +441,15 @@ passed object, even if that object is passed by reference. When an
 associative container is copied, either through a copy constructor or an
 assignment operator, the target container shall then use the comparison
 object from the container being copied, as if that comparison object had
 been passed to the target container in its constructor.
 #### 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).
@@ -425,19 +481,24 @@ function object type `Hash` that meets the `Hash` requirements (
 of type `Key`, and by a binary predicate `Pred` that induces an
 equivalence relation on values of type `Key`. Additionally,
 `unordered_map` and `unordered_multimap` associate an arbitrary *mapped
 type* `T` with the `Key`.
-A hash function is a function object that takes a single argument of
-type `Key` and returns a value of type `std::size_t`.
 Two values `k1` and `k2` of type `Key` are considered equivalent if the
-container’s `key_equal` function object returns `true` when passed those
-values. If `k1` and `k2` are equivalent, the 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.
 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
@@ -453,10 +514,18 @@ 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>`.
 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
 per bucket is kept below a bound. Rehashing invalidates iterators,
@@ -491,15 +560,14 @@ 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 `distance(Ea1, Ea2) == distance(Eb1, Eb2)` and
-`is_permutation(Ea1, Ea2, Eb1)` 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`.
@@ -521,12 +589,13 @@ 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.
 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 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.
 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
+i != j
+i < j
+i <= j
+i >= j
+i > j
+i - j
+```
+where `i` and `j` denote objects of a container’s `iterator` type,
+either or both may be replaced by an object of the container’s
+`const_iterator` type referring to the same element with no change in
+semantics.
 Unless otherwise specified, all containers defined in this clause obtain
 memory using an allocator (see  [[allocator.requirements]]). 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
 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.
 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)
   ```
+- An element of `X` is *default-inserted* if it is initialized by
+  evaluation of the expression
+  ``` cpp
+  allocator_traits<A>::construct(m, p)
+  ```
+  where `p` is the address of the uninitialized storage for the element
+  allocated within `X`.
 - `T` is *`MoveInsertable` into `X`* means that the following expression
   is well-formed:
   ``` cpp
+  allocator_traits<A>::construct(m, p, rv)
   ```
+  and its evaluation causes the following postcondition to hold: The
+  value of `*p` is equivalent to the value of `rv` before the
+  evaluation. 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)
+  ```
+  and its evaluation causes the following postcondition to hold: The
+  value of `v` is unchanged and is equivalent to `*p`.
 - `T` is *`EmplaceConstructible` into `X` from `args`*, for zero or more
   arguments `args`, means that the following expression is well-formed:
   ``` cpp
+  allocator_traits<A>::construct(m, p, args)
+  ```
+- `T` is *`Erasable` from `X`* means that the following expression is
+  well-formed:
+  ``` cpp
+  allocator_traits<A>::destroy(m, p)
   ```
 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
 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`:
 `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
 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
 `multiset`, `map` and `multimap`.
 Each associative container is parameterized on `Key` and an ordering
 relation `Compare` that induces a strict weak ordering (
 [[alg.sorting]]) on elements of `Key`. In addition, `map` and `multimap`
+associate an arbitrary *mapped type* `T` with the `Key`. The object of
+type `Compare` is called the *comparison object* of a container.
 The phrase “equivalence of keys” means the equivalence relation imposed
 by the comparison and *not* the `operator==` on keys. That is, two keys
 `k1` and `k2` are considered to be equivalent if for the comparison
 object `comp`, `comp(k1, k2) == false && comp(k2, k1) == false`. For any
 `multimap` classes support equivalent keys. For `multiset` and
 `multimap`, `insert`, `emplace`, and `erase` preserve the relative
 ordering of equivalent elements.
 For `set` and `multiset` the value type is the same as the key type. For
+`map` and `multimap` it is equal to `pair<const Key, T>`.
 `iterator`
 of an associative container is of the bidirectional iterator category.
 For associative containers where the value type is the same as the key
 `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
 associative container is copied, either through a copy constructor or an
 assignment operator, the target container shall then use the comparison
 object from the container being copied, as if that comparison object had
 been passed to the target container in its constructor.
+The member function templates `find`, `count`, `lower_bound`,
+`upper_bound`, and `equal_range` shall not participate in overload
+resolution unless the qualified-id `Compare::is_transparent` is valid
+and denotes a type ([[temp.deduct]]).
 #### 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).
 of type `Key`, and by a binary predicate `Pred` that induces an
 equivalence relation on values of type `Key`. Additionally,
 `unordered_map` and `unordered_multimap` associate an arbitrary *mapped
 type* `T` with the `Key`.
+The container’s object of type `Hash` — denoted by `hash` — is called
+the *hash function* of the container. The container’s object of type
+`Pred` — denoted by `pred` — is called the *key equality predicate* of
+the container.
 Two values `k1` and `k2` of type `Key` are considered equivalent if the
+container’s key equality predicate returns `true` when passed those
+values. If `k1` and `k2` are equivalent, the container’s hash function
+shall return the same value for both. 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
 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
 per bucket is kept below a bound. Rehashing invalidates iterators,
 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`.
 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

Diff to HTML by rtfpessoa