Why can’t I compile an unordered_map with a pair as key?

by

You need to provide a suitable hash function for your key type. A simple example:

#include <unordered_map>
#include <functional>
#include <string>
#include <utility>

// Only for pairs of std::hash-able types for simplicity.
// You can of course template this struct to allow other hash functions
struct pair_hash {
    template <class T1, class T2>
    std::size_t operator () (const std::pair<T1,T2> &p) const {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);

        // Mainly for demonstration purposes, i.e. works but is overly simple
        // In the real world, use sth. like boost.hash_combine
        return h1 ^ h2;  
    }
};

using Vote = std::pair<std::string, std::string>;
using Unordered_map = std::unordered_map<Vote, int, pair_hash>;

int main() {
    Unordered_map um;
}

This will work, but not have the best hash-properties†. You might want to have a look at something like boost.hash_combine for higher quality results when combining the hashes. This is also discussed in greater detail – including the aforementioned solution from boost – in this answer.

For real world use: Boost also provides the function set hash_value which already provides a hash function for std::pair, as well as std::tuple and most standard containers.

†More precisely, it will produce too many collisions. E.g., every symmetric pair will hash to 0 and pairs that differ only by permutation will have the same hash. This is probably fine for your programming exercise, but might seriously hurt performance of real world code.

More Related Contents:

  1. Is there any advantage of using map over unordered_map in case of trivial keys?
  2. How to choose between map and unordered_map?
  3. Is NaN a valid key value for associative containers?
  4. Map C++ Sort and Insert elements by value
  5. c++ push reference node to stl list
  6. Insert into map with pair as key and list as value [closed]
  7. C++ unordered_map using a custom class type as the key
  8. Why does the C++ map type argument require an empty constructor when using []?
  9. A std::map that keep track of the order of insertion?
  10. Why is std::map implemented as a red-black tree?
  11. How std::unordered_map is implemented
  12. Const map element access
  13. In STL maps, is it better to use map::insert than []?
  14. How to use range-based for() loop with std::map?
  15. Is the order of iterating through std::map known (and guaranteed by the standard)?
  16. std::map emplace without copying value
  17. What is the default constructor for C++ pointer?
  18. unordered_map hash function c++
  19. C++ Loop through Map
  20. How can I modify values in a map using range based for loop?
  21. insert vs emplace vs operator[] in c++ map
  22. Super high performance C/C++ hash map (table, dictionary) [closed]
  23. how do you make a heterogeneous boost::map?
  24. Using std::map where V has no usable default constructor
  25. How can I make the map::find operation case insensitive?
  26. std::map thread-safety
  27. What would a std::map extended initializer list look like?
  28. Why Can’t I store references in a `std::map` in C++?
  29. error for hash function of pair of ints
  30. Is it possible to implement lock free map in C++

Leave a Comment