STL源码剖析-hash_set / hash_multiset
程序员文章站
2022-03-23 10:51:54
...
类似于标准的set以rb_tree为底层实现,hash_set以hashtable为底层实现,hash_set的底层操作也是由hashtable提供。
运用set,为的是能够快速的搜索元素。这一点无论其底层是rb_tree或是hashtable,都可以达成任务。但是rb_tree有自动排序的功能,而hashtable是没有,反应的结果是set元素有自动排序功能,而hash_set没有。
如下主要给出hash_set的成员变量,以及构造函数,插入函数,通过这几个部门我们就可以在大体上理解hash_set.
template<typename Value, class HashFun = std::hash<Value>>
class hash_set{
private:
typedef hashtable<Value, Value, HashFun> ht;
// 成员,底层以hash table完成
ht rep;
public:
// 构造函数,缺省使用大小为100的表格
// 会被hashtable调整为193
hash_set():rep(100){};
template<typename InputIterator>
hash_set(InputIterator first, InputIterator last):
rep(100){rep.insert_unique(first, last);}
};
hash_multiset的特性和hash_set完全相同,唯一的区别在于插入的时候使用的insert_equal函数(允许插入重复值)而不是insert_unique(不允许插入重复值)。
下一篇: poj3087 Shuffle'm Up