Menu
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;
^
http://ideone.com/wusr5V
657
We can use it to hash integers, floats, pointers, strings, arrays, pairs, and standard containers. That's all about using pair as a key in std::unordered_set in C++.
Two unordered_sets are equal if they have the same number of elements and the elements in one container are a permutation of the elements in the other container.
An unordered set vector is an unordered associative container that is used to hold unique vectors together. Two vectors are considered the same if the corresponding elements of the vectors are equal. Unlike a set of vectors, vectors are not arranged in any particular order in an unordered set of vectors.
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);
}
Live example
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.
185
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.
44
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
