【C++ STL篇(十五)】哈希表封装 unordered_map 和 unordered

在这里插入图片描述

大家好，欢迎来到 huangjin007_ 的博客
⭐
个人主页：huangjin007_
🔥
文章收录专栏：零基础入门C++

总会有一些坚持能从冰封的土地里培育出十万朵怒放的蔷薇

C++ STL篇(十五) —— 哈希表封装 unordered_map 和 unordered_set

在上一篇文章中，我们深入讲解了哈希表的实现，如果你对这些内容还不太熟悉，建议先回顾一下【C++ STL篇(十四)】哈希表实现：开放定址法与链地址法

本文假定你已经掌握了哈希表实现的基础操作，接下来我们要完成一个更酷的挑战：用我们自己实现的哈希表，模拟出 STL 中的 unordered_map 和 unordered_set !

全程干货，坐稳发车~ ദ്ദി˶ｰ̀֊ｰ́ )✧

文章目录

C++ STL篇(十五) —— 哈希表封装 unordered_map 和 unordered_set
- 1. 站在巨人的肩膀上：SGI-STL 源码框架分析
- 2. 我们已有的哈希桶
- 3. 打造通用型 HashTable（支持泛型 T）
- - 3.1 节点模板改为只含 `T`
  - 3.2 HashTable 模板参数增加 `KeyOfT`
  - 3.3 在 `Insert`、`Find`、`Erase` 中使用 `KeyOfT`
  - 3.4 改造 `Insert` 返回值，为 `operator[]` 准备
- 4. 实现哈希表迭代器 —— 最难的点 `operator++`
- - 4.1 解引用和访问成员
  - 4.2 不等于比较
  - 4.3 最核心的 `operator++`：跨桶找下一个节点
  - 4.4 友元声明与类型别名
  - 4.5 `Begin()` 和 `End()` 的实现
- 5. 完整的 HashTable 实现解析
- 6. 封装 unordered_map 和 unordered_set
- - 6.1 unordered_set 的封装
  - 6.2 unordered_map 的封装
- 7. 容易踩的坑与设计细节回顾
- - 7.1 迭代器为什么需要 `_ht` 指针
  - 7.2 拷贝构造时的链表深度复制
  - 7.3 `SetKeyOfT` / `MapKeyOfT` 的作用
  - 7.4 如何保证键不可修改
  - 7.5 扩容时元素重新映射
  - 7.6 `operator[]` 的细节
- 结语：

1. 站在巨人的肩膀上：SGI-STL 源码框架分析

SGI-STL30 版本发布于 C++11 之前，那时候还没有 unordered_map/unordered_set，但它已经实现了功能基本相同的 hash_map 和 hash_set，只是它们属于“非标准容器”。源码就在 stl_hash_map.h、stl_hash_set.h 和 stl_hashtable.h 里。

我们截取出核心结构，先来感受一下：

// stl_hash_set.h
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;
public:
typedef typename ht::key_type key_type;
typedef typename ht::value_type value_type;
typedef typename ht::hasher hasher;
typedef typename ht::key_equal key_equal;
typedef typename ht::const_iterator iterator;
typedef typename ht::const_iterator const_iterator;
hasher hash_funct() const { return rep.hash_funct(); }
key_equal key_eq() const { return rep.key_eq(); }
};

// stl_hash_map.h
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;
public:
typedef typename ht::key_type key_type;
typedef T data_type;
typedef T mapped_type;
typedef typename ht::value_type value_type;
typedef typename ht::hasher hasher;
typedef typename ht::key_equal key_equal;
typedef typename ht::iterator iterator;
typedef typename ht::const_iterator const_iterator;
};

而底层的 hashtable 声明大概是这样的（简化）：

template <class Value, class Key, class HashFcn,
class ExtractKey, class EqualKey,
class Alloc>
class hashtable {
public:
typedef Key key_type;
typedef Value value_type;
typedef HashFcn hasher;
typedef EqualKey key_equal;
private:
hasher hash;
key_equal equals;
ExtractKey get_key;
typedef __hashtable_node<Value> node;
vector<node*, Alloc> buckets;
size_type num_elements;
public:
typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator;
pair<iterator, bool> insert_unique(const value_type& obj);
const_iterator find(const key_type& key) const;
};

节点很简单，就是单链表：

template <class Value>
struct __hashtable_node
{
__hashtable_node* next;
Value val;
};

核心设计思路：

