14

Looking around on cppreference, I found that std::unordered_map gets efficient lookup functions from "equivalent keys".

I take that to mean that the equivalent key must have the same hash value. How can I provide that for a string literal I get the same hash value as for std::hash<std::string> without temporarily constructing an std::string and thereby making the whole point about the equivalent keys for naught?

Charles
  • 50,943
  • 13
  • 104
  • 142
Johannes Schaub - litb
  • 496,577
  • 130
  • 894
  • 1,212
  • At first glance, I see 2 issues to overcome: 1) find (and the other `std::unordered_map` lookup functions) all take `Key const&`, which will create a temporary pretty much immediately. 2) There is no `std::hash` specialization for string literals. I suspect the best answer is to write your own container, which is similar to `unordered_map`, but allows to search by string literals, and uses a custom hash function which can handle `std::string` (stored values) as well as `const char*` for lookups. – Dave S Dec 03 '13 at 12:17
  • @DaveS so how come that cppreference says that `unordered_map` starting with C++14 has an overload for `find` that takes an "equivalent key"? I'm confused. The paper at http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3657.htm that I thought introduced `is_transparent` doesn't seem to introduce it for hash function objects. Also what is `Compare` that the cppreference talks about? I have the feeling I'm missing something important. I just find it smelly that even in C++14 I still have to write my own container for such simple concerns :( – Johannes Schaub - litb Dec 03 '13 at 12:20
  • Yes, the idea was that you write your own hash function that covers all the equivalent types. For this use case I always had some "pair" in mind anyways. So don't use an std::hash, but your own that has an op() for both types. – PlasmaHH Dec 03 '13 at 12:22
  • Sorry, I missed the C++14 tag, and hadn't seen that paper. I should know better than to try to respond to questions right after I wake up. – Dave S Dec 03 '13 at 12:22
  • @PlasmaHH I would be glad if you could provide an answer on how to use this feature. I wonder if it is implemented in libc++ or libstdc++ anyway. AFAIK, C++17 will come with `std::string_view`, so then they could add a `hash` and make `hash` rely on it. – Johannes Schaub - litb Dec 03 '13 at 12:28
  • @JohannesSchaub-litb: Yeah, that string view stuff would be nice. I can not really comment on how the actual standard wording came out, I can just say what the intention was: make your own comparator and hash objects (the comparator marked, by having some is_transparent typedef, what type is unimportant) both of which have op() overloaded for (in your case) taking string and charptr. – PlasmaHH Dec 03 '13 at 12:33
  • This answer sounds relevant: http://stackoverflow.com/a/20318064/453271 – Andriy Tylychko Dec 03 '13 at 12:43
  • 1
    @PlasmaHH ahh i see. something like this: http://coliru.stacked-crooked.com/a/f80fefd2c6c51c2e . Unfortunately, gcc and clang don't seem to support it yet :/ – Johannes Schaub - litb Dec 03 '13 at 12:44
  • 3
    Are we sure that `std::hash` is getting this support in C++14? The paper you linked only shows it on the associative containers, not the unordered ones. cppreference, for all its benefits, also makes heavy use of internal templates to reduce duplication. It appears that both `map` and `unordered_map` are using the same description block for `find`, which explains the use of `Compare::is_transparent` in the description. – Dave S Dec 03 '13 at 13:20
  • @DaveS Hmm, interesting point, given that `unordered_map` doesn't have an actual `Compare` while `map` does. – Christian Rau Dec 03 '13 at 13:43
  • @DaveS ah i see. these days i avoid looking into the stdlib spec, because i feel like being lost in a big forest. too bad i was possibly tricked by cppreference. I would be glad if someone provided an answer showing that this is indeed the case. – Johannes Schaub - litb Dec 03 '13 at 13:46
  • @DaveS you guessed the root cause correctly, by the way. I used the wrong wiki template initially. – Cubbi Dec 03 '13 at 17:21

3 Answers3

5

That was an error in cppreference; there are no templated finds for unordered associated containers.

Compare, from n3690,

from §23.5.4.1[unord.map.overview]

// lookup
iterator find(const key_type& k);
const_iterator find(const key_type& k) const;
size_type count(const key_type& k) const;

from §23.4.4.1[map.overview]

// 23.4.4.5, map operations:
iterator find(const key_type& x);
const_iterator find(const key_type& x) const;
template <class K> iterator find(const K& x);
template <class K> const_iterator find(const K& x) const;
size_type count(const key_type& x) const;
Cubbi
  • 46,567
  • 13
  • 103
  • 169
  • It would be nice if they added unorded associative containers as well. It would require a transparent `KeyEqual` function, but also a `Hash` that supports both the Key type and the input to a templated `find`. I think specifying the latter would be a bit trickier. – Dave S Dec 03 '13 at 17:16
  • @DaveS for `unordered_set< T, Hash, Equal >`, iff `Hash::is_transparent` add `unordered_set< T, Hash, Equal >::find(const K& x)` that does a `Hash(x)` then `Equal( y, x )` where `y` is the element(s) found by the `Hash(x)`? Now, `x` has to be `Equal`-able (either by conversion or transparency), but... – Yakk - Adam Nevraumont Dec 09 '13 at 22:03
4

Heterogeneous lookup for unordered containers has been adopted for C++20 (p0919, p1690). It's already available in gcc 11.0 and clang 12.0.

m8mble
  • 1,513
  • 1
  • 22
  • 30
2

As others said, unordered associative containers don't support the is_transparent mode. Boost.MultiIndex hashed indices, on the other hand, allow for what you want, as explained in the documentation, in case it is an option for you to replace std::unordered_map with an equivalent construct based on a multi_index_container.

Joaquín M López Muñoz
  • 5,243
  • 1
  • 15
  • 20