11

Is there a reason for missing transparent (template <class K> at(K&& key);) in std::map?

Community
  • 1
  • 1
bobah
  • 18,364
  • 2
  • 37
  • 70

2 Answers2

11

My guess is that std::map::at() must be a "bounds-checked" version of std::map::operator[](). Providing a transparent version of std::map::operator[]() imposes an additional requirement on std::map::key_type and the query key type K - if the query key is not in the map, it must be inserted (with default constructed value), which means that std::map::key_type must be constructible from the query key type.

Leon
  • 31,443
  • 4
  • 72
  • 97
  • Not sure if I buy this argument. If the type is convertible, it is the same as being constructible from it. – SergeyA Nov 23 '16 at 15:20
  • 6
    @SergeyA The two types are not required to be convertible - they are only required to be comparable through a transparent comparator. – Leon Nov 23 '16 at 15:22
  • 5
    this is indeed correct! I would leave my comment there for future readers, but it's logically retracted. – SergeyA Nov 23 '16 at 15:26
  • 3
    Also, unlike the homogeneous case, there's no requirement that a heterogeneous key compares equivalent to at most one key in the map. What do you return if more than one key is a match? – T.C. Nov 24 '16 at 09:25
  • 1
    @T.C. The same argument could be made for `find`, but there's a transparent `find`. – krzaq Nov 24 '16 at 11:31
  • 4
    @krzaq except that `find` is an established operation for multimaps too. – T.C. Nov 24 '16 at 11:33
  • @T.C. and `at` is an established non-option for multimaps. Okay, makes sense now, thanks :) – krzaq Nov 24 '16 at 11:34
  • This means one has to use `find` instead of `at` on a `std::map` using a `std::string_view` key if they want to avoid constructing a temporary `std::string` for the access. Kinda sucks. – Emile Cormier Feb 02 '23 at 19:59
  • I think @T.C. 's comment about multiple possible matches should be the answer, unless someone else is privy to the Committee's rationale for this. – Emile Cormier Feb 02 '23 at 20:30
  • 1
    *...which means that std::map::key_type must be constructible from the the query key type.* - But that is not the case for `at` which never constructs map elements. – Emile Cormier Feb 02 '23 at 20:35
3

P2363 proposes to add a heterogenous key overloads for at, as well as try_emplace, insert_or_assign, operator[], insert and bucket (the latter for unordered maps). It missed inclusion into C++23 and is marked as pending for C++26.

A summary of a review conducted on P2363 can be found here on Github. Sorry, I don't know how to find the original review; it might not even be publicly available.

In that review summary, there is this comment:

Currently, for heterogeneous lookup, the unique-key associative containers do not require that there is at most one match ...

I think the paper should discuss what happens in such cases, particularly for insert_or_assign, operator[], and at (and what try_emplace returns on failure)

I believe that comment answers why a heteregenous overload was not provided for at() for C++14 or C++17.

My conclusions (which jives with T.C.'s comments in the other answer):

Heterogenous lookups for std::map currently do not require that there be at most one match. For the at() function, such lookups would have to either:

  • be constrained to 0..1 matches, or,
  • access the first element that meets the criteria for key equivalence (or throw if none found).

There may not have been consensus on what the behavior should be, which may be why at() was left out of the proposals that introduced heterogenous keys in C++14 and C++17. Or perhaps they felt that at is semantically only meaningful for accessing a unique element without ambiguity (the reason why there's no at in multimaps).

Note that there's no way to check at compile-time whether a heterogeneous key matches one element at most.

For reference, this is the proposal that introduced heterogeneous keys for C++14: N3657 Adding heterogeneous comparison lookup to associative containers. There's no mention of at() in it.

This is the proposal that introduced heterogenous lookups for unordered containers in C++20: P0919 Heterogeneous lookup for unordered containers.

This is the proposal that introduced heterogenous key for erasure: P2077 Heterogeneous erasure overloads for associative containers, which is marked as approved for C++23.

Emile Cormier
  • 28,391
  • 15
  • 94
  • 122