hash_set 存储纯 key 值：传给 hashtable 的两个类型参数都是 Value（也就是 Key），并用 identity<Value> 作为“从值中取出 key”的仿函数（它的 operator() 就是直接返回自己）。

hash_map 存储 key-value 对：传给 hashtable 的是 pair<const Key, T>（值类型）和 Key（键类型），并用 select1st<pair<const Key, T>> 来从 pair 中取出 first（即 key）。

hashtable 只认一个模板参数 Value（它存在节点里），但它不知道这个 Value 到底是什么。于是额外需要一个 ExtractKey 仿函数，帮它从 Value 中提取出 Key，用来计算哈希值和比较相等。

一个容器只需要持有一个 hashtable 对象，把自己收到的操作全部转发给它。

这个设计简直神了！一份哈希表，两份复用，完美适配两种数据结构。

接下来我们就照着这个思路，把我们之前写的哈希桶版本改造成能复用的 HashTable，再用它封装出 unordered_map 和 unordered_set。

2. 我们已有的哈希桶

在上一篇博客中，我们完成了一个开放地址法（线性探测）和哈希桶（链地址法）的 HashTable。其中哈希桶版本结构大致如下（namespace hash_bucket）：

template<class K, class V>
struct HashNode {
pair<K, V> _kv;
HashNode<K, V>* _next;
HashNode(const pair<K,V>& kv)
: _kv(kv)
, _next(nullptr)
{}
};

template<class K, class V, class Hash = HashFunc<K>>
class HashTable {
typedef HashNode<K, V> Node;
// …
vector<Node*> _tables; // 指针数组
size_t _n = 0; // 有效数据个数
};

它只能存储 pair<K,V>，Find 查找也是直接用 cur->_kv.first == key 比较。现在我们要让它能适应 unordered_set（只存 K）和 unordered_map（存 pair<const K, V>）两种类型。怎么做？最关键的一步就是把数据类型抽象成模板参数 T，并引入 KeyOfT 仿函数。

3. 打造通用型 HashTable（支持泛型 T）

3.1 节点模板改为只含 T

原来节点里是 pair<K, V> _kv，现在改成 T _data。因为 T 可以是 K（对 set），也可以是 pair<const K, V>（对 map）。节点也相应变成：

namespace hash_bucket
{
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;

HashNode(const T& data)
:_data(data)
,_next(nullptr)
{}
};
// …
}

3.2 HashTable 模板参数增加 KeyOfT

原版：template<class K, class V, class Hash = HashFunc<K>> 新版：template<class K, class T, class KeyOfT, class Hash>

K 依然是键类型，T 是节点中真正存储的数据类型（可能是 K 也可能是 pair<const K, V>）。KeyOfT 是一个仿函数类型，它的任务就是从 T 类型的对象中提取出 K 类型的键。

例如：

对 unordered_set：T = K，KeyOfT 直接返回 key 本身。
对 unordered_map：T = pair<const K, V>，KeyOfT 返回 pair.first。

3.3 在 Insert、Find、Erase 中使用 KeyOfT

原先 Find 里这样比较：if (cur->_kv.first == key) 现在要变成：KeyOfT kot; if (kot(cur->_data) == key)

在计算哈希桶下标时，也同样先用 kot 取出键，再进行哈希和取模：

KeyOfT kot;
size_t hashi = hash(kot(data)) % _tables.size();

这样一来，HashTable 就完全不再关心 T 到底是个啥，只要 KeyOfT 能从中取出 K，它就能正常工作。

3.4 改造 Insert 返回值，为 operator[] 准备

原来插入返回 bool，但是 map::operator[] 需要返回 mapped_type 的引用，通常是通过 insert 返回的迭代器实现的。标准库的做法是：insert 返回 pair<iterator, bool>。

因此我们把哈希桶的 Insert 返回值类型改成：

pair<Iterator, bool> Insert(const T& data)

同时在函数内部去重检查时也利用迭代器。插入成功时返回 {Iterator(newnode, this), true}；失败时返回 {it, false}。

代码实现：

pair<Iterator, bool> Insert(const T& data)
{
KeyOfT kot;
Iterator it = Find(kot(data));
if (it != End())
return {it, false}; // 已存在

Hash hash;
// 负载因子 1：当 _n == 表大小时扩容
if (_n == _tables.size())
{
vector<Node*> newTable(__stl_next_prime(_tables.size() + 1));
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
size_t hashi = hash(kot(cur->_data)) % newTable.size();
// 头插到新表
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newTable);
}

