C++进阶：红黑树封装map/set & 哈希表unordered系列容器详解
·
C++进阶：红黑树封装map/set & 哈希表unordered系列容器详解
本文基于SGI-STL源码思想，完整实现红黑树封装map/set，并对比讲解unordered_map/unordered_set使用与底层差异，代码可直接编译运行，适合C++后端/STL源码学习。
文章目录
一、前言：STL关联式容器底层
C++ STL 关联式容器分为两大派系：
- 红黑树派系：
map/set/multimap/multiset—— 有序、去重、O(logN) - 哈希表派系：
unordered_map/unordered_set—— 无序、去重、平均O(1)
本文先从红黑树封装map/set讲起，再对比哈希表unordered系列，带你吃透底层设计。
二、红黑树封装 map / set 核心思想
SGI-STL 中 map/set 底层共用一棵红黑树，通过泛型+仿函数解耦，实现一套红黑树支撑两种容器：
set：只存 key → 红黑树结点存Keymap：存 key-value → 红黑树结点存pair<const Key, Value>- 比较时只比 key，通过仿函数从结点数据中提取 key
2.1 关键设计点
- 红黑树模板参数
template<class K, class T, class KeyOfT>
class RBTree;
- K：查找用的 key 类型
- T：结点实际存储数据（set=K，map=pair<const K,V>）
- KeyOfT：仿函数，从 T 中提取 key 用于比较
- set 封装：提取自身作为 key
- map 封装：提取 pair.first 作为 key
- 迭代器：中序遍历，模拟指针行为
- map operator[]：插入+返回 value 引用
三、完整代码实现（可直接运行）
3.1 红黑树结点与颜色定义
#pragma once
#include <iostream>
#include <utility>
using namespace std;
enum Colour
{
RED,
BLACK
};
// 红黑树结点
template<class T>
struct RBTreeNode
{
T _data;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Colour _col;
RBTreeNode(const T& data)
: _data(data)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(RED) // 新结点默认红色
{}
};
3.2 红黑树迭代器实现
// 红黑树迭代器
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;
Node* _root;
RBTreeIterator(Node* node, Node* root)
:_node(node)
,_root(root)
{}
// ++：中序下一个
Self& operator++()
{
if (_node->_right)
{
// 右子树最左结点
Node* leftMost = _node->_right;
while (leftMost->_left)
leftMost = leftMost->_left;
_node = leftMost;
}
else
{
// 向上找：孩子是父亲左的祖先
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
// --：中序上一个
Self& operator--()
{
if (_node == nullptr) // --end()
{
Node* rightMost = _root;
while (rightMost && rightMost->_right)
rightMost = rightMost->_right;
_node = rightMost;
}
else if (_node->_left)
{
// 左子树最右结点
Node* rightMost = _node->_left;
while (rightMost->_right)
rightMost = rightMost->_right;
_node = rightMost;
}
else
{
// 向上找：孩子是父亲右的祖先
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
Ref operator*() { return _node->_data; }
Ptr operator->() { return &_node->_data; }
bool operator!= (const Self& s) const { return _node != s._node; }
bool operator== (const Self& s) const { return _node == s._node; }
};
3.3 红黑树主体（插入+旋转+平衡）
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef RBTreeIterator<T, T&, T*> Iterator;
typedef RBTreeIterator<T, const T&, const T*> ConstIterator;
Iterator Begin()
{
Node* leftMost = _root;
while (leftMost && leftMost->_left)
leftMost = leftMost->_left;
return Iterator(leftMost, _root);
}
Iterator End() { return Iterator(nullptr, _root); }
ConstIterator Begin() const
{
Node* leftMost = _root;
while (leftMost && leftMost->_left)
leftMost = leftMost->_left;
return ConstIterator(leftMost, _root);
}
ConstIterator End() const { return ConstIterator(nullptr, _root); }
// 插入：返回<迭代器, 是否插入成功>
pair<Iterator, bool> Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(Iterator(_root, _root), true);
}
KeyOfT kot;
Node* parent = nullptr;
Node* cur = _root;
// 1. 搜索插入位置
while (cur)
{
if (kot(cur->_data) < kot(data))
{
parent = cur;
cur = cur->_right;
}
else if (kot(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else // 已存在
return make_pair(Iterator(cur, _root), false);
}
// 2. 插入新结点
cur = new Node(data);
Node* newNode = cur;
cur->_col = RED;
if (kot(parent->_data) < kot(data)) parent->_right = cur;
else parent->_left = cur;
cur->_parent = parent;
// 3. 平衡调整
while (parent && parent->_col == RED)
{
Node* grandfather = parent->_parent;
if (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;
// 情况1：叔叔存在且为红 → 变色
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else // 情况2/3：叔叔黑或不存在 → 旋转
{
if (cur == parent->_left)
{
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else // 对称：parent在右
{
Node* uncle = grandfather->_left;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return make_pair(Iterator(newNode, _root), true);
}
// 查找
Iterator Find(const K& key)
{
Node* cur = _root;
KeyOfT kot;
while (cur)
{
if (kot(cur->_data) < key) cur = cur->_right;
else if (kot(cur->_data) > key) cur = cur->_left;
else return Iterator(cur, _root);
}
return End();
}
private:
// 左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL) subRL->_parent = parent;
Node* pp = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (pp == nullptr) { _root = subR; subR->_parent = nullptr; }
else
{
if (pp->_left == parent) pp->_left = subR;
else pp->_right = subR;
subR->_parent = pp;
}
}
// 右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR) subLR->_parent = parent;
Node* pp = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (pp == nullptr) { _root = subL; subL->_parent = nullptr; }
else
{
if (pp->_left == parent) pp->_left = subL;
else pp->_right = subL;
subL->_parent = pp;
}
}
void Destroy(Node* root)
{
if (root == nullptr) return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
private:
Node* _root = nullptr;
};
3.4 封装 set
#pragma once
#include "RBTree.h"
namespace bit
{
template<class K>
class set
{
// 仿函数：从key提取key
struct SetKeyOfT
{
const K& operator()(const K& key) { return key; }
};
public:
typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;
iterator begin() { return _t.Begin(); }
iterator end() { return _t.End(); }
const_iterator begin() const { return _t.Begin(); }
const_iterator end() const { return _t.End(); }
pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key);
}
iterator find(const K& key)
{
return _t.Find(key);
}
private:
RBTree<K, const K, SetKeyOfT> _t;
};
}
3.5 封装 map（含 operator[]）
#pragma once
#include "RBTree.h"
namespace bit
{
template<class K, class V>
class map
{
// 仿函数：从pair提取key
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv) { return kv.first; }
};
public:
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;
iterator begin() { return _t.Begin(); }
iterator end() { return _t.End(); }
const_iterator begin() const { return _t.Begin(); }
const_iterator end() const { return _t.End(); }
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
iterator find(const K& key)
{
return _t.Find(key);
}
// map核心：operator[]
V& operator[](sslocal://flow/file_open?url=const+K%26+key&flow_extra=eyJsaW5rX3R5cGUiOiJjb2RlX2ludGVycHJldGVyIn0=)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
}
3.6 测试代码
#include "MySet.h"
#include "MyMap.h"
void test_set()
{
bit::set<int> s;
int arr[] = { 4,2,6,1,3,5,15,7,16,14 };
for (auto e : arr) s.insert(e);
// 遍历有序
for (auto e : s) cout << e << " ";
cout << endl;
}
void test_map()
{
bit::map<string, string> dict;
dict.insert({ "sort","排序" });
dict.insert({ "left","左边" });
dict["right"] = "右边";
dict["insert"] = "插入";
for (auto& kv : dict)
cout << kv.first << " : " << kv.second << endl;
}
int main()
{
test_set();
test_map();
return 0;
}
四、unordered_map / unordered_set 使用与对比
4.1 底层结构
unordered_map/unordered_set：哈希桶（拉链法）- 平均
O(1)，最坏O(N)（哈希冲突严重） - 遍历无序
4.2 与红黑树容器核心差异
| 特性 | map/set | unordered_map/unordered_set |
|---|---|---|
| 底层 | 红黑树 | 哈希表（拉链法） |
| 顺序 | 有序（中序） | 无序 |
| 查找效率 | O(logN) | 平均O(1) |
| key要求 | 支持 < 比较 | 支持哈希、== 比较 |
| 迭代器类型 | 双向迭代器 | 单向迭代器 |
| 内存占用 | 较低 | 较高（哈希桶空间） |
4.3 使用示例
#include <unordered_map>
#include <unordered_set>
#include <iostream>
using namespace std;
void test_unordered()
{
unordered_set<int> us;
us.insert(1); us.insert(3); us.insert(2);
for (auto e : us) cout << e << " "; // 无序
unordered_map<string, int> um;
um["a"] = 1; um["b"] = 2;
cout << um["a"] << endl;
}
五、总结
- map/set 复用红黑树：通过泛型+仿函数提取 key，一套代码支撑两种容器。
- 迭代器本质：中序遍历，模拟指针，++/-- 严格遵循中序规则。
- map operator[]：
insert+ 返回 value 引用，是日常高频用法。 - unordered 系列：哈希表实现，无序、更快，适合纯查找场景。
更多推荐
9
0- 0
已为社区贡献2条内容
所有评论(0)