C++如何将数组插入到哈希集中？

Question

我需要将一维数组插入到哈希集中。

但我在编译时出错了。

#include <stdio.h>
#include <stdlib.h>
#include <hash_set.h>
using namespace std;
int hash_comp(const int* state1,const int* state2) {
    int result = 0;

    for (i = 0; i < 16; i++) 
    {
        if (state1[i] != state2[i]) {
            result = -1;
        }

    }
    return result;
}
struct eqArray
{
    bool operator()(const int* a1,const int* a2) const
  {
    return hash_comp(a1,a2) == 0;
  }
};
hash_set<int*,hash<int*>,eqArray> closelist;
int main(int argc, char** argv)
{
   const int sn[16] = {1,2,3,4,5,6,0,8,9,10,11,12,13,14,7,15};
   closelist.insert(sn);
   return 0;
}

/usr/include/c++/4.2.1/ext/hashtable.h: In member function 'size_t __gnu_cxx::hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>::_M_bkt_num_key(const _Key&, size_t) const [with _Val = int*, _Key = int*, _HashFcn = __gnu_cxx::hash<int*>, _ExtractKey = std::_Identity<int*>, _EqualKey = std::equal_to<int*>, _Alloc = std::allocator<int*>]':
/usr/include/c++/4.2.1/ext/hashtable.h:599:   instantiated from 'size_t __gnu_cxx::hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>::_M_bkt_num(const _Val&, size_t) const [with _Val = int*, _Key = int*, _HashFcn = __gnu_cxx::hash<int*>, _ExtractKey = std::_Identity<int*>, _EqualKey = std::equal_to<int*>, _Alloc = std::allocator<int*>]'
/usr/include/c++/4.2.1/ext/hashtable.h:1006:   instantiated from 'void __gnu_cxx::hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>::resize(size_t) [with _Val = int*, _Key = int*, _HashFcn = __gnu_cxx::hash<int*>, _ExtractKey = std::_Identity<int*>, _EqualKey = std::equal_to<int*>, _Alloc = std::allocator<int*>]'
/usr/include/c++/4.2.1/ext/hashtable.h:437:   instantiated from 'std::pair<__gnu_cxx::_Hashtable_iterator<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>, bool> __gnu_cxx::hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>::insert_unique(const _Val&) [with _Val = int*, _Key = int*, _HashFcn = __gnu_cxx::hash<int*>, _ExtractKey = std::_Identity<int*>, _EqualKey = std::equal_to<int*>, _Alloc = std::allocator<int*>]'
/usr/include/c++/4.2.1/ext/hash_set:197:   instantiated from 'std::pair<typename __gnu_cxx::hashtable<_Value, _Value, _HashFcn, std::_Identity<_Tp>, _EqualKey, _Alloc>::const_iterator, bool> __gnu_cxx::hash_set<_Value, _HashFcn, _EqualKey, _Alloc>::insert(const typename __gnu_cxx::hashtable<_Value, _Value, _HashFcn, std::_Identity<_Tp>, _EqualKey, _Alloc>::value_type&) [with _Value = int*, _HashFcn = __gnu_cxx::hash<int*>, _EqualKey = std::equal_to<int*>, _Alloc = std::allocator<int*>]'
src/ods2.cpp:677:   instantiated from here

Answer 1

如果您使用 std::array 而不是 int*，所有问题都会消失。如果您没有 C++11 编译器，则可以使用 boost::array 代替。另外，将 hash_set 替换为 unordered_set。

看来对于 std::array 没有专门化的 std::hash ，所以我编写了自己的：

#include <unordered_set>
#include <array>

namespace std
{
    template<typename T, size_t N>
    struct hash<array<T, N> >
    {
        typedef array<T, N> argument_type;
        typedef size_t result_type;

        result_type operator()(const argument_type& a) const
        {
            hash<T> hasher;
            result_type h = 0;
            for (result_type i = 0; i < N; ++i)
            {
                h = h * 31 + hasher(a[i]);
            }
            return h;
        }
    };
}

std::unordered_set<std::array<int, 16> > closelist;

int main()
{
    std::array<int, 16> sn = {1,2,3,4,5,6,0,8,9,10,11,12,13,14,7,15};
    closelist.insert(sn);
}

Answer 2

您没有发布实际的错误消息，只发布了跟踪。也就是说，这可能是因为您的集合使用非 const int*，而您的数据是 const。

也就是说，我建议使用 unordered_set 而不是 hash_set（如果您的编译器支持的话，可以使用 std::tr1 ，或者使用 >std（如果您的编译器支持 C++11 或来自 Boost），并注意 Fred 的建议，使用 {std,boost}::array 而不是原始指针。

Answer 3

我认为不存在专门的hash。我添加了这一点：

namespace __gnu_cxx{ //I'm not sure what compiler version you used,
                     //mine wanted this
    template<>
    struct hash<const int*>{
        size_t operator()(const int*a) const{
            size_t r = 0;
            for (int i=0;i<16;i++)
                r = (r<<1) ^ a[i]; //not sure if it makes sense as a hash.
            return r;
        }
    };
}

我还放入了一些 const 并进行编译。