关联容器 — hash_set
最后更新于：2022-04-01 19:54:24
容器hash_set是以hash table为底层机制的，几乎所有的操作都是转调用hash table提供的接口。由于插入无法存储相同的键值，所以hash_set的插入操作全部都使用hash table的insert_unique接口，代码如下：
~~~
pair insert(const value_type& obj)
{
pair p = rep.insert_unique(obj);
return pair(p.first, p.second);
}
~~~
再看一下一个构造函数：
~~~
private:
typedef hashtable,
EqualKey, Alloc> ht;
ht rep; // 底层机制——hash table
public:
hash_set() : rep(100, hasher(), key_equal()) {} // 默认大小为100
~~~
这里把hash table的表格大小，也就是vector大小设置为了100，那么在初始化hash table时，会自动选择最接近的质数为197。也就是说一开始hash_set便拥有了197个“桶”。
下面来比较一下set和hash_set的异同：
set的底层机制为红黑树，hash_set的底层机制为hash table，两者都能进行高效率的搜索。红黑树利用了二叉搜索树的特性，而hash table则利用散列技术。但红黑树有自动排序功能而hash table没有，反映出来的结果就是，set的元素有自动排序功能而hash_set没有。下面是测试代码：
~~~
#include
#include
using namespace std;
using namespace __gnu_cxx;
int main()
{
hash_set set;
set.insert(3);
set.insert(196);
set.insert(1);
set.insert(389);
set.insert(194);
set.insert(387);
hash_set::iterator iter = set.begin();
for ( ; iter != set.end(); ++iter)
cout << *iter << ' ';
return 0;
}
~~~
运行结果：
由于有197个桶，所以元素1、194、387被散列到1号桶；3、196、389被散列到3号桶。但新元素是插入到每个桶指向的链表的前端，所以就有了这样的输出顺序。
参考：
《STL源码剖析》 P270.
';