Как использовать unordered_set в STL?

Question

Мне нужен класс hash_map в C ++ (STL). Основная операция - поместить пару в набор, а затем проверить, существует она или нет.

Я не могу найти пример кода, который делает это, чтобы узнать, правильно ли я заявляю или нет.

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

Этот компилируется. Но если я добавлю строку: карта [пись (10, "Привет")] = 10; тогда это дает много ошибок:

/ usr / include / c ++ / 4.4 / backward / hashtable.h: в функции-члене 'size_t __gnu_cxx :: hashtable :: _ M_bkt_num_key (const _Key &, size_t) const [с _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: создается из '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: создается из 'void __gnu_cxx :: hashtable :: resize (size_t) [с _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: создается из '_Val & __gnu_cxx :: hashtable :: find_or_insert (const _Val &) [с _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: создается из '_Tp & __gnu_cxx :: hash_map :: operator [] (постоянное имя __gnu_cxx :: hashtable, _Key, _HashFn, std :: _ Select1st>, _EqualKey, _AqualKey, :: key_type &) [с _Key = std :: pair, std :: allocator>>, _Tp = int, _HashFn = __gnu_cxx :: hash, std :: allocator>>>, _EqualKey = eqpis, _Alloc = std :: allocator] ' x.cpp: 18: создается здесь /usr/include/c++/4.4/backward/hashtable.h:590: ошибка: нет совпадения для вызова '(const __gnu_cxx :: hash, std :: allocator>>>) (const std :: pair, std :: распределитель>> &) '

Спасибо

Answer 1

Ваша проблема в том, что hash<T> специализируется только для определенных типов. Он не может волшебным образом создать хеш-функцию для любого старого типа. Вам нужно создать собственную хеш-функцию.

Answer 2

Прежде всего, вы хотите std::unordered_map или unordered_set. Требования заключаются в том, что вашему классу требуется operator= (или вам нужен класс EqualityCompare), и вам нужен класс хеширования, имеющий operator(), который принимает ваш тип ключа в качестве аргумента и возвращает size_t.

Answer 3

Вы используете его так же, как 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;
}

Существуют некоторые различия с заголовочными файлами между Windows и 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

Я считаю, что linux hash_map требует, чтобы хеш-функция была способна хешировать ключ, вы можете использовать boost :: hash, как указано выше.

Вот ваш код, скомпилированный в linux (см. Выше различия между linux и windows, я использую boost :: hash, потому что в linux нет хэш-функции, она есть в windows, я не уверен, что это перегружен для типа структуры ...):

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

Выход:

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

Answer 4

Извините за поздний ответ. На вашем месте я бы передавал объекты в функцию сравнения по ссылке (const pis &). При передаче его копии, каждый раз, когда происходит сравнение, выполняется дорогостоящее выделение памяти и копирование строки, что приводит к трате времени и памяти.

Answer 5

Я не уверен, какой компилятор вы используете, но вы смотрели на этот Hash map (C ++) список Википедии ?