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.
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.
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 … 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()). … 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); […]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); […]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); […]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); […]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); […]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); […]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); […]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.
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.
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()).
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); […]
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); […]
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); […]
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); […]
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); […]
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); […]
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); […]
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); […]