首页 > 代码库 > 关联容器 — hash_set
关联容器 — hash_set
容器hash_set是以hash table为底层机制的,几乎所有的操作都是转调用hash table提供的接口。由于插入无法存储相同的键值,所以hash_set的插入操作全部都使用hash table的insert_unique接口,代码如下:
pair<iterator, bool> insert(const value_type& obj) { pair<typename ht::iterator, bool> p = rep.insert_unique(obj); return pair<iterator, bool>(p.first, p.second); }
再看一下一个构造函数:
private: typedef hashtable<Value, Value, HashFcn, identity<Value>, 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 <iostream> #include <hash_set> using namespace std; using namespace __gnu_cxx; int main() { hash_set<int> set; set.insert(3); set.insert(196); set.insert(1); set.insert(389); set.insert(194); set.insert(387); hash_set<int>::iterator iter = set.begin(); for ( ; iter != set.end(); ++iter) cout << *iter << ‘ ‘; return 0; }
运行结果:
由于有197个桶,所以元素1、194、387被散列到1号桶;3、196、389被散列到3号桶。但新元素是插入到每个桶指向的链表的前端,所以就有了这样的输出顺序。
参考:
《STL源码剖析》 P270.
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。