The following program does not compile an unordered set of pairs of integers, but it does for integers. Can unordered_set and its member functions be used on user-defined types, and how can I define it?
#include <unordered_set>
...
class A{
...
private:
std::unordered_set< std::pair<int, int> > u_edge_;
};
Compiler error:
error: no matching function for call to 'std::unordered_set >::unordered_set()'
Your code compiles on VS2010 SP1 (VC10), but it fails to compile with GCC g++ 4.7.2.
However, you may want to consider boost::hash from Boost.Functional to hash a std::pair (with this addition, your code compiles also with g++).
#include <unordered_set>
#include <boost/functional/hash.hpp>
class A
{
private:
std::unordered_set<
std::pair<int, int>,
boost::hash< std::pair<int, int> >
> u_edge_;
};
There is no standard way of computing a hash on a pair. Add this definition to your file:
struct pair_hash {
inline std::size_t operator()(const std::pair<int,int> & v) const {
return v.first*31+v.second;
}
};
Now you can use it like this:
std::unordered_set< std::pair<int, int>, pair_hash> u_edge_;
This works, because pair<T1,T2> defines equality. For custom classes that do not provide a way to test equality you may need to provide a separate function to test if two instances are equal to each other.
Of course this solution is limited to a pair of two integers. Here is a link to an answer that helps you define a more general way of making hash for multiple objects.
The problem is that std::unordered_set is using std::hash template to compute hashes for its entries and there is no std::hash specialization for pairs. So you will have to do two things:
std::hash for your key type (std::pair<int, int>) using that function.Here is a simple example:
#include <unordered_set>
namespace std {
template <> struct hash<std::pair<int, int>> {
inline size_t operator()(const std::pair<int, int> &v) const {
std::hash<int> int_hasher;
return int_hasher(v.first) ^ int_hasher(v.second);
}
};
}
int main()
{
std::unordered_set< std::pair<int, int> > edge;
}
You need to provide a specialization for std::hash<> that works with std::pair<int, int>. Here is a very simple example of how you could define the specialization:
#include <utility>
#include <unordered_set>
namespace std
{
template<>
struct hash<std::pair<int, int>>
{
size_t operator () (std::pair<int, int> const& p)
{
// A bad example of computing the hash,
// rather replace with something more clever
return (std::hash<int>()(p.first) + std::hash<int>()(p.second));
}
};
}
class A
{
private:
// This won't give you problems anymore
std::unordered_set< std::pair<int, int> > u_edge_;
};
As already mentioned in most of the other answers on this question, you need to provide a hash function for std::pair<int, int>. However, since C++11, you can also use a lambda expression instead of defining a hash function. The following code takes the solution given by dasblinkenlight as basis:
auto hash = [](const std::pair<int, int>& p){ return p.first * 31 + p.second; };
std::unordered_set<std::pair<int, int>, decltype(hash)> u_edge_(8, hash);
Code on Ideone
I'd like repeat dasblinkenlight's disclaimer: This solution is limited to a pair of two integers. This answer provides the idea for a more general solution.
You are missing a hash function for std::pair<int, int>>. For example,
struct bad_hash
{
std::size_t operator()(const std::pair<int,int>& p) const
{
return 42;
}
};
....
std::unordered_set< std::pair<int, int>, bad_hash> u_edge_;
You can also specialize std::hash<T> for std::hash<std::pair<int,int>>, in which case you can omit the second template parameter.
The other answers here all suggest building a hash function that somehow combines your two integers.
This will work, but produces non-unique hashes. Though this is fine for your use of unordered_set, for some applications it may be unacceptable. In your case, if you happen to choose a bad hash function, it may lead to many unnecessary collisions.
But you can produce unique hashes!
int is usually 4 bytes. You could make this explicit by using int32_t.
The hash's datatype is std::size_t. On most machines, this is 8 bytes. You can check this upon compilation.
Since a pair consists of two int32_t types, you can put both numbers into an std::size_t to make a unique hash.
That looks like this (I can't recall offhandedly how to force the compiler to treat a signed value as though it were unsigned for bit-manipulation, so I've written the following for uint32_t.):
#include <cassert>
#include <cstdint>
#include <unordered_set>
#include <utility>
struct IntPairHash {
std::size_t operator()(const std::pair<uint32_t, uint32_t> &p) const {
assert(sizeof(std::size_t)>=8); //Ensure that std::size_t, the type of the hash, is large enough
//Shift first integer over to make room for the second integer. The two are
//then packed side by side.
return (((uint64_t)p.first)<<32) | ((uint64_t)p.second);
}
};
int main(){
std::unordered_set< std::pair<uint32_t, uint32_t>, IntPairHash> uset;
uset.emplace(10,20);
uset.emplace(20,30);
uset.emplace(10,20);
assert(uset.size()==2);
}
OK here is a simple solution with guaranteed non collisions. Simply reduce your problem to an existing solution i.e. convert your pair of int to string like so:
auto stringify = [](const pair<int, int>& p, string sep = "-")-> string{
return to_string(p.first) + sep + to_string(p.second);
}
unordered_set<string> myset;
myset.insert(stringify(make_pair(1, 2)));
myset.insert(stringify(make_pair(3, 4)));
myset.insert(stringify(make_pair(5, 6)));
Enjoy!
