如何在STL中使用unordered_set？

Question

我需要 C++(STL) 中的 hash_map 类。主要操作是将pair放入集合中，然后检查它是否存在。

我无法找到示例代码来了解我的声明是否正确。

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

这个可以编译。但如果我添加以下行： 地图[pis(10,"你好")]=10; 然后它给出了很多错误：

/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::对， std::allocator > >、int>、_Key = std::pair、std::allocator > >, _HashFcn = __gnu_cxx::hash, std::allocator >; > >, _ExtractKey = std::_Select1st, std::allocator >; >, 整数> >, _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 >; >, 整数> >, _EqualKey = eqpis, _Alloc = std::allocator]' /usr/include/c++/4.4/backward/hashtable.h:1001：从 '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 >; >, 整数> >, _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 >; >, 整数> >, _EqualKey = eqpis, _Alloc = std::allocator]' /usr/include/c++/4.4/backward/hash_map:216：从 '_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：从这里实例化 /usr/include/c++/4.4/backward/hashtable.h:590: 错误: 与调用 '(const __gnu_cxx::hash, std::allocator > > >) (const std::pair, std::分配器 >>&)'

谢谢

Answer 1

您的问题是 hash 仅专门针对某些类型。它不能神奇地为任何旧类型创建哈希函数。您需要创建自己的哈希函数。

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中有一个，我不确定它是否被重载为struct类型...）：

#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&)。当传递它的副本时，每次比较发生时，都会执行昂贵的内存分配和字符串复制，导致时间和内存的浪费。