如何在STL中使用unordered_set？

Question

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

我无法找到一个示例代码，它知道我是否正确地声明了它。

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

这个编译。但如果我添加该行： map [pis（10，“hello”）] = 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::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 > >&)’

感谢

Answer 1

您的问题是hash<T>只针对某些类型。它不能神奇地为任何旧类型创建散列函数。你需要制作你自己的散列函数。

Answer 2

我不知道你正在使用的编译器，但你看这Hash map (C++) Wikipedia listing？

Answer 3

您可以使用它以同样的方式作为的std ::地图：

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

首先，你要std::unordered_map或unordered_set。要求是你的类需要operator=（或者你需要一个EqualityCompare类），并且你需要一个散列类，它有operator()，它把你的键类型作为参数并返回一个size_t。

Answer 5

对不起，迟到的回应。如果我是你，我会通过引用将对象传递给比较函数（const pis &）。当它通过复制时，每次进行比较时，都会执行昂贵的内存分配和字符串副本，导致浪费时间和内存。