C++ 的两个参考文档
非官方文档：cplusplus 官方文档：cppreference
- set/multiset：set、multiset
- map/multimap：map、multimap
- unordered_set/multiset：unordered_set、unordered_multiset
- unordered_map/multimap：unordered_map、unordered_multimap
1. 浅解源码和框架
1.1 源码回顾
SGI STL 30 版本是 C++11 之前的标准，当时并没有 unordered_map 和 unordered_set。这两个容器是 C++11 引入的，而旧版 STL 中对应的是 hash_map 和 hash_set。它们属于非标准容器，即 C++ 标准未强制要求实现的部分。
1.2 核心框架
在 SGI STL 源码中，hash_map 和 hash_set 的实现结构非常清晰，核心逻辑集中在 stl_hashtable.h 中。hash_set 本质上是对 hashtable 的封装，传入的 Value 类型即为 Key；而 hash_map 则传入 pair<const Key, T> 作为 Value，通过提取器获取 Key。
// stl_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;
public:
// ... 省略部分 typedef 定义
};
// stl_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;
public:
// ... 省略部分 typedef 定义
};
可以看到，底层都复用了同一个 hashtable 实现。命名风格上确实比较随意，比如 hash_set 用 Value 做模板参数，而 hash_map 用 Key 和 T。我们在模拟实现时会统一规范命名。
2. 模拟实现 unordered_map 和 unordered_set
2.1 设计思路
复用哈希表框架
我们基于之前实现的通用 HashTable 进行封装。为了适配不同容器，需要解决泛型问题：HashTable 内部不知道存储的是 K 还是 pair<K,V>。因此，我们在 unordered_map 和 unordered_set 层分别实现仿函数（Functor），用于从存储对象中提取 Key，传给 HashTable 的 KeyOfT 参数。
迭代器实现难点
哈希表的迭代器是单向的。operator++ 的实现是核心：如果当前桶内还有节点，直接指向下一个节点；如果当前桶遍历完毕，则需要计算下一个不为空的桶位置。这要求迭代器持有哈希表对象的指针，以便访问桶数组。
Self& operator++() {
if (_node->_next) { // 当前桶没走完
_node = _node->_next;
} else { // 当前桶走完了，找下一个桶
KeyOfT kot; Hash hs;
size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
++hashi;
while (hashi < _pht->_tables.size()) {
if (_pht->_tables[hashi]) {
_node = _pht->_tables[hashi];
break;
}
++hashi;
}
if (hashi == _pht->_tables.size()) {
_node = nullptr; // 到达 end()
}
}
return *this;
}
支持 [] 运算符
unordered_map 需要支持 [] 操作符，这依赖于 insert 返回值的调整。修改 Insert 返回 pair<Iterator, bool>，即可轻松实现 [] 的逻辑：查找失败时插入新元素并返回引用。
2.2 完整代码示例
HashTable.h
这是底层哈希表的核心实现，包含节点定义、迭代器及扩容逻辑。
#pragma once
#include<vector>
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
};
inline unsigned long __stl_next_prime(unsigned long n) {
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;
}
template<class K> struct HashFunc {
size_t operator()(const K& key) { return (size_t)key; }
};
template<> struct HashFunc<string> {
size_t operator()(const string& key) {
size_t hash = 0;
for (auto ch : key) { hash += ch; hash *= 131; }
return hash;
}
};
namespace Hash_bucket {
template<class T> struct HashNode {
T _data;
HashNode<T>* _next;
HashNode(const T& data) :_data(data), _next(nullptr) {}
};
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 Self;
Node* _node;
const HT* _pht;
HTIterator(Node* node, const HT* pht) :_node(node), _pht(pht) {}
Ref operator*() { return _node->_data; }
Ptr operator->() { return &_node->_data; }
Self& operator++() {
if (_node->_next) {
_node = _node->_next;
} else {
KeyOfT kot; Hash hs;
size_t hashi = hs(kot(_node->_data)) % _pht->_tables.size();
++hashi;
while (hashi < _pht->_tables.size()) {
if (_pht->_tables[hashi]) {
_node = _pht->_tables[hashi];
break;
} else {
++hashi;
}
}
if (hashi == _pht->_tables.size()) {
_node = nullptr;
}
}
return *this;
}
bool operator!=(const Self & s) const { return _node != s._node; }
bool operator==(const Self & s) const { return _node == s._node; }
};
template<class K,class T,class KeyOfT,class Hash>
class HashTable {
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;
Iterator Begin() {
if (_n == 0) return End();
for (size_t i = 0; i < _tables.size(); i++) {
if (_tables[i]) return Iterator(_tables[i], 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++) {
if (_tables[i]) return ConstIterator(_tables[i], this);
}
return End();
}
ConstIterator End() const { return ConstIterator(nullptr, this); }
HashTable() :_tables(__stl_next_prime(1),nullptr), _n(0) {}
~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;
}
_n = 0;
}
pair<Iterator, bool> Insert(const T& data) {
KeyOfT kot;
if (auto it = Find(kot(data)); it != End()) return { it,false };
Hash hs;
if (_n == _tables.size()) {
std::vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr);
for (size_t i = 0; i < _tables.size(); i++) {
Node* cur = _tables[i];
while (cur) {
Node* next = cur->_next;
size_t hashi = hs(kot(cur->_data)) % newtables.size();
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
size_t hashi = hs(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 hs;
size_t hashi = hs(key) % _tables.size();
Node* cur = _tables[hashi];
while (cur) {
if (kot(cur->_data) == key) return { cur,this };
cur = cur->_next;
}
return { nullptr,this };
}
bool Erase(const K& key) {
KeyOfT kot; Hash hs;
size_t hashi = hs(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;
--_n;
delete cur;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
private:
std::vector<Node*> _tables;
size_t _n;
};
}
unordered_set.h
封装 HashTable，限制 Key 为不可变类型。
#pragma once
#include"HashTable.h"
namespace jqj {
template<class K, class Hash = HashFunc<K>>
class unordered_set {
struct SetKeyOfT {
const K& operator()(const K& key) { return key; }
};
public:
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;
};
}
unordered_map.h
封装 HashTable，支持 Key 不可变但 Value 可变，并提供 [] 操作符。
#pragma once
#include"HashTable.h"
namespace jqj {
template<class K, class V, class Hash = HashFunc<K>>
class unordered_map {
struct MapKeyOfT {
const K& operator()(const pair<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(); }
pair<iterator, bool> insert(const pair<K, V>& kv) { return _ht.Insert(kv); }
V& operator[](const K& key) {
pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
return ret.first->second;
}
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;
};
}
Test.cpp
测试代码，验证基本功能。
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<unordered_map>
using namespace std;
#include"unordered_map.h"
#include"unordered_set.h"
void Print(const jqj::unordered_set<int>& s) {
jqj::unordered_set<int>::const_iterator it = s.begin();
while (it != s.end()) {
cout << *it << " ";
++it;
}
cout << endl;
}
int main() {
jqj::unordered_set<int> us;
us.insert(3); us.insert(1000); us.insert(2);
us.insert(102); us.insert(2111); us.insert(22);
Print(us);
jqj::unordered_map<string, string> dict;
dict.insert({ "string","" });
dict.insert({ "left","左边" });
dict.insert({ "right","右边" });
dict["left"] = "左边";
dict["map"] = "地图";
for (auto& [k, v] : dict) {
cout << k << ":" << v << endl;
}
return 0;
}
运行结果将展示插入、查找及迭代遍历的正确性。
