How to use unordered_set in STL?

Question

Hi,

I am in need of a hash_map class in C++(STL). Primary operation is to put pair in the set and then check if it exists or not.

I am unable to find a sample code which does it to know if what I am declaration correctly or not.

#include <iostream>
#include <hash_map>

using namespace std;
using namespace __gnu_cxx;

typedef pair<int,string> pis;

struct eqpis {
    bool operator()(pis p1,pis p2) const {
     if(p1==p2) return true;
     return false;
    }
};

int main() {
    hash_map<pis,int,hash<pis>,eqpis> map;
}

This one compiles. But if I add the line : map[pis(10,"hello")]=10; then it gives a lot of errors:

/usr/include/c++/4.4/backward/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 = std::pair, std::allocator > >, int>, _Key = std::pair, std::allocator > >, _HashFcn = __gnu_cxx::hash, std::allocator > > >, _ExtractKey = std::_Select1st, std::allocator > >, int> >, _EqualKey = eqpis, _Alloc = std::allocator]’: /usr/include/c++/4.4/backward/hashtable.h:594: instantiated from ‘size_t __gnu_cxx::hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>::_M_bkt_num(const _Val&, size_t) const [with _Val = std::pair, std::allocator > >, int>, _Key = std::pair, std::allocator > >, _HashFcn = __gnu_cxx::hash, std::allocator > > >, _ExtractKey = std::_Select1st, std::allocator > >, int> >, _EqualKey = eqpis, _Alloc = std::allocator]’ /usr/include/c++/4.4/backward/hashtable.h:1001: instantiated from ‘void __gnu_cxx::hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>::resize(size_t) [with _Val = std::pair, std::allocator > >, int>, _Key = std::pair, std::allocator > >, _HashFcn = __gnu_cxx::hash, std::allocator > > >, _ExtractKey = std::_Select1st, std::allocator > >, int> >, _EqualKey = eqpis, _Alloc = std::allocator]’ /usr/include/c++/4.4/backward/hashtable.h:789: instantiated from ‘_Val& __gnu_cxx::hashtable<_Val, _Key, _HashFcn, _ExtractKey, _EqualKey, _Alloc>::find_or_insert(const _Val&) [with _Val = std::pair, std::allocator > >, int>, _Key = std::pair, std::allocator > >, _HashFcn = __gnu_cxx::hash, std::allocator > > >, _ExtractKey = std::_Select1st, std::allocator > >, int> >, _EqualKey = eqpis, _Alloc = std::allocator]’ /usr/include/c++/4.4/backward/hash_map:216: instantiated from ‘_Tp& __gnu_cxx::hash_map<_Key, _Tp, _HashFn, _EqualKey, _Alloc>::operator, _Key, _HashFn, std%3A%3A_Select1st >, _EqualKey, _Alloc>%3A%3Akey%5Ftype&"> [with _Key = std::pair, std::allocator > >, _Tp = int, _HashFn = __gnu_cxx::hash, std::allocator > > >, _EqualKey = eqpis, _Alloc = std::allocator]’ x.cpp:18: instantiated from here /usr/include/c++/4.4/backward/hashtable.h:590: error: no match for call to ‘(const __gnu_cxx::hash, std::allocator > > >) (const std::pair, std::allocator > >&)’

Thanks

Answer 1

I'm not sure which compiler you are using, but have you looked at this Hash map (C++) Wikipedia listing?

Answer 2

You use it in the same way as std::map:

typedef hash_map<int,string> HMap;

HMap map;
map.insert(HMap::value_type(1,"two"));

for (HMap::iterator it = map.begin(); it != map.end(); ++it)
{
    cout << (*it).first << " " << (*it).second << endl;
}

There are some differences with header files between windows and linux:

#ifdef WIN32
#include <hash_map>
#else
#include <ext/hash_map>
#endif

#ifndef WIN32
    using __gnu_cxx::hash_map;
#endif

#ifdef WIN32
    typedef hash_map< const K, V > HMap;
#else
    typedef hash_map< const K, V, boost::hash<K> >;
#endif

I believe linux hash_map requires hash function to be able to hash the key, you can use boost::hash as above.

Here is your code compiled on linux (see above for differences between linux and windows, i'm using boost::hash because on linux there's no hash function, there is one in windows, i'm not sure if it is overloaded for struct type ...):

#include <iostream>
//#include <hash_map>
#include <ext/hash_map>
#include <string>
#include <boost/functional/hash.hpp>
using namespace std;
//using namespace __gnu_cxx;
using __gnu_cxx::hash_map;

typedef pair<int,string> pis;

struct eqpis {
    bool operator()(pis p1,pis p2) const {
        if(p1==p2) return true;
        return false;
    }
};

int main() {
    //hash_map<pis,int,hash<pis>,eqpis> map;
    typedef hash_map<pis,int, boost::hash<pis>, eqpis > HMap;
    HMap map;
    map.insert(HMap::value_type(pis(10,"hello"), 11));
    map.insert(HMap::value_type(pis(20,"hello"), 21));
    map.insert(HMap::value_type(pis(30,"hello"), 31));
    map.insert(HMap::value_type(pis(40,"hello"), 41));

    for (HMap::iterator it = map.begin(); it != map.end(); ++it)
    {
        cout << (*it).first.first << ":" << (*it).first.second
             <<  " == " << (*it).second << endl;
    }
}

Output:

40:hello == 41
20:hello == 21
10:hello == 11
30:hello == 31

Answer 3

First of all, you want std::unordered_map or unordered_set. The requirements are that your class needs operator= (or you need an EqualityCompare class), and you need a hashing class which has operator() which takes your key type as an argument and returns a size_t.

Answer 4

Your problem is that hash<T> is only specialized for certain types. It can't magically make a hash function for any old type. You need to make your own hash function.