On Mon, May 27, 2019 at 11:19 AM Boyarinov, Konstantin via Std-Proposals <std-proposals@lists.isocpp.org> 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");
    m.erase(it);

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;

HTH,
–Arthur