欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

STL源码剖析(十八)关联式容器之hash_map、hash_multimap

程序员文章站 2022-03-23 11:29:06
...

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); }

可以看到,绝大数操作都是转而调用哈希表完成的