size_t hashi = hash(kot(data)) % _tables.size();
Node* newnode = new Node(data);
// 头插
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;

return {Iterator(newnode, this), true};
}

4. 实现哈希表迭代器 —— 最难的点 operator++

哈希表迭代器是单向迭代器（只支持 ++）。它的实现思路和 list 迭代器很像：封装一个节点指针，然后重载 *、->、!=、++。

但哈希表的 operator++ 有一个特有的难点：当当前桶走完了，如何找到下一个非空桶？

答案在 SGI-STL 源码里就给出了：迭代器内部不仅要保存当前节点的指针，还要保存整个哈希表的指针。有了哈希表指针，就能访问 _tables 数组，计算出当前所在桶的下标，然后向后找下一个非空桶。

在这里插入图片描述

因此我们的迭代器设计如下：

template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> HT;
typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;

Node* _node; // 当前指向的节点
const HT* _ht; // 哈希表对象指针，用于寻找下一个桶

HTIterator(Node* node, const HT* ht)
:_node(node)
,_ht(ht)
{}
// …
};

为什么 _ht 是 const HT*？因为我们希望普通 Iterator 和 ConstIterator 都持有 const HT*，这样可以给 ConstIterator 传入 const HashTable 时也能兼容。如果你理解了 const_iterator 的本质是一个不能修改元素的迭代器，就明白这里把哈希表指针用 const 是合适的。

4.1 解引用和访问成员

Ref operator*()
{
return _node->_data;
}

Ptr operator->()
{
return &_node->_data;
}

模板参数 Ref 和 Ptr 用来区分普通迭代器和 const 迭代器：

普通迭代器：Ref = T&，Ptr = T*
const 迭代器：Ref = const T&，Ptr = const T*

4.2 不等于比较

bool operator!=(const Self& s)
{
return _node != s._node;
}

4.3 最核心的 operator++：跨桶找下一个节点

流程：

如果当前节点的 _next 不为空，直接走链表下一个节点。

如果当前桶已经走完（_next == nullptr），就计算出当前节点 key 对应的桶下标 hashi，然后从 hashi+1 开始遍历 _tables 数组，找到第一个非空的桶，将其头节点赋给 _node。

如果一直到数组末尾都没有非空桶，说明遍历结束，_node 置为 nullptr，即为 end()。

代码实现：

Self& operator++()
{
if (_node->_next)
{
_node = _node->_next; // 桶内还有数据，走到当前桶的下一个节点
}
else
{
// 当前桶走完了，找下一个不为空的桶
KeyOfT kot;
Hash hash;
size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();
++hashi;
while (hashi < _ht->_tables.size())
{
_node = _ht->_tables[hashi];
if (_node)
break;
else
++hashi;
}
if (hashi == _ht->_tables.size())
{
_node = nullptr;
}
}
return *this;
}

特别注意：计算当前节点 key 的哈希值时，我们使用了 KeyOfT kot 和 Hash hash，这正是泛型的威力。对于 unordered_map，_node->_data 是 pair，kot 会取出它的 first；对于 unordered_set，就是 key 本身。哈希函数同样支持自定义。

4.4 友元声明与类型别名

为了让 HTIterator 访问 HashTable 的私有成员 _tables，我们需要在 HashTable 中前置声明并友元化整个迭代器模板。

注意：由于 HTIterator 和 HashTable 互相引用，在 HashTable 定义之前必须先前置声明 HashTable。我们在 HTIterator 之前加了：

template<class K, class T, class KeyOfT, class Hash>
class HashTable; // 前置声明

然后在 HashTable 内部声明友元：

template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
friend struct HTIterator;

4.5 Begin() 和 End() 的实现

Begin() 要返回第一个非空桶的第一个节点的迭代器；如果哈希表为空，返回 End()。

Iterator Begin()
{
if (_n == 0)
return End();
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
if (cur)
{
return Iterator(cur, this); // 迭代器绑定当前哈希表
}
}
return End();
}

Iterator End()
{
return Iterator(nullptr, this); // end 迭代器的节点指针为空
}

// const 版本类似
ConstIterator Begin() const
{
if (_n == 0)
return End();
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
if (cur)
{
return ConstIterator(cur, this);
}
}
return End();
}

ConstIterator End() const
{
return ConstIterator(nullptr, this);
}

这样上层容器直接调用 _ht.Begin() 和 _ht.End() 即可获得迭代器。

