This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of New status.

### 3227. Ambiguity issue for `extract` in ordered and unordered associative containers

Section: 24.2.7 [associative.reqmts], 24.2.8 [unord.req] Status: New Submitter: Konstantin Boyarinov Opened: 2019-06-25 Last modified: 2022-04-24

Priority: 3

View other active issues in [associative.reqmts].

View all other issues in [associative.reqmts].

View all issues with New status.

Discussion:

Ordered and unordered associative containers in C++14 contained an issue, which caused an ambiguity while invoking `std::map::erase` when `key_type` of the map can be constructed from the iterator. In this case both overloads `erase(const key_type&)` and `erase(const_iterator)` could be chosen.

The issue LWG 2059 was reported and resolved in C++17 by adding an extra overload for `erase` in ordered and unordered associative containers which accepts `iterator` as an argument.

C++17 also introduced new functionality for splicing ordered and unordered maps and sets. One of the extensions allows to extract a node from the container by passing either `key_type&` or `const_iterator` to the `extract()` member function:

>     node_type extract(const key_type& x);
>     node_type extract(const_iterator position);

Providing these two `extract` overloads causes the same problem as for `erase`. Consider the following example:

>     #include <map>
>     #include <string>

>     struct Key
>     {
>       template <typename T>
>       Key(const T&) {}
>     };

>     bool operator<(const Key&, const Key&) { return false; }

>     int main()
>     {
>       using map_type = std::map<Key, std::string>;

>       map_type m({ {Key(1), "a"}, {Key(2), "b"} });
>       map_type::iterator it = m.begin();
>       auto nh = m.extract(it);
>     }

In this case, call to `extract()` is ambiguous, because the overloads which accept `const_iterator` and `key_type` are equally good matches for the argument `it`.

Consequently, this issue can be resolved in the same way as for `std::map::erase` by adding an overload for `extract` which accepts `iterator` as an argument.

[2019-07 Issue Prioritization]

Priority to 3 after discussion on the reflector.

Previous resolution [SUPERSEDED]:

> This wording is relative to N4820.

> 1. Modify [tab:container.assoc.req], Table 69 — "Associative container requirements", as indicated:

>    > Table 69 — Associative container requirements (in addition to container) [tab:container.assoc.req]
>    > Expression | Return type | Assertion/note pre-/post-condition | Complexity
>    > --- | --- | --- | ---
>    > `…`
>    > `a.extract(q)` | `node_type` | Effects: Removes the element pointed to by `q`. Returns: A `node_type` owning that element. | amortized constant
>    > `a.extract(r)` | `node_type` | Effects: Removes the element pointed to by `r`. Returns: A `node_type` owning that element. | amortized constant
>    > `…`

> 2. Modify [tab:container.assoc.req], Table 70 — "Unordered associative container requirements", as indicated:

>    > Table 70 — Unordered associative container requirements (in addition to container) [tab:container.hash.req]
>    > Expression | Return type | Assertion/note pre-/post-condition | Complexity
>    > --- | --- | --- | ---
>    > `…`
>    > `a.extract(q)` | `node_type` | Effects: Removes the element pointed to by `q`. Returns: A `node_type` owning that element. | Average case `𝒪(1)`, worst case `𝒪(a.size())`.
>    > `a.extract(r)` | `node_type` | Effects: Removes the element pointed to by `r`. Returns: A `node_type` owning that element. | Average case `𝒪(1)`, worst case `𝒪(a.size())`.
>    > `…`

> 3. Modify 24.4.4.1 [map.overview], class template `map` synopsis, as indicated:

>    >     […]
>    >     node_type extract(iterator position);
>    >     node_type extract(const_iterator position);
>    >     node_type extract(const key_type& x);
>    >     […]

> 4. Modify 24.4.5.1 [multimap.overview], class template `multimap` synopsis, as indicated:

>    >     […]
>    >     node_type extract(iterator position);
>    >     node_type extract(const_iterator position);
>    >     node_type extract(const key_type& x);
>    >     […]

> 5. Modify 24.4.6.1 [set.overview], class template `set` synopsis, as indicated:

>    >     […]
>    >     node_type extract(iterator position);
>    >     node_type extract(const_iterator position);
>    >     node_type extract(const key_type& x);
>    >     […]

> 6. Modify 24.4.7.1 [multiset.overview], class template `multiset` synopsis, as indicated:

>    >     […]
>    >     node_type extract(iterator position);
>    >     node_type extract(const_iterator position);
>    >     node_type extract(const key_type& x);
>    >     […]

