STL源码剖析(十七)关联式容器之hash_set、hash_multiset
STL源码剖析(十七)关联式容器之hash_set、hash_multiset
文章目录
前面我们将过 set 和 multiset,这里将 hash_set 和 hash_multiset,它们的区别主要是底层支持不同,set 和 multiset 使用的是红黑树,hash_set 和 hash_multiset 使用的是哈希表
红黑树是自动排序的,而哈希表是无序的,所以 set 和 multiset 是有序的,而 hash_set 和 hash_multiset 是无序的
关于 set 和 multiset 的区别前面文章已经介绍过了,就是 set 不允许键值重复,multiset 运行键值重复,对于 hash_set 和 hash_multiset 也是一样的
一、hash_set、hash_multiset的数据结构
hash_set 的定义如下
template <class Value, class HashFcn = hash<Value>,
class EqualKey = equal_to<Value>,
class Alloc = alloc>
class hash_set
{
private:
typedef hashtable<Value, Value, HashFcn, identity<Value>,
EqualKey, Alloc> ht;
ht rep;
};
它的成员变量就是一个哈希表,我们这里主要是看哈希表的模板参数
首先看哈希表模板参数的定义
template <class Value, class Key, class HashFcn,
class ExtractKey, class EqualKey,
class Alloc>
class hashtable {
...
};
-
Value:key+data,对于 set 来说,没有 data,所以 key 就是 value,value 就是 key
-
key:键值
-
HashFcn:用于生成哈希值的仿函数,hash_set 定义为 hash<Value>,其定义如下
template <class Key> struct hash { }; ... __STL_TEMPLATE_NULL struct hash<unsigned int> { size_t operator()(unsigned int x) const { return x; } }; __STL_TEMPLATE_NULL struct hash<long> { size_t operator()(long x) const { return x; } }; ...
STL中对大多数基本变量类型都定义的对应的哈希函数,如果要将哈希表用于自己定义的类型,那么就需要特化一个自己的仿函数
-
ExtractKey:从 value 中获取 key,hash_set 的定义为 identity<Value>,这是一个仿函数,其作用是返回自己,定义如下
template <class T> struct identity : public unary_function<T, T> { const T& operator()(const T& x) const { return x; } };
-
EqualKey:判断两个键值是否相等,hash_set 的定义为 equal_to<Value>,其定义如下
template <class T> struct equal_to : public binary_function<T, T, bool> { bool operator()(const T& x, const T& y) const { return x == y; } };
解析完这些模板参数后,hash_set 的数据结构也应该清楚了,hash_multiset 的数据结构和 hash_set 是一样的,这里就不列出了
二、hash_set、hash_multiset的迭代器
hash_set、hash_multiset的迭代器定义如下
typedef typename ht::const_iterator iterator;
它们都没有自己特定的迭代器,都是直接使用哈希表的迭代器
这里需要注意的是,迭代器的类型为const,这是因为 set 的 value 只有 key,key 是不允许被修改的,所以这里使用了 const 类型
三、hash_set、hash_multiset的操作
3.1 构造函数
hash_set() : rep(100, hasher(), key_equal()) {}
初始化哈希表,指定bucket个数为100
3.2 析构函数
hash_set 没有析构函数,当释放 hash_set 的时候,它的成员变量会自动被析构释放,也就是其中的哈希表会被析构释放
3.3 插入元素
hash_set 的 insert
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);
}
因为 hash_set 不支持键值重复,所以它调用的是哈希表的 insert_unique 函数
返回值是一个对组,包括指向插入节点的迭代器还有插入结果
hash_multiset 的 insert
iterator insert(const value_type& obj) { return rep.insert_equal(obj); }
hash_multiset 支持键值重复,所以调用的是 insert_equal
3.4 删除元素
size_type erase(const key_type& key) {return rep.erase(key); }
调用哈希表的erase函数
3.5 其他操作
begin
iterator begin() const { return rep.begin(); }
end
iterator end() const { return rep.end(); }
find
iterator find(const key_type& key) const { return rep.find(key); }
下一篇: iPhone13Pro屏幕发红是什么问题