Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to use unordered_set in STL?

Tags:

c++

stl

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::_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::_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::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::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::operator[](const typename __gnu_cxx::hashtable, _Key, _HashFn, std::_Select1st >, _EqualKey, _Alloc>::key_type&) [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

like image 226
user855 Avatar asked Nov 30 '09 03:11

user855


People also ask

How does unordered_set work?

An unordered_set is an Associative container that contains an unordered set of data inserted randomly. Each element may occur only once, so duplicates are not allowed. A user can create an unordered set by inserting elements in any order and an unordered set will return data in any order i.e. unordered form.

What is unordered_set used for?

Use unordered_set whenWe need to keep a set of distinct elements and no ordering is required.

How is unordered_set implemented?

An unordered_set is implemented using a hash table where keys are hashed into indices of a hash table so that the insertion is always randomized.

Is unordered_set faster than set?

For a small number of elements, lookups in a set might be faster than lookups in an unordered_set . Even though many operations are faster in the average case for unordered_set , they are often guaranteed to have better worst case complexities for set (for example insert ).


1 Answers

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.

like image 143
novalis Avatar answered Sep 20 '22 18:09

novalis