Используйте векторы как key в unordered_map

Question

Так что я хочу использовать векторы в качестве ключей в unordered_map. Я следовал this answer и у меня есть следующие

#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; 
} 

, но я получаю следующее сообщение об ошибке компиляции кода.

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. 

Это что-то легкое, что я испортил? Что я делаю не так?

Answer 1

В этом примере есть две ошибки. Во-первых, параметр вашего хакера operator() должен быть const.

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

Во-вторых, вы определяете тип хеширования, как vectorHasher<std::vector<std::size_t> >, который будет означать, что T = std::vector<std::size_t>, а это означает, что вы пытаетесь создать экземпляр Hasher с std::size_t operator()(const std::vector<std::vector<std::size_t>> &in) const, который слишком много векторов. Удалите std::vector из вашего объявления типа карты, как это:

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

Answer 2

Проблема в том, у вас есть неправильный параметр для operator(). Когда вы строите vectorHasher использовать

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

Это означает T является

std::vector<std::size_t> 

Это означает, что ваш operator() выглядит

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

Который не то, что вы хотите. Что вы можете сделать, это использовать T непосредственно как

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

Или изменить vectorHasher быть

vectorHasher<std::size_t> 

Answer 3

Есть 2 ошибки в коде.

1) Так как вы определили свой vectorHasher как

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

следующий шаблон экземпляра vectorHasher<std::vector<std::size_t>> расширяется:

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

И, конечно, std::vector<std::size_t> не может быть передан этой функции.

Изменить экземпляр шаблона на vectorHasher<std::size_t>.

2) operator() из struct, используемых для хеширования необходимо принимать const значения/ссылку, так что вы должны изменить подпись к ней:

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

Live demo.