C++算法
C++红黑树封装实战：从零实现 MyMap 与 MySet
C++红黑树封装实战，基于泛型编程思想复用红黑树底层结构。通过 KeyOfT 仿函数区分 set 和 map 的键值存储逻辑，实现迭代器中序遍历支持 ++/--操作。代码包含 RBTree 核心类、Map 容器及 Set 容器的完整模拟实现，演示了 insert、find、operator[] 等关键功能，并验证了红黑树平衡调整与节点访问的正确性。
C++红黑树封装实战，基于泛型编程思想复用红黑树底层结构。通过 KeyOfT 仿函数区分 set 和 map 的键值存储逻辑，实现迭代器中序遍历支持 ++/--操作。代码包含 RBTree 核心类、Map 容器及 Set 容器的完整模拟实现，演示了 insert、find、operator[] 等关键功能，并验证了红黑树平衡调整与节点访问的正确性。
非官方文档：cplusplus
官方文档（同步更新）：cppreference
set和multiset的参考文档：set、multiset
map和multimap的参考文档：map、multimap
封装红黑树的难度主要在于结构而非逻辑。
SGI—STL30版本源代码中，map和set的源代码在 map / set / stl_map.h / stl_set.h / stl_tree.h 等头文件中。建议查看中间版本的源码，避免最新源码经过过多优化导致难以理解。
stl_tree.h：
stl_set.h：
stl_map.h：
底层均使用红黑树实现，区别在于模板参数。Key 为第一个模板参数，value 为第二个。对于 set，第二个参数是 Key；对于 map，第二个参数是 pair<const key, T>。
源码中的 rb_tree 实现了泛型思想，通过第二个模板参数 value 决定节点存储的数据类型。
set 实例化时第二个参数给的是 Key。map 实例化时第二个参数给的是 pair<const key, T>。这样一棵红黑树既可以实现 Key 搜索场景的 set，也可以实现 Key/Value 搜索场景的 map。
注意源码中模板参数用 T 代表 value，内部 value_type 指红黑树节点中存储的真实数据类型。
第一个模板参数 Key 主要用于 find / erase 等函数的形参类型。对于 set，两个参数相同；对于 map，插入的是 pair 对象，但查找/删除的是 Key 对象。
参考源码框架，map和set复用红黑树。调整参数命名：key 用 K，value 用 V，红黑树数据类型用 T。
由于 RBTree 是泛型的，无法直接比较 pair 或 K，需要分别实现 MapKeyOfT 和 SetKeyOfT 仿函数传给 RBTree 的 KeyOfT，用于取出对象中的 key 进行比较。
iterator核心代码：
template<class T, class Ref, class Ptr> struct RBTreeIterator {
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;
RBTreeIterator(Node* node) :_node(node) { }
Ref operator*() { return _node->_data; }
Ptr operator->() { return &_node->_data; }
Self& operator++() {
if (_node->_right) {
Node* minRight = _node->_right;
while (minRight->_left) { minRight = minRight->_left; }
_node = minRight;
} else {
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right) {
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
bool operator!=(const Self& s) { return _node != s._node; }
bool operator==(const Self& s) { return _node == s._node; }
};
iterator 大框架与 list 一致，封装结点指针并重载运算符。
operator++ 核心逻辑：
end() 表示： 当 it 指向最右结点且继续 ++ 时，若无父节点，将结点指针置为 nullptr 充当 end。
set 的 iterator：
不支持修改，第二个模板参数改为 const K。
RBTree<K, const K, SetKeyOfT> _t;
map 的 iterator：
不支持修改 key 但可以修改 value，第二个模板参数 pair 的第一个参数改为 const K。
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
pair<Iterator, bool>。operator[] 调用 insert，若存在则修改 value，不存在则插入默认值。template<class T, class Ref, class Ptr> struct RBTreeIterator {
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;
RBTreeIterator(Node* node) :_node(node) { }
Ref operator*() { return _node->_data; }
Ptr operator->() { return &_node->_data; }
Self& operator++() {
if (_node->_right) {
Node* minRight = _node->_right;
while (minRight->_left) { minRight = minRight->_left; }
_node = minRight;
} else {
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right) { cur = parent; parent = parent->_parent; }
_node = parent;
}
return *this;
}
bool operator!=(const Self& s) { return _node != s._node; }
bool operator==(const Self& s) { return _node == s._node; }
};
template<class K, class T, class KeyOfT> struct RBTree {
typedef RBTreeNode<T> Node;
public:
typedef RBTreeIterator<T, T&, T*> Iterator;
typedef RBTreeIterator<T, T&, T*> ConstIterator;
~() { (_root); _root = ; }
{
Node* minLeft = _root;
(minLeft && minLeft->_left) { minLeft = minLeft->_left; }
(minLeft);
}
{ (); }
{
Node* minLeft = _root;
(minLeft && minLeft->_left) { minLeft = minLeft->_left; }
(minLeft);
}
{ (); }
{
(_root == ) {
_root = (data);
_root->_col = BLACK;
{ (_root), };
}
KeyOfT kot;
Node* parent = ;
Node* cur = _root;
(cur) {
((cur->_data) < (data)) {
parent = cur;
cur = cur->_right;
} ((data) < (cur->_data)) {
parent = cur;
cur = cur->_left;
} {
{ (cur), };
}
}
cur = (data);
Node* newnode = cur;
cur->_col = RED;
((parent->_data) < (data)) {
parent->_right = cur;
} {
parent->_left = cur;
}
cur->_parent = parent;
(parent && parent->_col == RED) {
Node* grandfather = parent->_parent;
(grandfather->_left == parent) {
Node* uncle = grandfather->_right;
(uncle && uncle->_col == RED) {
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
} {
(cur == parent->_left) {
(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
} {
(parent);
(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
;
}
} {
Node* uncle = grandfather->_left;
(uncle && uncle->_col == RED) {
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
} {
(cur == parent->_right) {
(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
} {
(parent);
(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
;
}
}
}
_root->_col = BLACK;
{ (newnode), };
}
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
(subLR) subLR->_parent = parent;
Node* parentParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
(parent == _root) {
_root = subL;
subL->_parent = ;
} {
(parentParent->_left == parent) {
parentParent->_left = subL;
} {
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
(subRL) subRL->_parent = parent;
Node* parentParent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
(parentParent == ) {
_root = subR;
subR->_parent = ;
} {
(parent == parentParent->_left) {
parentParent->_left = subR;
} {
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
{
KeyOfT kot;
Node* cur = _root;
(cur) {
((cur->_data) < key) {
cur = cur->_right;
} ((cur->_data) > key) {
cur = cur->_left;
} {
(cur);
}
}
();
}
{ _Height(_root); }
{ _Size(_root); }
:
_Size(Node* root) {
(root == ) ;
_Size(root->_left) + _Size(root->_right) + ;
}
_Height(Node* root) {
(root == ) ;
leftHeight = _Height(root->_left);
rightHeight = _Height(root->_right);
leftHeight > rightHeight ? leftHeight + : rightHeight + ;
}
{
(root == ) ;
(root->_left);
(root->_right);
root;
}
:
Node* _root = ;
};
#pragma once
#include"RBTree.h"
namespace jqj {
template<class K, class V> class map {
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, > { .(kv); }
{ .(key); }
V& []( K& key) {
[it, flag] = .({ key, () });
it->second;
}
:
RBTree<K, pair< K, V>, MapKeyOfT> ;
};
}
#pragma once
#include"RBTree.h"
namespace jqj {
template<class K> class set {
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( K& key) { .(key); }
{ .(key); }
:
RBTree<K, K, SetKeyOfT> ;
};
}
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;
#include"RBTree.h"
#include"Map.h"
#include"Set.h"
template<class T> void func(const jqj::set<T>& s) {
typename jqj::set<T>::const_iterator it = s.begin();
while (it != s.end()) {
cout << *it << " ";
++it;
}
cout << endl;
}
void Test_set() {
jqj::set<int> s;
s.insert(1); s.insert(2); s.insert(1); s.insert(5);
s.insert(0); s.insert(10); s.insert(8);
jqj::set<int>::iterator it = s.begin();
while (it != s.end()) {
cout << *it << " ";
++it;
}
cout << endl;
(s);
}
{
jqj::map<string, string> dict;
dict.({ , });
dict.({ , });
dict.({ , });
dict[] = ;
dict[] = ;
it = dict.();
(it != dict.()) {
it->second += ;
cout << it->first << << it->second << endl;
++it;
}
cout << endl;
(& [k, v] : dict) {
cout << k << << v << endl;
}
cout << endl;
string arr[] = { , , , , , , , , , , };
jqj::map<string, > countMap;
(& e : arr) {
countMap[e]++;
}
(& [k, v] : countMap) {
cout << k << << v << endl;
}
cout << endl;
}
{
();
();
;
}
（程序输出展示了有序遍历的 set 元素及 map 的键值对统计结果）
本文基于泛型编程思想，利用红黑树底层结构封装了 C++ 标准库中的 map 和 set 容器，重点讲解了迭代器的中序遍历实现及红黑树的平衡调整逻辑。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online