在 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>，这意味着您正试图用 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) 用于散列的struct的operator()需要取constvalue/reference，所以你要把它的签名改成：

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

Live demo.

在 unordered_map 中使用向量作为键

Use vectors as key in unordered_map

c++

hash

unordered-map