0

map<pair<int,int>, int> compiles but unordered_map<pair<int,int>> has issues with hash function. What's really happening in the back?

phuclv
  • 37,963
  • 15
  • 156
  • 475
Gokularam
  • 3
  • 2
  • C++ has a built-in `operator<` for pairs (lexicographic ordering, assuming the types of the pair support comparison by `operator<`) but it doesn't have a built-in hash for pairs and tuples. So you can use them in `map`s but not `unordered_map`s. Not sure exactly _why_ there isn't a built-in hash for pairs and tuples--hard to come down on a "right" default that balances speed and hash quality? – Nathan Pierson Sep 25 '21 at 20:35
  • 2
    This has nothing to do with Rcpp so please remove the tag (which I cannot do right now as there is pending-approval edit). – Dirk Eddelbuettel Sep 25 '21 at 20:39
  • Duplicates: [Why can't I compile an unordered_map with a pair as key?](https://stackoverflow.com/q/32685540/995714), [Why did the C++ standards committee not include std::hash for pair and tuple?](https://stackoverflow.com/q/68320024/995714), [Why does std::map accept a std::pair as key, but std::unordered_map does not?](https://stackoverflow.com/q/50163423/995714), [Why can't I compile an unordered_map with a pair as key?](https://stackoverflow.com/q/32685540/995714), [`pair` pair as key of unordered_map issue](https://stackoverflow.com/q/4870437/995714) – phuclv Sep 26 '21 at 02:10
  • Does this answer your question? [Why can't I compile an unordered\_map with a pair as key?](https://stackoverflow.com/questions/32685540/why-cant-i-compile-an-unordered-map-with-a-pair-as-key) – phuclv Sep 26 '21 at 02:10
  • the solution is to provide the hash function yourself: [How to std::hash an unordered std::pair](https://stackoverflow.com/q/28367913/995714), [Hash for a std::pair, for use in an unordered_map](https://stackoverflow.com/q/45395071/995714) – phuclv Sep 26 '21 at 02:11

1 Answers1

0

std::map<Key,T> requires that the key type is comparable. The default comparator for std::map<Key,T> is std::less<Key>, so you can use it with std::pair<T1,T2> because std::pair defines operator< (or operator<=> depending on your version of C++), making it comparable. Since the map is ordered, it must be able to compare the keys to know how they will be ordered internally, and it does this with the comparator.

std::unordered_map<Key,T> on the other hand requires two different aspects from the Key type, it must be hashable and must also be comparable for equality. std::pair<T1,T2> does implement operator==/operator<=> but this alone is not enough for the type to be usable as the Key type. The standard library does not supply a specialisation of std::hash for std::pair, hence it will not compile (however, boost does, it simply combines the hash of .first and .second).

You can use std::unordered_map<std::pair<int, int>, ...> if want to, but you need to supply your own function for hashing this type, either by defining a functor to pass as a template argument to std::unordered_map<> or by defining your own custom specialisation of std::hash<std::pair<int, int>> directly.

dreamlax
  • 93,976
  • 29
  • 161
  • 209