Why no transparent C++1x std::map::at?

Question

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

Delphina

It does not have transparent operator[] either – Xylon

@Slava, but it does have a transparent find. – Angevin

I would not want it. Key is a specific type, and I do not want a templated function which would take anything, only to give me sheets of errors whenever I mistype the argument. – Bookshelf

@StoryTeller, this is very different. find is expected to be transparent, simply because the same find expressed as explicit loop would be transparent. – Bookshelf

@Bookshelf It wasn't expected to be transparent until c++14. We implicitly converted to Key for both operations. It's a valid question and contrast. – Angevin

Answer 1

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.

Osmond

Not sure if I buy this argument. If the type is convertible, it is the same as being constructible from it. – Bookshelf

@Bookshelf The two types are not required to be convertible - they are only required to be comparable through a transparent comparator. – Osmond

this is indeed correct! I would leave my comment there for future readers, but it's logically retracted. – Bookshelf

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? – Bergschrund

@Bergschrund The same argument could be made for find, but there's a transparent find. – Luo

@Luo except that find is an established operation for multimaps too. – Bergschrund

@Bergschrund and at is an established non-option for multimaps. Okay, makes sense now, thanks :) – Luo

This means one has to use find instead of at on a std::map<std::string, T> using a std::string_view key if they want to avoid constructing a temporary std::string for the access. Kinda sucks. – Ischia

I think @Bergschrund 's comment about multiple possible matches should be the answer, unless someone else is privy to the Committee's rationale for this. – Ischia

...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. – Ischia

Answer 2

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.

Ischia