5. 完整的 HashTable 实现解析

现在我们把改造后的 HashTable 完整展示出来。

#pragma once
#include<iostream>
#include<vector>
#include <utility>
#include <string>
#include <algorithm>
using namespace std;

// ———- 哈希函数 ———-
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};

template<>
struct HashFunc<string> // 特化 string 的哈希函数
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto ch : s)
{
hash += ch;
hash *= 131; // BKDR 哈希
}
return hash;
}
};

// ———- SGI-STL 质数表 ———-
inline unsigned long __stl_next_prime(unsigned long n)
{
static const int __stl_num_primes = 28;
static const unsigned long __stl_prime_list[__stl_num_primes] = {
53, 97, 193, 389, 769,
1543, 3079, 6151, 12289, 24593,
49157, 98317, 196613, 393241, 786433,
1572869, 3145739, 6291469, 12582917, 25165843,
50331653, 100663319, 201326611, 402653189, 805306457,
1610612741, 3221225473, 4294967291
};
const unsigned long* first = __stl_prime_list;
const unsigned long* last = __stl_prime_list + __stl_num_primes;
const unsigned long* pos = lower_bound(first, last, n);
return pos == last ? *(last – 1) : *pos;
}

// ———- 哈希桶命名空间 ———-
namespace hash_bucket
{
// 通用节点
template<class T>
struct HashNode
{
T _data;
HashNode<T>* _next;

HashNode(const T& data)
:_data(data)
,_next(nullptr)
{}
};

// 前置声明，以便 HTIterator 使用
template<class K, class T, class KeyOfT, class Hash>
class HashTable;

// 哈希表迭代器
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> HT;
typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;

Node* _node;
const HT* _ht; // 哈希表指针，用于跨桶

HTIterator(Node* node, const HT* ht)
:_node(node)
,_ht(ht)
{}

Ref operator*() { return _node->_data; }
Ptr operator->() { return &_node->_data; }

bool operator!=(const Self& s) { return _node != s._node; }

Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
KeyOfT kot;
Hash hash;
size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();
++hashi;
while (hashi < _ht->_tables.size())
{
_node = _ht->_tables[hashi];
if (_node) break;
else ++hashi;
}
if (hashi == _ht->_tables.size())
_node = nullptr;
}
return *this;
}
};

// 通用哈希表
template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
// 让迭代器访问私有成员 _tables
template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash>
friend struct HTIterator;

typedef HashNode<T> Node;
public:
typedef HTIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;
typedef HTIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;

// ———- begin / end ———-
Iterator Begin()
{
if (_n == 0) return End();
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
if (cur) return Iterator(cur, this);
}
return End();
}

Iterator End()
{
return Iterator(nullptr, this);
}

ConstIterator Begin() const
{
if (_n == 0) return End();
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
if (cur) return ConstIterator(cur, this);
}
return End();
}

ConstIterator End() const
{
return ConstIterator(nullptr, this);
}

// 构造、拷贝、赋值、析构
HashTable()
:_tables(__stl_next_prime(0))
,_n(0)
{}

HashTable(const HashTable& ht)
:_tables(ht._tables.size(), nullptr), _n(ht._n)
{
for (size_t i = 0; i < ht._tables.size(); i++)
{
Node* cur = ht._tables[i];
Node* tail = nullptr;
while (cur)
{
Node* newnode = new Node(cur->_data);
if (tail == nullptr)
_tables[i] = newnode;
else
tail->_next = newnode;
tail = newnode;
cur = cur->_next;
}
}
}

void swap(HashTable& tmp)
{
_tables.swap(tmp._tables);
std::swap(_n, tmp._n);
}

HashTable& operator=(HashTable tmp)
{
swap(tmp);
return *this;
}