> 7. Modify 24.5.4.1 [unord.map.overview], class template `unordered_map` synopsis, as indicated:

>    >     […]
>    >     node_type extract(iterator position);
>    >     node_type extract(const_iterator position);
>    >     node_type extract(const key_type& x);
>    >     […]

> 8. Modify 24.5.5.1 [unord.multimap.overview], class template `unordered_multimap` synopsis, as indicated:

>    >     […]
>    >     node_type extract(iterator position);
>    >     node_type extract(const_iterator position);
>    >     node_type extract(const key_type& x);
>    >     […]

> 9. Modify 24.5.6.1 [unord.set.overview], class template `unordered_set` synopsis, as indicated:

>    >     […]
>    >     node_type extract(iterator position);
>    >     node_type extract(const_iterator position);
>    >     node_type extract(const key_type& x);
>    >     […]

> 10. Modify 24.5.7.1 [unord.multiset.overview], class template `unordered_multiset` synopsis, as indicated:

>     >     […]
>     >     node_type extract(iterator position);
>     >     node_type extract(const_iterator position);
>     >     node_type extract(const key_type& x);
>     >     […]

[2022-04-24; Daniel rebases wording on N4910]

Proposed resolution:

This wording is relative to N4910.

1. Modify 24.2.7.1 [associative.reqmts.general] as indicated:

   >     a.extract(q)

   > > -108- Result: `node_type`

   > > -109- Effects: Removes the element pointed to by `q`.

   > > -110- Returns: A `node_type` owning that element.

   > > -111- Complexity: Amortized constant.

   >     a.extract(r)

   > > -?- Result: `node_type`

   > > -?- Effects: Removes the element pointed to by `r`.

   > > -?- Returns: A `node_type` owning that element.

   > > -?- Complexity: Amortized constant.

2. Modify 24.2.8.1 [unord.req.general] as indicated:

   >     a.extract(q)

   > > -141- Result: `node_type`

   > > -142- Effects: Removes the element pointed to by `q`.

   > > -143- Returns: A `node_type` owning that element.

   > > -144- Complexity: Average case `𝒪(1)`, worst case `𝒪(a.size())`.

   >     a.extract(r)

   > > -?- Result: `node_type`

   > > -?- Effects: Removes the element pointed to by `r`.

   > > -?- Returns: A `node_type` owning that element.

   > > -?- Complexity: Average case `𝒪(1)`, worst case `𝒪(a.size())`.

3. Modify 24.4.4.1 [map.overview], class template `map` synopsis, as indicated:

   >     […]
   >     node_type extract(iterator position);
   >     node_type extract(const_iterator position);
   >     node_type extract(const key_type& x);
   >     […]

4. Modify 24.4.5.1 [multimap.overview], class template `multimap` synopsis, as indicated:

   >     […]
   >     node_type extract(iterator position);
   >     node_type extract(const_iterator position);
   >     node_type extract(const key_type& x);
   >     […]

5. Modify 24.4.6.1 [set.overview], class template `set` synopsis, as indicated:

   >     […]
   >     node_type extract(iterator position);
   >     node_type extract(const_iterator position);
   >     node_type extract(const key_type& x);
   >     […]

6. Modify 24.4.7.1 [multiset.overview], class template `multiset` synopsis, as indicated:

   >     […]
   >     node_type extract(iterator position);
   >     node_type extract(const_iterator position);
   >     node_type extract(const key_type& x);
   >     […]

7. Modify 24.5.4.1 [unord.map.overview], class template `unordered_map` synopsis, as indicated:

   >     […]
   >     node_type extract(iterator position);
   >     node_type extract(const_iterator position);
   >     node_type extract(const key_type& x);
   >     […]

8. Modify 24.5.5.1 [unord.multimap.overview], class template `unordered_multimap` synopsis, as indicated:

   >     […]
   >     node_type extract(iterator position);
   >     node_type extract(const_iterator position);
   >     node_type extract(const key_type& x);
   >     […]

9. Modify 24.5.6.1 [unord.set.overview], class template `unordered_set` synopsis, as indicated:

   >     […]
   >     node_type extract(iterator position);
   >     node_type extract(const_iterator position);
   >     node_type extract(const key_type& x);
   >     […]

10. Modify 24.5.7.1 [unord.multiset.overview], class template `unordered_multiset` synopsis, as indicated:

    >     […]
    >     node_type extract(iterator position);
    >     node_type extract(const_iterator position);
    >     node_type extract(const key_type& x);
    >     […]