On Mon, May 27, 2019 at 11:19 AM Boyarinov, Konstantin via Std-Proposals <
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");
    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