STL源码剖析(十八)关联式容器之hash_map、hash_multimap
STL源码剖析(十八)关联式容器之hash_map、hash_multimap
文章目录
map 和 set 的区别就是,set 的 value 中 只有 key 没有 data,而 map 的 value 既有 key 又有 data,每一个元素都是一个对组
一、hash_map、hash_multimap的数据结构
hash_map的定义如下
template <class Key, class T, class HashFcn = hash<Key>,
class EqualKey = equal_to<Key>,
class Alloc = alloc>
class hash_map
{
...
private:
typedef hashtable<pair<const Key, T>, Key, HashFcn,
select1st<pair<const Key, T> >, EqualKey, Alloc> ht;
ht rep;
...
};
它们的成员变量只有一个哈希表,下面解析一下哈希表的模板参数
哈希表的模板参数定义如下
template <class Value, class Key, class HashFcn,
class ExtractKey, class EqualKey,
class Alloc>
class hashtable {
...
};
-
Value:包含 key + data,hash_map 指定的是 pair<const Key, T>,一个对组,注意里面的 key 是 const 类型,因为 key 是不允许被修改的
-
Key:键值
-
HashFcn:哈希函数,hash_map 指定的是 hash<Key>,用于生成哈希值,这个上一篇文章已经讲解过了,这里不再讲解
-
ExtractKey:从 value 中获取 key,hash_map 的定义为 select1st<pair<const Key, T> >,因为每个元素都是 key 加 data,所以获取键值就从对组中取出第一个元素就行,select1st 的定义如下
template <class Pair> struct select1st : public unary_function<Pair, typename Pair::first_type> { const typename Pair::first_type& operator()(const Pair& x) const { return x.first; } };
-
EqualKey:判断 key 是否相等,hash_map 的定义为 equal_to<Key> ,定义如下
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_mulitmap 的数据结构和 hash_map 是一样的,这里不再列出
二、hash_map、hash_multimap的迭代器
hash_map 和 hash_multimap 的迭代器都是一样的,定义如下
typedef typename ht::iterator iterator;
它们都是直接使用哈希表的迭代器
如果要修改对应的data,可以这样做
it->second = xxx;
三、hash_map、hash_multimap的操作
hash_map 和 hash_multimap 的操作基本是相同的,只是插入元素的操作不同,这里相同的部分只会列处 hash_map
3.1 构造函数
hash_map() : rep(100, hasher(), key_equal()) {}
初始化哈希表
3.2 析构函数
hash_map 和 hash_multimap 是没有析构函数的,在释放 hash_map 和 hash_multimap 对象的时候,会自动析构释放成员变量,所以哈希表会被自动析构释放
3.3 插入元素
hash_map 的 insert
pair<iterator, bool> insert(const value_type& obj)
{ return rep.insert_unique(obj); }
因为不允许键值重复,所以调用的哈希表的 insert_unique 操作
hash_multimap 的 insert
iterator insert(const value_type& obj) { return rep.insert_equal(obj); }
允许键值重复,所以调用的哈希表的 insert_equal 操作
3.4 删除元素
size_type erase(const key_type& key) {return rep.erase(key); }
通过调用哈希表的 erase 完成操作
3.5 其他操作
begin
iterator begin() { return rep.begin(); }
end
iterator end() { return rep.end(); }
find
iterator find(const key_type& key) { return rep.find(key); }
可以看到,绝大数操作都是转而调用哈希表完成的
上一篇: JAVA游戏------裁判评分小游戏
下一篇: 荐 python3入门笔记