By icn


2011-02-02 03:12:27 8 Comments

My code:

 typedef pair<int,int> Pair
  tr1::unordered_map<Pair,bool> h;
  h.insert(make_pair(Pair(0,0),true));

Erorr

 undefined reference to `std::tr1::hash<std::pair<int, int> >::operator()(std::pair<int, int>) const'

Something I need to fix?

thanks

3 comments

@fight_club 2019-08-24 06:00:35

Unordered Map does not contain a hash function for a pair, So if we want to hash a pair then we have to explicitly provide it with a hash function that can hash a pair.

If we want to use pair as a key to unordered_map, there are 2 ways to do it :

  1. Define specializaion for std::hash
typedef std::pair<std::string,std::string> pair;

struct pair_hash
{
    template <class T1, class T2>
    std::size_t operator() (const std::pair<T1, T2> &pair) const
    {
        return std::hash<T1>()(pair.first) ^ std::hash<T2>()(pair.second);
    }
};

int main()
{
    std::unordered_map<pair,int,pair_hash> unordered_map =
    {
        {{"C++", "C++11"}, 2011},
        {{"C++", "C++14"}, 2014},
        {{"C++", "C++17"}, 2017},
        {{"Java", "Java 7"}, 2011},
        {{"Java", "Java 8"}, 2014},
        {{"Java", "Java 9"}, 2017}
    };

    for (auto const &entry: unordered_map)
    {
        auto key_pair = entry.first;
        std::cout << "{" << key_pair.first << "," << key_pair.second << "}, "
                  << entry.second << '\n';
    }

    return 0;
}
  1. Using Boost Library Another good way is to use boost::hash from Boost.functional which can be used to hash integers,floats,pointers,strings,arrays,pairs and theh STL containers.
#include <iostream>
#include <boost/functional/hash.hpp>
#include <unordered_map>
#include <utility>

typedef std::pair<std::string,std::string> pair;

int main()
{
    std::unordered_map<pair,int,boost::hash<pair>> unordered_map =
    {
        {{"C++", "C++11"}, 2011},
        {{"C++", "C++14"}, 2014},
        {{"C++", "C++17"}, 2017},
        {{"Java", "Java 7"}, 2011},
        {{"Java", "Java 8"}, 2014},
        {{"Java", "Java 9"}, 2017}
    };

    for (auto const &entry: unordered_map)
    {
        auto key_pair = entry.first;
        std::cout << "{" << key_pair.first << "," << key_pair.second << "}, "
                  << entry.second << '\n';
    }

    return 0;
}

@Manohar Reddy Poreddy 2017-09-17 01:03:17

Ran into the same issue:

unordered_map <pair<x, y>, z> m1;

A few workarounds are:

unordered_map <stringxy, z> m1;
// the first and second of the pair merged to a string
//   though string parsing may be required, looks same complexity overall

unordered_multimap <x, pair<y, z>> m1;
// second of the pair of the key went into value.  
//   time complexity slightly increases

deque<deque<x>> d1;
// here x & y are of same type, z is stored as: d1[x][y] = z
//   space required is x * y, however time complexity is O(1)

@Rez 2018-09-06 21:42:37

Is unordered_multimap <x, pair<y, z>> m1; sufficient for inserting two pairs (x,y) such that x is the same and y is different? How would the hash function know to use y if it's in the value section?

@Manohar Reddy Poreddy 2018-09-07 03:39:19

I really want to help, but I lost the context of the above details. Did the comments, already given above, help at all?

@Murilo Vasconcelos 2011-02-02 03:18:13

This happens because there is no specialization for std::tr1::hash<Key> with Key = std::pair<int, int>. You must to specialize std::tr1::hash<Key> with Key = std::pair<int, int> before declaring tr1::unordered_map<Pair,bool> h;. This happens because std don't know how to hash a pair<int, int>.

Following there is a example of how to specialize std::tr1::hash<>

template <>
struct std::tr1::hash<std::pair<int, int> > {
public:
        size_t operator()(std::pair<int, int> x) const throw() {
             size_t h = SOMETHING;//something with x   
             return h;
        }
};

@Steve Jessop 2011-02-02 03:21:45

Which is unfortunate, because if I specialize it for use in my library, and you specialize it for use in your library, and our definitions aren't identical, then when our libraries are linked together we get undefined behavior. std::tr1::hash is a bit under-specced, it's better if possible to specify a custom Hash class to the unordered_map instead, as the third template parameter.

@GManNickG 2011-02-02 03:27:13

No, you can gain quite a lot without any pain, much more than with.

@Steve Jessop 2011-02-02 03:27:31

@Murilo: if it ain't hurting, it ain't C++.

@Murilo Vasconcelos 2011-02-02 03:32:44

@Steven :). But think about how to make a generic hash function for all possible types. In Java also, we have to override hashCode() for HashTables working with non-trivial types. +1 for your first comment because is a true but necessary evil.

@GManNickG 2011-02-02 03:35:02

@Murilo: It's hardly necessary. Standard types can easily have standard, unspecified hashes. It's only necessary for non-standard types, and even that's arguable.

@Steve Jessop 2011-02-03 17:22:09

@Murilo: but std::pair is a library class, so IMO the library should provide a hashcode (subject of course to the contained types having hashcodes). Java provides a hashcode for containers, as does Python for its built-in tuple type (but not for mutable containers, since Python doesn't allow mutable hash keys). C++0x has hashcodes for at least some containers, haven't checked if it's all of them. Looks to me like it has them for vector but not pair or tuple, which if true is odd, I think.

@Murilo Vasconcelos 2011-02-03 17:24:06

std::pair is a templated type. Unlike Java with Generics for example std::pair<int, int> is one type different from std::pair<int, double> (for example an ArrayList<Integer> is the same type of ArrayList<String> in Java). Each specialization generates code for differents types and is because of that, I think, is not possible to do a generic hash function.

@Steve Jessop 2011-02-03 17:26:14

@Murilo: of course it's possible: template <typename T, U> struct hash<pair<T,U> > { size_t operator() { return hash<T>()(first) ^ hash<U>()(second); }};. This provides a valid hashcode for pair<T,U> provided that the hashcodes for T and U are valid. As I say, C++0x has generic hashes for vector, and so do Java and Python for collections. So I don't understand why generic hash for pair is missing in TR1, let alone C++0x.

@Steve Jessop 2011-02-03 17:35:05

Bah, I failed to type the parameter to operator(), but the point is that for any container or container-like entity, if you have decent hashcodes for the elements you can define a decent hashcode for the whole thing provided that operator== does element-wise comparison.

@Steve Jessop 2011-02-03 19:03:49

@Murilo: Sure, that isn't a great hashcode, a better one would be hash(first)*31 + hash(second), or whatever you'd use for a 2-character string. You don't have to hash all kinds of elements, the template naturally means that if the contents have a hashcode then the pair does too. If the contents don't have a (useful) hashcode then don't try to hash the pair either. This is exactly the situation that pertains in Java, I don't see any problem with it.

@Murilo Vasconcelos 2011-02-03 20:29:10

@Steve: Ok, you are right. Would be good if this appears in the next standard.

@darKoram 2013-05-14 15:39:46

I'm compiling with g++ 4.7.3 on ubuntu. Pasting the code in the answer, I get an error: specialization of template<class_Tp> std::tr1::hash in a different namespace. So i wrap the code in namespace std { namespace tr1 //// code block /// } }. Then i get an error: explicit specialization of non-template std::tr1<anonymous struct>

Related Questions

Sponsored Content

27 Answered Questions

[SOLVED] Easiest way to convert int to string in C++

18 Answered Questions

[SOLVED] What is the difference between const int*, const int * const, and int const *?

12 Answered Questions

[SOLVED] Is there any advantage of using map over unordered_map in case of trivial keys?

33 Answered Questions

[SOLVED] What is the equivalent of the C++ Pair<L,R> in Java?

  • 2008-10-01 04:48:41
  • David Segonds
  • 453223 View
  • 664 Score
  • 33 Answer
  • Tags:   java tuples std-pair

4 Answered Questions

[SOLVED] error: passing xxx as 'this' argument of xxx discards qualifiers

  • 2011-05-12 04:52:56
  • JASON
  • 407262 View
  • 438 Score
  • 4 Answer
  • Tags:   c++

1 Answered Questions

[SOLVED] Cannot initialize const int from unpacked tuple

1 Answered Questions

[SOLVED] C++ unordered_map, efficient lazy load and use of value

  • 2016-09-17 09:47:02
  • Alex Cornford
  • 191 View
  • 3 Score
  • 1 Answer
  • Tags:   c++ unordered-map

1 Answered Questions

[SOLVED] Using std::pair as key in std::unordered_map

Sponsored Content