C++ how to insert array into hash set?

Question

I need to insert a 1D array into the hashset.

But I got error while compiling.

#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

By the way, the .h headers and all the pointers and the return 0; inside main suggest that you are learning C++ from a very poor source. Do yourself a favor and buy a decent book. — fredoverflow
– fredoverflow, Commented Nov 6, 2011 at 12:21

fredoverflow · Accepted Answer · 2011-11-06 14:04:27Z

15

If you use a std::array<int, 16> instead of int*, all your problems will go away. If you have no C++11 compiler, you can use boost::array instead. Also, replace hash_set with unordered_set.

It appears there is no specialization of std::hash for std::arrays, so I wrote my own:

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

edited Nov 6, 2011 at 14:04

answered Nov 6, 2011 at 12:13

fredoverflow

265k101 gold badges403 silver badges680 bronze badges

Sign up to request clarification or add additional context in comments.

12 Comments

weeo Over a year ago

thank you, so what library should I include instead of hash_set.h? and how can I declare these? like {unordered_set<std::array<int,16>,hash<std::array<int,16>>,??which function?> closelist;}

Kerrek SB Over a year ago

You could use #include <tr1/unordered_set>, #include <tr1/array>, and std::tr1::unordered_set<std::tr1::array<int, 16> >.

weeo Over a year ago

I still got error: ` /usr/include/c++/4.2.1/tr1/hashtable_policy.h:784: error: using invalid field 'std::tr1::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, std::tr1::__detail::_Default_ranged_hash, false>::_M_h1' make[2]: *** [build/Debug/GNU-MacOSX/src/ods2.o] Error 1`

weeo Over a year ago

src/ods2.cpp:69: error: specialization of 'template<class T> struct std::tr1::hash' in different namespace /usr/include/c++/4.2.1/tr1/functional_hash.h:48: error:   from definition of 'template<class T> struct std::tr1::hash'

src/ods2.cpp:69: error: specialization of 'template<class T> struct std::tr1::hash' in different namespace /usr/include/c++/4.2.1/tr1/functional_hash.h:48: error: from definition of 'template<class T> struct std::tr1::hash' make[2]: *** [build/Debug/GNU-MacOSX/src/ods2.o] Error 1

fredoverflow Over a year ago

@BaummitAugen I stole it from java.lang.String.hashCode. It seems to be a popular number, because it is prime, and 31 * x can be implemented quite efficiently as (x << 5) - x.

|

Konrad Rudolph · Accepted Answer · 2011-11-06 12:13:42Z

0

You didn’t post the actual error message, only the trace. That said, it’s probably because your set uses non-const int* while your data is const.

That said, I’d suggest using unordered_set instead of hash_set(either from std::tr1 if your compiler supports that, or from std if your compiler supports C++11 or from Boost), and heed Fred’s advice of using an {std,boost}::array instead of a raw pointer.

answered Nov 6, 2011 at 12:13

Konrad Rudolph

549k142 gold badges967 silver badges1.3k bronze badges

1 Comment

weeo Over a year ago

I got this error message: /usr/include/c++/4.2.1/tr1/hashtable_policy.h:784: error: using invalid field 'std::tr1::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, std::tr1::__detail::_Default_ranged_hash, false>::_M_h1' make[2]: *** [build/Debug/GNU-MacOSX/src/ods2.o] Error 1

Vlad · Accepted Answer · 2011-11-06 12:23:54Z

0

I don't think that there exists a specialized hash<int*>. I added this:

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

I also put in some consts and it compiles.

answered Nov 6, 2011 at 12:23

Vlad

18.8k4 gold badges44 silver badges72 bronze badges

Collectives™ on Stack Overflow

C++ how to insert array into hash set?

3 Answers 3

12 Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

12 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related