How to use unordered_set that has elements that are vector of pair<int,int>
Solution 1
You could implement it like this, based on boost::hash_combine
for a sensible calculation of hashes:
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_set>
namespace
{
// a little helper that should IMHO be standardized
template<typename T>
std::size_t make_hash(const T& v)
{
return std::hash<T>()(v);
}
// adapted from boost::hash_combine
void hash_combine(std::size_t& h, const std::size_t& v)
{
h ^= v + 0x9e3779b9 + (h << 6) + (h >> 2);
}
// hash any container
template<typename T>
struct hash_container
{
size_t operator()(const T& v) const
{
size_t h=0;
for( const auto& e : v ) {
hash_combine(h, make_hash(e));
}
return h;
}
};
}
namespace std
{
// support for pair<T,U> if T and U can be hashed
template<typename T, typename U>
struct hash<pair<T, U>>
{
size_t operator()(const pair<T,U>& v) const
{
size_t h=make_hash(v.first);
hash_combine(h, make_hash(v.second));
return h;
}
};
// support for vector<T> if T is hashable
// (the T... is a required trick if the vector has a non-standard allocator)
template<typename... T>
struct hash<vector<T...>> : hash_container<vector<T...>> {};
// the same for map<T,U> if T and U are hashable
template<typename... T>
struct hash<map<T...>> : hash_container<map<T...>> {};
// simply add more containers as needed
}
int main()
{
std::unordered_set<std::vector<std::pair<int,int>>> us;
us.insert(std::vector<std::pair<int,int>>{{{42,0},{17,64}}});
std::cout << us.size() << std::endl;
std::cout << us.begin()->size() << std::endl;
std::cout << us.begin()->begin()->first << std::endl;
std::unordered_set<std::map<int,int>> usm;
std::map<int,int> m{{42,0},{17,64}};
usm.insert(m);
}
Note that there was a problem when combining Clang with libstdc++ which might affect you when specializing std::hash
. It has been fixed with GCC 4.8.2, but it is still visible on Coliru. If this is a problem in your case, you could disable the warning with -Wno-mismatched-tags
and Clang will no longer complain.
Solution 2
You should write a hasher for your types, for example:
class MyHash
{
public:
std::size_t operator()(const vector<pair<int,int>> &v) const
{
std::size_t x = 0;
for (auto &i : v)
x ^= std::hash<int>()(i.first) ^ std::hash<int>()(i.second);
return x;
}
};
int main()
{
unordered_set<vector<pair<int,int>>, MyHash> um;
}
Note: The hash function that I wrote is just an example, it can be replaced with another and better one.
NoSenseEtAl
Loving C++ because it gives me a warm FUBU feeling, also CHF :P aka: money for programming and high level abstractions for (almost )free. :P I dont hate C that much, but I fu*king hate C APIs
Updated on June 03, 2022Comments
-
NoSenseEtAl about 2 years
I wanted to have something like
unordered_set<vector<pair<int,int>>> us;
but even without pair:
#include <vector> #include <unordered_set> using namespace std; int main() { unordered_set<vector<int>> um; }
it fails:
In file included from /usr/include/c++/4.8/bits/hashtable.h:35:0, from /usr/include/c++/4.8/unordered_set:47, from prog.cpp:2: /usr/include/c++/4.8/bits/hashtable_policy.h: In instantiation of ‘struct std::__detail::_Hash_code_base<std::vector<int>, std::vector<int>, std::__detail::_Identity, std::hash<std::vector<int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>’: /usr/include/c++/4.8/bits/hashtable_policy.h:1402:10: required from ‘struct std::__detail::_Hashtable_base<std::vector<int>, std::vector<int>, std::__detail::_Identity, std::equal_to<std::vector<int> >, std::hash<std::vector<int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, true, true> >’ /usr/include/c++/4.8/bits/hashtable.h:174:11: required from ‘class std::_Hashtable<std::vector<int>, std::vector<int>, std::allocator<std::vector<int> >, std::__detail::_Identity, std::equal_to<std::vector<int> >, std::hash<std::vector<int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, true, true> >’ /usr/include/c++/4.8/bits/unordered_set.h:96:18: required from ‘class std::unordered_set<std::vector<int> >’ prog.cpp:7:32: required from here /usr/include/c++/4.8/bits/hashtable_policy.h:1070:12: error: invalid use of incomplete type ‘struct std::hash<std::vector<int> >’ struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, ^ In file included from /usr/include/c++/4.8/bits/stl_bvector.h:1134:0, from /usr/include/c++/4.8/vector:65, from prog.cpp:1: /usr/include/c++/4.8/bits/functional_hash.h:58:12: error: declaration of ‘struct std::hash<std::vector<int> >’ struct hash; ^ In file included from /usr/include/c++/4.8/bits/hashtable.h:35:0, from /usr/include/c++/4.8/unordered_set:47, from prog.cpp:2: /usr/include/c++/4.8/bits/hashtable_policy.h:1070:12: error: invalid use of incomplete type ‘struct std::hash<std::vector<int> >’ struct _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, ^ In file included from /usr/include/c++/4.8/bits/stl_bvector.h:1134:0, from /usr/include/c++/4.8/vector:65, from prog.cpp:1: /usr/include/c++/4.8/bits/functional_hash.h:58:12: error: declaration of ‘struct std::hash<std::vector<int> >’ struct hash; ^ In file included from /usr/include/c++/4.8/bits/hashtable.h:35:0, from /usr/include/c++/4.8/unordered_set:47, from prog.cpp:2: /usr/include/c++/4.8/bits/hashtable_policy.h:1082:53: error: invalid use of incomplete type ‘struct std::hash<std::vector<int> >’ using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>; ^ In file included from /usr/include/c++/4.8/bits/stl_bvector.h:1134:0, from /usr/include/c++/4.8/vector:65, from prog.cpp:1: /usr/include/c++/4.8/bits/functional_hash.h:58:12: error: declaration of ‘struct std::hash<std::vector<int> >’ struct hash; ^ In file included from /usr/include/c++/4.8/bits/hashtable.h:35:0, from /usr/include/c++/4.8/unordered_set:47, from prog.cpp:2: /usr/include/c++/4.8/bits/hashtable_policy.h:1082:53: error: invalid use of incomplete type ‘struct std::hash<std::vector<int> >’ using __ebo_h1 = _Hashtable_ebo_helper<1, _H1>; ^ In file included from /usr/include/c++/4.8/bits/stl_bvector.h:1134:0, from /usr/include/c++/4.8/vector:65, from prog.cpp:1: /usr/include/c++/4.8/bits/functional_hash.h:58:12: error: declaration of ‘struct std::hash<std::vector<int> >’ struct hash; ^ prog.cpp: In constructor ‘std::unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(std::unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type, const hasher&, const key_equal&, const allocator_type&) [with _Value = std::vector<int>; _Hash = std::hash<std::vector<int> >; _Pred = std::equal_to<std::vector<int> >; _Alloc = std::allocator<std::vector<int> >; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type = unsigned int; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::hasher = std::hash<std::vector<int> >; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::key_equal = std::equal_to<std::vector<int> >; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::allocator_type = std::allocator<std::vector<int> >]’: prog.cpp:7:32: error: invalid use of incomplete type ‘std::unordered_set<std::vector<int> >::hasher {aka struct std::hash<std::vector<int> >}’ unordered_set<vector<int>> um; ^ In file included from /usr/include/c++/4.8/bits/stl_bvector.h:1134:0, from /usr/include/c++/4.8/vector:65, from prog.cpp:1: /usr/include/c++/4.8/bits/functional_hash.h:58:12: error: declaration of ‘std::unordered_set<std::vector<int> >::hasher {aka struct std::hash<std::vector<int> >}’ struct hash; ^ prog.cpp:7:32: note: when instantiating default argument for call to std::unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(std::unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type, const hasher&, const key_equal&, const allocator_type&) [with _Value = std::vector<int>; _Hash = std::hash<std::vector<int> >; _Pred = std::equal_to<std::vector<int> >; _Alloc = std::allocator<std::vector<int> >; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type = unsigned int; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::hasher = std::hash<std::vector<int> >; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::key_equal = std::equal_to<std::vector<int> >; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::allocator_type = std::allocator<std::vector<int> >] unordered_set<vector<int>> um; ^ In file included from /usr/include/c++/4.8/bits/hashtable.h:35:0, from /usr/include/c++/4.8/unordered_set:47, from prog.cpp:2: /usr/include/c++/4.8/bits/hashtable_policy.h: In instantiation of ‘std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, std::__detail::_Default_ranged_hash, true>::_Hash_code_base(const _ExtractKey&, const _H1&, const _H2&, const std::__detail::_Default_ranged_hash&) [with _Key = std::vector<int>; _Value = std::vector<int>; _ExtractKey = std::__detail::_Identity; _H1 = std::hash<std::vector<int> >; _H2 = std::__detail::_Mod_range_hashing]’: /usr/include/c++/4.8/bits/hashtable_policy.h:1463:65: required from ‘std::__detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, _Hash, _Traits>::_Hashtable_base(const _ExtractKey&, const _H1&, const _H2&, const _Hash&, const _Equal&) [with _Key = std::vector<int>; _Value = std::vector<int>; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<std::vector<int> >; _H1 = std::hash<std::vector<int> >; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _Traits = std::__detail::_Hashtable_traits<true, true, true>]’ /usr/include/c++/4.8/bits/hashtable.h:828:24: required from ‘std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::_Hashtable(std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::size_type, const _H1&, const _H2&, const _Hash&, const _Equal&, const _ExtractKey&, const allocator_type&) [with _Key = std::vector<int>; _Value = std::vector<int>; _Alloc = std::allocator<std::vector<int> >; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<std::vector<int> >; _H1 = std::hash<std::vector<int> >; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, true, true>; std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::size_type = unsigned int; std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::allocator_type = std::allocator<std::vector<int> >]’ /usr/include/c++/4.8/bits/hashtable.h:397:26: required from ‘std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::_Hashtable(std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::size_type, const _H1&, const key_equal&, const allocator_type&) [with _Key = std::vector<int>; _Value = std::vector<int>; _Alloc = std::allocator<std::vector<int> >; _ExtractKey = std::__detail::_Identity; _Equal = std::equal_to<std::vector<int> >; _H1 = std::hash<std::vector<int> >; _H2 = std::__detail::_Mod_range_hashing; _Hash = std::__detail::_Default_ranged_hash; _RehashPolicy = std::__detail::_Prime_rehash_policy; _Traits = std::__detail::_Hashtable_traits<true, true, true>; std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::size_type = unsigned int; std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::key_equal = std::equal_to<std::vector<int> >; std::_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, _Traits>::allocator_type = std::allocator<std::vector<int> >]’ /usr/include/c++/4.8/bits/unordered_set.h:136:35: required from ‘std::unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(std::unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type, const hasher&, const key_equal&, const allocator_type&) [with _Value = std::vector<int>; _Hash = std::hash<std::vector<int> >; _Pred = std::equal_to<std::vector<int> >; _Alloc = std::allocator<std::vector<int> >; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::size_type = unsigned int; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::hasher = std::hash<std::vector<int> >; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::key_equal = std::equal_to<std::vector<int> >; std::unordered_set<_Value, _Hash, _Pred, _Alloc>::allocator_type = std::allocator<std::vector<int> >]’ prog.cpp:7:32: required from here /usr/include/c++/4.8/bits/hashtable_policy.h:1099:63: error: invalid use of incomplete type ‘struct std::hash<std::vector<int> >’ : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { } ^ In file included from /usr/include/c++/4.8/bits/stl_bvector.h:1134:0, from /usr/include/c++/4.8/vector:65, from prog.cpp:1: /usr/include/c++/4.8/bits/functional_hash.h:58:12: error: declaration of ‘struct std::hash<std::vector<int> >’ struct hash; ^ In file included from /usr/include/c++/4.8/bits/hashtable.h:35:0, from /usr/include/c++/4.8/unordered_set:47, from prog.cpp:2: /usr/include/c++/4.8/bits/hashtable_policy.h:1099:63: error: invalid use of incomplete type ‘struct std::hash<std::vector<int> >’ : __ebo_extract_key(__ex), __ebo_h1(__h1), __ebo_h2(__h2) { } ^ In file included from /usr/include/c++/4.8/bits/stl_bvector.h:1134:0, from /usr/include/c++/4.8/vector:65, from prog.cpp:1: /usr/include/c++/4.8/bits/functional_hash.h:58:12: error: declaration of ‘struct std::hash<std::vector<int> >’ struct hash; ^