~HashTable()
{
for (size_t i = 0; i < _tables.size(); i++)
{
Node* cur = _tables[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_tables[i] = nullptr;
}
}

// ———- 核心功能 ———-
pair<Iterator, bool> Insert(const T& data)
{
KeyOfT kot;
Iterator it = Find(kot(data));
if (it != End())
return {it, false}; // 已存在

size_t hashi = hash(kot(data)) % _tables.size();
Node* newnode = new Node(data);
// 头插
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;

return {Iterator(newnode, this), true};
}

Iterator Find(const K& key)
{
KeyOfT kot;
Hash hash;
size_t hashi = hash(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur)
{
if (kot(cur->_data) == key)
return Iterator(cur, this);
cur = cur->_next;
}
return End();
}

bool Erase(const K& key)
{
KeyOfT kot;
Hash hash;
size_t hashi = hash(key) % _tables.size();
Node* prev = nullptr;
Node* cur = _tables[hashi];

while (cur)
{
if (kot(cur->_data) == key)
{
if (prev == nullptr)
_tables[hashi] = cur->_next;
else
prev->_next = cur->_next;
delete cur;
—_n;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}

private:
vector<Node*> _tables; // 指针数组
size_t _n = 0; // 有效数据个数
};
}

补充说明：

扩容策略与之前一致：使用 SGI-STL 质数表 __stl_next_prime 获取下一个桶大小，并将旧表节点重新映射到新表（头插法）。
拷贝构造需要深拷贝所有节点和链表，保持原结构。
swap 和 operator= 使用现代 C++ 的 copy-and-swap 惯用法，既安全又简洁。
Begin() 通过遍历找到第一个非空桶的头节点；End() 返回持有 nullptr 的迭代器。

6. 封装 unordered_map 和 unordered_set

现在 HashTable 已经通用了，我们只需在 unordered_map 和 unordered_set 中：

定义自己的 KeyOfT 仿函数。

用具体的模板参数实例化 hash_bucket::HashTable。

把容器接口转发给 _ht 成员。

6.1 unordered_set 的封装

#include "HashTable.h"

namespace hj
{
template<class K, class Hash = HashFunc<K>>
class unordered_set
{
// 仿函数：从 K 中取出 K（就返回自身）
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};

public:
// 注意：HashTable 第二个模板参数是 const K，因为 set 的 key 不可修改
typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::Iterator iterator;
typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::ConstIterator const_iterator;

iterator begin() { return _ht.Begin(); }
iterator end() { return _ht.End(); }
const_iterator begin() const { return _ht.Begin(); }
const_iterator end() const { return _ht.End(); }

pair<iterator, bool> insert(const K& key)
{
return _ht.Insert(key);
}

iterator Find(const K& key)
{
return _ht.Find(key);
}

bool Erase(const K& key)
{
return _ht.Erase(key);
}

private:
hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;
};
}

要点解析：

SetKeyOfT：operator() 接收 K 并返回 K，非常直接。
传给 HashTable 的 T 是 const K。这保证了 iterator 指向的元素是不可修改的，即使你使用普通迭代器，也不能通过 *it 修改值（因为类型是 const K）。
insert 返回 pair<iterator, bool>，方便了后续的 unordered_map::operator[]。
对外接口只暴露 key，完全隐藏了底层的哈希表细节。

6.2 unordered_map 的封装

#include "HashTable.h"

namespace hj
{
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map
{
// 仿函数：从 pair<const K, V> 中取出键 K
struct MapKeyOfT
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};

public:
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;
typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator const_iterator;

iterator begin() { return _ht.Begin(); }
iterator end() { return _ht.End(); }
const_iterator begin() const { return _ht.Begin(); }
const_iterator end() const { return _ht.End(); }

// operator[] 的实现依赖 insert
V& operator[](const K& key)
{
// 插入一个 key，如果不存在则映射值为默认构造的 V()
pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
return ret.first->second;
}

pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}

iterator Find(const K& key)
{
return _ht.Find(key);
}

bool Erase(const K& key)
{
return _ht.Erase(key);
}

private:
hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};
}

要点解析：

MapKeyOfT 从 pair 中取出 first，注意 pair 的 Key 是 const K。
传给 HashTable 的 T 是 pair<const K, V>，key 类型不可变，但 value 可变。
operator[] 的行为与标准库一致：
若 key 已存在，Insert 返回已存在节点的迭代器，并返回 bool = false，然后 ret.first->second 就是那个 value 的引用。
若 key 不存在，Insert 插入一个 pair(key, V()) 并返回新节点的迭代器，ret.first->second 是默认构造的 V()。
这样无论是读还是写，operator[] 都能正确工作。

7. 容易踩的坑与设计细节回顾

7.1 迭代器为什么需要 _ht 指针

在实现 ++ 时，我们已经强调过：哈希表的桶不是连续内存，节点之间只有同一个桶内的 _next 指向关系，跨桶是无法用单纯的节点指针解决的。因此迭代器必须持有一个指向哈希表的指针，以便在走到桶末尾时访问 _tables 数组找到下一个非空桶。

7.2 拷贝构造时的链表深度复制

