C ++, как вставить массив в хэш-набор?

Question

Мне нужно вставить массив 1D в хэш-набор.

Но я получил ошибку при компиляции.

#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, 16> вместо int*, все ваши проблемы исчезнут.Если у вас нет компилятора C ++ 11, вы можете использовать вместо него boost::array.Кроме того, замените hash_set на unordered_set.

Похоже, что нет специализации std::hash для std::array с, поэтому я написал свою собственную:

#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

Не думаю, что существует специализированный hash<int*>. Я добавил это:

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 с, и он компилируется.

Answer 3

Вы не опубликовали фактическое сообщение об ошибке, только след.Тем не менее, это, вероятно, потому что ваш набор использует не-const int*, в то время как ваши данные const.

Тем не менее, я бы предложил использовать unordered_set вместо hash_set (либо изstd::tr1, если ваш компилятор поддерживает это, или из std, если ваш компилятор поддерживает C ++ 11 или из Boost), и прислушайтесь к совету Фреда об использовании {std,boost}::array вместо необработанного указателя.