C++ Logo


Advanced search

Re: Heterogeneous erase for associative containers

From: Boyarinov, Konstantin <konstantin.boyarinov_at_[hidden]>
Date: Mon, 27 May 2019 16:15:16 +0000
As I can see, C++17 adds an overload for std::map::erase, which takes an iterator as an argument.
So the addition of template version of std::map::erase would not cause any ambiguities.

However, for std::unordered_map it will be a problem, because an overload with the iterator was not added.

Best regards,
Konstantin Boyarinov

From: Arthur O'Dwyer [mailto:arthur.j.odwyer_at_[hidden]]
Sent: Monday, May 27, 2019 6:45 PM
To: std-proposals_at_lists.isocpp.org
Cc: Boyarinov, Konstantin <konstantin.boyarinov_at_[hidden]>
Subject: Re: [std-proposals] Heterogeneous erase for associative containers

On Mon, May 27, 2019 at 11:19 AM Boyarinov, Konstantin via Std-Proposals <std-proposals_at_[hidden]<mailto:std-proposals_at_[hidden]>> wrote:
Dear Sir or Madam,

We have a question regarding the heterogeneous methods in STL associative containers:
C++14 and C++17 introduced heterogeneous lookup functions (for std::map, std::unordered_map and others).

Heterogeneous lookup for std::unordered_map is not standardized yet. It's likely to come in C++2a. (Mateusz Pusz has an active proposal that was in LWG wording review in Kona.)

These are overloads for find, count and other lookup algorithms, that accepts objects of any type compatible with key_type and only participates in overload resolution if Compare::is_transparent is valid and denotes a type.

But there are no overloads for heterogeneous erase and extract.

Does it make sense to propose adding the following methods to the std::map, std::multimap, std::set, std::multiset, std::unordered_map, std::unordered_multimap, std::unordered_set and std::unordered_multiset?

template <typename K>
size_type erase(const K& x);

template <typename K>
node_type extract(const K& x);
Incidentally, I'm surprised that `extract(const key_type&)` exists — and even exists for std::multimap! That seems strange to me. I would have expected the `extract` taking a `const_iterator` to be the only overload of `extract`.

The existing functions were originally added in http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3465.pdf
That paper has a section on `erase`. The author worried about ambiguity between `erase(const_iterator)` and `erase(const key_type&)`.

That is, if you blindly added an unconstrained `map::erase(const K&)` simply because the comparator was heterogeneous, then

    auto it = m.find("foo");

would stop working, because `it` has type `map::iterator`, which is a better match for `const K&` than for `map::const_iterator`.

Now, of course these member function templates should never have been unconstrained in the first place; but the STL doesn't like constrained templates because they're hard to write.

If you want heterogeneous `erase` or `extract`, you'll have to solve the overload resolution problem above, which probably means you'll have to propose constraining all the heterogeneous member function templates of `set`, `map`, etc. For example,

    template<class K>
    size_type count(const K& key) const;

would have to become something like

    template<class K, class = decltype(declval<const Compare&>()(declval<const Key&>(), declval<const K&>()))>
    size_type count(const K& key) const;


Joint Stock Company Intel A/O
Registered legal address: Krylatsky Hills Business Park,
17 Krylatskaya Str., Bldg 4, Moscow 121614,
Russian Federation

This e-mail and any attachments may contain confidential material for
the sole use of the intended recipient(s). Any review or distribution
by others is strictly prohibited. If you are not the intended
recipient, please contact the sender and delete all copies.

Received on 2019-05-27 11:17:04