哈希表在拷贝构造时，不能简单地将 _tables 指针数组复制过来，因为那会导致两个对象指向同一批节点，析构时会发生重复释放。正确做法是逐桶遍历原表，为每个节点创建新的副本，并按相同顺序链接。

7.3 SetKeyOfT / MapKeyOfT 的作用

这是整个封装的核心。底层哈希表完全不知道它存的是单独的 K 还是 pair<const K, V>，它只通过 KeyOfT 这个仿函数从 T 类型的对象中取出 K，用于计算哈希值和比较是否相等。上层容器通过提供不同的仿函数，实现了数据结构的复用。

7.4 如何保证键不可修改

unordered_set：将 T 指定为 const K，节点中存储的就是不可修改的值。
unordered_map：将 T 指定为 pair<const K, V>，pair 的 first 自动成为 const，而 second 可修改。

两者都从类型系统层面阻止了用户通过迭代器修改键。

7.5 扩容时元素重新映射

我们在 Insert 中，当 _n == _tables.size() 时进行扩容。扩容后每个节点的桶位置可能发生变化，因此需要遍历原表所有节点，重新计算哈希值并挂到新表的对应桶上。这里我们使用了头插法，避免遍历链表找尾节点，提高效率。

7.6 operator[] 的细节

operator[] 用了 make_pair(key, V())，V() 会调用值类型的默认构造函数生成一个默认值。如果键已存在，插入失败，返回已存在节点；如果不存在，则新插入一个包含默认值的节点，最后统一返回值的引用。

结语：

今天的内容到这里就结束了，希望你能有所收获~

干货整理到手抖，觉得有用的话，赏个三连回回血？__(:ᗤ」ㄥ)_ _

【C++ STL篇(十五)】哈希表封装 unordered_map 和 unordered_set

C++ STL篇(十五) —— 哈希表封装 unordered_map 和 unordered_set

文章目录

1. 站在巨人的肩膀上：SGI-STL 源码框架分析

2. 我们已有的哈希桶

3. 打造通用型 HashTable（支持泛型 T）

3.1 节点模板改为只含 T

3.2 HashTable 模板参数增加 KeyOfT

3.3 在 Insert、Find、Erase 中使用 KeyOfT

3.4 改造 Insert 返回值，为 operator[] 准备

4. 实现哈希表迭代器 —— 最难的点 operator++

4.1 解引用和访问成员

4.2 不等于比较

4.3 最核心的 operator++：跨桶找下一个节点

4.4 友元声明与类型别名

4.5 Begin() 和 End() 的实现

5. 完整的 HashTable 实现解析

6. 封装 unordered_map 和 unordered_set

6.1 unordered_set 的封装

6.2 unordered_map 的封装

7. 容易踩的坑与设计细节回顾

7.1 迭代器为什么需要 _ht 指针

7.2 拷贝构造时的链表深度复制

7.3 SetKeyOfT / MapKeyOfT 的作用

7.4 如何保证键不可修改

7.5 扩容时元素重新映射

7.6 operator[] 的细节

结语：

相关推荐

评论抢沙发

热门标签

热门文章

最新文章

归档

分类

C++ STL篇(十五) —— 哈希表封装 unordered_map 和 unordered_set

文章目录

1. 站在巨人的肩膀上：SGI-STL 源码框架分析

2. 我们已有的哈希桶

3. 打造通用型 HashTable（支持泛型 T）

3.1 节点模板改为只含 T

3.2 HashTable 模板参数增加 KeyOfT

3.3 在 Insert、Find、Erase 中使用 KeyOfT

3.4 改造 Insert 返回值，为 operator[] 准备

4. 实现哈希表迭代器 —— 最难的点 operator++

4.1 解引用和访问成员

4.2 不等于比较

4.3 最核心的 operator++：跨桶找下一个节点

4.4 友元声明与类型别名

4.5 Begin() 和 End() 的实现

5. 完整的 HashTable 实现解析

6. 封装 unordered_map 和 unordered_set

6.1 unordered_set 的封装

6.2 unordered_map 的封装

7. 容易踩的坑与设计细节回顾

7.1 迭代器为什么需要 _ht 指针

7.2 拷贝构造时的链表深度复制

7.3 SetKeyOfT / MapKeyOfT 的作用

7.4 如何保证键不可修改

7.5 扩容时元素重新映射

7.6 operator[] 的细节

结语：

相关推荐

评论 抢沙发

热门标签

热门文章

最新文章

归档

分类

评论抢沙发