Use vectors as key in unordered_map

Question

So I want to use vectors as keys in my unordered_map. I have followed this answer and I have the following

#include <iostream>
#include <cstdlib>
#include <tuple>
#include <unordered_map>
#include <vector>
#include <boost/functional/hash.hpp> /* hash_combine */
template <typename T>

struct vectorHasher{
std::size_t operator()(std::vector<T> &in) const
{
    using boost::hash_value;
    using boost::hash_combine;
    // Start with a hash value of 0
    std::size_t seed = 0;
    T value;
    for (int i=0; i< in.size(); i++)
    {
        value = static_cast<T>(in[i]);
        hash_combine(seed, hash_value(value));
    }
    return seed;
}
};


int main()
{
typedef std::unordered_map< std::vector<std::size_t>, int, vectorHasher<std::vector<std::size_t> > > map_type;
map_type mymap;

std::vector<size_t> vec (3,100);
mymap[vec] = 1;

return 0;
}

, but I get the following error compiling the code.

In file included from mytest_vectorhasher.cpp:6:
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/unordered_map:404:17: error: 
  no matching function for call to object of type 'const
  vectorHasher<std::__1::vector<unsigned long, std::__1::allocator<unsigned long> >
  >'
    {return static_cast<const _Hash&>(*this)(__x);}
            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/__hash_table:1976:21: note: 
  in instantiation of member function
  'std::__1::__unordered_map_hasher<std::__1::vector<unsigned long,
  std::__1::allocator<unsigned long> >,
  std::__1::__hash_value_type<std::__1::vector<unsigned long,
  std::__1::allocator<unsigned long> >, int>, vectorHasher<std::__1::vector<unsigned
  long, std::__1::allocator<unsigned long> > >, true>::operator()' requested here
size_t __hash = hash_function()(__k);
                ^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/unordered_map:1443:21: note: 
  in instantiation of function template specialization
  'std::__1::__hash_table<std::__1::__hash_value_type<std::__1::vector<unsigned long,
  std::__1::allocator<unsigned long> >, int>,
  std::__1::__unordered_map_hasher<std::__1::vector<unsigned long,
  std::__1::allocator<unsigned long> >,
  std::__1::__hash_value_type<std::__1::vector<unsigned long,
  std::__1::allocator<unsigned long> >, int>, vectorHasher<std::__1::vector<unsigned
  long, std::__1::allocator<unsigned long> > >, true>,
  std::__1::__unordered_map_equal<std::__1::vector<unsigned long,
  std::__1::allocator<unsigned long> >,
  std::__1::__hash_value_type<std::__1::vector<unsigned long,
  std::__1::allocator<unsigned long> >, int>,
  std::__1::equal_to<std::__1::vector<unsigned long, std::__1::allocator<unsigned
  long> > >, true>,
  std::__1::allocator<std::__1::__hash_value_type<std::__1::vector<unsigned long,
  std::__1::allocator<unsigned long> >, int> >
  >::__emplace_unique_key_args<std::__1::vector<unsigned long,
  std::__1::allocator<unsigned long> >, const std::__1::piecewise_construct_t &,
  std::__1::tuple<const std::__1::vector<unsigned long, std::__1::allocator<unsigned
  long> > &>, std::__1::tuple<> >' requested here
return __table_.__emplace_unique_key_args(__k,
                ^
mytest_vectorhasher.cpp:41:10: note: in instantiation of member function
  'std::__1::unordered_map<std::__1::vector<unsigned long,
  std::__1::allocator<unsigned long> >, int, vectorHasher<std::__1::vector<unsigned
  long, std::__1::allocator<unsigned long> > >,
  std::__1::equal_to<std::__1::vector<unsigned long, std::__1::allocator<unsigned
  long> > >, std::__1::allocator<std::__1::pair<const std::__1::vector<unsigned long,
  std::__1::allocator<unsigned long> >, int> > >::operator[]' requested here
mymap[vec] = 1;
     ^
mytest_vectorhasher.cpp:13:17: note: candidate function not viable: no known conversion
  from 'const std::__1::vector<unsigned long, std::__1::allocator<unsigned long> >'
  to 'std::vector<vector<unsigned long, allocator<unsigned long> > > &' for 1st
  argument
std::size_t operator()(std::vector<T> &in) const
            ^
1 error generated.

Is it something easy that I am messing up? What am I doing wrong?

Possible duplicate of [C++ unordered\_map using a custom class type as the key](http://stackoverflow.com/questions/17016175/c-unordered-map-using-a-custom-class-type-as-the-key) — Deedee Megadoodoo, Jan 12 '17 at 07:13

François Andrieux · Accepted Answer · 2017-01-12T16:32:55.317

There are two errors in this example. First, your hasher's operator() parameter should be const.

std::size_t operator()(const std::vector<T> &in) const
//      Add const here ^^^^^

Second is you are defining your hashing type as vectorHasher<std::vector<std::size_t> > which would imply that T = std::vector<std::size_t>, meaning that you are trying to instantiate a hasher with std::size_t operator()(const std::vector<std::vector<std::size_t>> &in) const which is too many vectors. Remove the std::vector from your map type declaration like this :

typedef std::unordered_map< std::vector<std::size_t>, int, vectorHasher< std::size_t > > map_type;
//                        Remove std::vector from this template argument ^^^^^^^^^^^

score 2 · Answer 2 · answered Jan 12 '17 at 04:00

2

The problem is you have the wrong parameter for operator(). When you construct the vectorHasher you use

vectorHasher<std::vector<std::size_t>>

Which means T is a

std::vector<std::size_t>

That means your operator() looks like

std::size_t operator()(std::vector<std::vector<std::size_t>> &in) const

Which is not what you want. What you can do is to use T directly like

std::size_t operator()(const T& in) const

Or change the vectorHasher to be

vectorHasher<std::size_t>

answered Jan 12 '17 at 04:00

NathanOliver

171,901
28
288
402

Thanks for the input. – Sep Jan 12 '17 at 16:30
@Seth No problem. Glad to help. – NathanOliver Jan 12 '17 at 16:39

score 0 · Answer 3 · answered Jan 12 '17 at 04:03

There are 2 errors in your code.

1) Since you defined your vectorHasher as

template <typename T>
struct vectorHasher{
std::size_t operator()(std::vector<T> &in) const
    {
    // ...
    }
};

The following template instantiation vectorHasher<std::vector<std::size_t>> expands to:

struct vectorHasher{
std::size_t operator()(std::vector<std::vector<std::size_t>> &in) const
    {
    // ...
    }
};

And, sure enough, std::vector<std::size_t> can't be passed to this function.

Change the instantiation of the template to vectorHasher<std::size_t>.

2) operator() of the struct used for hashing needs to take const value/reference, so you should change the signature of it to:

std::size_t operator()(std::vector<T> const &in) const

Live demo.

Use vectors as key in unordered_map

3 Answers3