[associative.reqmts.general]

Files changed (1) hide show

tmp/tmpvk6jkooo/{from.md → to.md} +823 -0

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

	@@ -0,0 +1,823 @@

+#### 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`
+is called the *comparison object* of a container.
+The phrase “equivalence of keys” means the equivalence relation imposed
+by the comparison object. That is, two keys `k1` and `k2` are considered
+to be equivalent if for the comparison object `comp`,
+`comp(k1, k2) == false && comp(k2, k1) == false`.
+[*Note 1*: This is not necessarily the same as the result of
+`k1 == k2`. — *end note*]
+For any two keys `k1` and `k2` in the same container, calling
+`comp(k1, k2)` shall always return the same value.
+An associative container supports *unique keys* if it may contain at
+most one element for each key. Otherwise, it supports *equivalent keys*.
+The `set` and `map` classes support unique keys; the `multiset` and
+`multimap` classes support equivalent keys. For `multiset` and
+`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
+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*]
+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
+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
+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`, `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
+  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.

Diff to HTML by rtfpessoa