Title
Ambiguity issue for extract in ordered and unordered associative containers
Status
new
Section
[associative.reqmts][unord.req]
Submitter
Konstantin Boyarinov

Created on 2019-06-25.00:00:00 last changed 1 month ago

Messages

Date: 2022-04-24.17:52:14

Proposed resolution:

This wording is relative to N4910.

  1. Modify [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 [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 [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 [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 [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 [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 [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 [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 [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 [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);
    […]
    
Date: 2022-04-15.00:00:00

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

Date: 2022-04-24.17:52:14

[ 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 [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 [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 [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 [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 [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 [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 [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 [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);
    […]
    
Date: 2019-06-25.00:00:00

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.

History
Date User Action Args
2022-04-24 17:52:14adminsetmessages: + msg12430
2019-07-23 15:26:26adminsetmessages: + msg10508
2019-06-30 17:22:01adminsetmessages: + msg10468
2019-06-25 00:00:00admincreate