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

Myth丶恋晨 2023-06-04 04:56 14阅读 0赞

# STL源码剖析（十八）关联式容器之hash\_map、hash\_multimap #

### 文章目录 ###

*  STL源码剖析（十八）关联式容器之hash\_map、hash\_multimap
 *   *  一、hash\_map、hash\_multimap的数据结构
     *  二、hash\_map、hash\_multimap的迭代器
     *  三、hash\_map、hash\_multimap的操作
     *   *  3.1 构造函数
         *  3.2 析构函数
         *  3.3 插入元素
         *  3.4 删除元素
         *  3.5 其他操作

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()) {}

初始化哈希表