Missing heterogeneous modifiers for `map` and `set`?

[joseph....@gmail.com]

Proposal N3657 added the following heterogeneous lookup functions in the presence of a `Compare::is_transparent` tag:

find
count
lower_bound
upper_bound
equal_range

However, heterogeneous keys are not supported for modifiers. My use case is wanting to use a `string_view` as a key into a `map<string, X>`. For efficiency, I only want a `string` to be constructed if the entry doesn't already exist.

auto count_k_mers(std::string_view s, std::size_t length) {
  std::map<std::string, std::size_t, std::less<>> counts;
  for (std::size_t i = 0; i < s.length() - length + 1; ++i) {
    ++counts[s.substr(i, length)]; // error: no such function `operator[](string_view)`
  }
  return counts;
}

No overload of `operator[]` takes a heterogeneous key, hence the compilation error. The same is true for `try_emplace`:

    ++counts.try_emplace(k_mer).first->second; // error: no such function `try_emplace(string_view)`

I can't use `emplace` naively because that will create a `string` on every call. Instead, I am forced to do something like this:

auto count_k_mers(std::string_view s, std::size_t length) {
  std::map<std::string, std::size_t, std::less<>> counts;
  for (std::size_t i = 0; i < s.length() - length + 1; ++i) {
    auto k_mer = s.substr(i, length);
    auto it = counts.find(k_mer);
    if (it == counts.end()) {
      it = counts.emplace(k_mer, std::size_t()).first;
    }
    ++it->second;
  }
  return counts;
}

This could obviously be optimized by using `lower_bound` and `emplace_hint`, but what are the chances the average user will do this? So why not provide a heterogeneous `operator[]` that gives optimal performance by default?

template <typename K>
T& operator[](K const& k) {
  auto it = lower_bound(k);
  if (it == end() || Compare()(k, it->first)) {
    it = emplace_hint(it, k, T());
  }
  return it->second;
}

Pretty much any function that takes a key could have a heterogeneous overload (`at`, `try_emplace`, `extract`, `erase`). Is there some reason these functions don't exist yet?

[Nicol Bolas]

Well here's one. Currently, heterogeneous lookup requires precisely one thing out of `K`: that `Compare` can compare it to `key_type`.  To implement many of the functions you specify (like `emplace` and the like), `K` now must be convertible to `key_type`. And that's a very different requirement, one that not all heterogeneous lookup types will permit. This is particularly true for `set`s, where the `T` type is usually a much more complex object than `K` (which is why you want heterogeneous lookup in the first place).

Now, you could make it so that these overloads only exist for `K`'s where `is_convertible<K, key_type>` is true. This would be needed for any of the functions that potentially insert a new item.

Indeed, `emplace` doesn't even include `key_type` in its signature; the assumption is that it will always create a `pair<const key_type, T>` from the values. So changing that would require a non-trivial change. `try_emplace` at least has a specific value which is `key_type` that could be augmented with an overload for a generic `K`.

[joseph....@gmail.com]

The requirements for `K` don't have to be the same for every function, so I don't see this as a reason why they shouldn't exist.
 

Now, you could make it so that these overloads only exist for `K`'s where `is_convertible<K, key_type>` is true. This would be needed for any of the functions that potentially insert a new item.

For my use case to be supported, the requirement would have to be `is_constructible_v<key_type, K>` is true. At first glance this seems unwise, as it has the potential to make explicit conversions somewhat more implicit; for example:

int i;
std::map<std::unique_ptr<int>, int> m;
m[&i] = 42; // bad

However, there is still the implicit requirement that `K` be comparable to `key_type`, so this example would still fail as `unique_ptr<T>` is not comparable to `T*`. It works in the `string_view` case because `string` is convertible to `string_view`. I'm not sure why `string_view` is not convertible to `string`. I also note that the following already does work:

m.insert(std::make_pair(&i, 42));

Indeed, `emplace` doesn't even include `key_type` in its signature; the assumption is that it will always create a `pair<const key_type, T>` from the values. So changing that would require a non-trivial change. `try_emplace` at least has a specific value which is `key_type` that could be augmented with an overload for a generic `K`.

 I don't think trying to support this for `emplace` is necessary given the existence of `try_emplace`.

[Thomas Köppe]

I could imagine extending try_emplace to transparent comparators. That was out of scope for N4279 because I wanted to keep it simple. Also, transparent operations are tricky for the hash containers, so we'd have to think carefully about that. We'd probably only want to support them in std::map::try_emplace for now.

The fundamental idea of try_emplace is that *no objects* are constructed from the arguments until the lookup has been done. This idea has to exclude things like comparators that take arguments by prvalue, of course, so I suppose you could rephrase the goal to say that no objects are constructed in order to formulate the key lookup expression. And I think that could be consistently extended to a templated key parameter when the comparator is transparent; the key parameter would be a forwarding reference, and no objects would be constructed.

[joseph....@gmail.com]

On Wednesday, 22 March 2017 21:02:05 UTC+8, Thomas Köppe wrote:

I could imagine extending try_emplace to transparent comparators. That was out of scope for N4279 because I wanted to keep it simple. Also, transparent operations are tricky for the hash containers, so we'd have to think carefully about that. We'd probably only want to support them in std::map::try_emplace for now.

The fundamental idea of try_emplace is that *no objects* are constructed from the arguments until the lookup has been done. This idea has to exclude things like comparators that take arguments by prvalue, of course, so I suppose you could rephrase the goal to say that no objects are constructed in order to formulate the key lookup expression. And I think that could be consistently extended to a templated key parameter when the comparator is transparent; the key parameter would be a forwarding reference, and no objects would be constructed.

I agree. So the functions would look like this?

template <typename K, typename... Args>
pair<iterator, bool> try_emplace(K&& k, Args&&... args);


template <typename K>
T& operator[](K&& k);

And would only participate in overload resolution if `is_convertible_v<K&&, key_type>`.