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: 23.2.7 [associative.reqmts], 23.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 23.4.3.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 23.4.4.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 23.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 23.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 23.5.3.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 23.5.4.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 23.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 23.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 23.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 23.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 23.4.3.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 23.4.4.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 23.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 23.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 23.5.3.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 23.5.4.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 23.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 23.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);
    […]