C++的两个参考文档
非官方文档： 官方文档（同步更新）：
C++算法
C++红黑树封装实战：从零实现 MyMap 与 MySet
C++红黑树封装实战，基于泛型编程思想复用红黑树底层结构。通过 KeyOfT 仿函数区分 set 和 map 的键值存储逻辑，实现迭代器中序遍历支持 ++/--操作。代码包含 RBTree 核心类、Map 容器及 Set 容器的完整模拟实现，演示了 insert、find、operator[] 等关键功能，并验证了红黑树平衡调整与节点访问的正确性。
C++红黑树封装实战，基于泛型编程思想复用红黑树底层结构。通过 KeyOfT 仿函数区分 set 和 map 的键值存储逻辑，实现迭代器中序遍历支持 ++/--操作。代码包含 RBTree 核心类、Map 容器及 Set 容器的完整模拟实现，演示了 insert、find、operator[] 等关键功能，并验证了红黑树平衡调整与节点访问的正确性。
非官方文档： 官方文档（同步更新）：
封装红黑树的难度主要在于结构而非逻辑。
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, const T&, const T*> ConstIterator;
~RBTree() { Destroy(_root); _root = nullptr; }
Iterator Begin() {
Node* minLeft = _root;
while (minLeft && minLeft->_left) { minLeft = minLeft->_left; }
return Iterator(minLeft);
}
Iterator End() { return Iterator(nullptr); }
ConstIterator Begin() const {
Node* minLeft = _root;
while (minLeft && minLeft->_left) { minLeft = minLeft->_left; }
return ConstIterator(minLeft);
}
ConstIterator End() const { return ConstIterator(nullptr); }
pair<Iterator, bool> Insert(const T& data) {
if (_root == nullptr) {
_root = new Node(data);
_root->_col = BLACK;
return { Iterator(_root), true };
}
KeyOfT kot;
Node* parent = nullptr;
Node* cur = _root;
while (cur) {
if (kot(cur->_data) < kot(data)) {
parent = cur;
cur = cur->_right;
} else if (kot(data) < kot(cur->_data)) {
parent = cur;
cur = cur->_left;
} else {
return { Iterator(cur), false };
}
}
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;
while (parent && parent->_col == RED) {
Node* grandfather = parent->_parent;
if (grandfather->_left == parent) {
Node* uncle = grandfather->_right;
if (uncle && uncle->_col == RED) {
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
} else {
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 {
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 { Iterator(newnode), true };
}
void RotateR(Node* parent) {
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR) subLR->_parent = parent;
Node* parentParent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (parent == _root) {
_root = subL;
subL->_parent = nullptr;
} else {
if (parentParent->_left == parent) {
parentParent->_left = subL;
} else {
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}
void RotateL(Node* parent) {
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL) subRL->_parent = parent;
Node* parentParent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (parentParent == nullptr) {
_root = subR;
subR->_parent = nullptr;
} else {
if (parent == parentParent->_left) {
parentParent->_left = subR;
} else {
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
Iterator Find(const K& key) {
KeyOfT kot;
Node* cur = _root;
while (cur) {
if (kot(cur->_data) < key) {
cur = cur->_right;
} else if (kot(cur->_data) > key) {
cur = cur->_left;
} else {
return Iterator(cur);
}
}
return End();
}
int Height() { return _Height(_root); }
int Size() { return _Size(_root); }
private:
int _Size(Node* root) {
if (root == nullptr) return 0;
return _Size(root->_left) + _Size(root->_right) + 1;
}
int _Height(Node* root) {
if (root == nullptr) return 0;
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
void Destroy(Node* root) {
if (root == nullptr) return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
private:
Node* _root = nullptr;
};
#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, bool> insert(const pair<K, V>& kv) { return _t.Insert(kv); }
iterator find(const K& key) { return _t.Find(key); }
V& operator[](const K& key) {
auto [it, flag] = _t.Insert({ key, V() });
return it->second;
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
}
#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(const K& key) { return _t.Insert(key); }
iterator find(const K& key) { return _t.Find(key); }
private:
RBTree<K, const K, SetKeyOfT> _t;
};
}
#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;
func(s);
}
void Test_map() {
jqj::map<string, string> dict;
dict.insert({ "sort", "排序" });
dict.insert({ "left", "左边" });
dict.insert({ "right", "右边" });
dict["string"] = "字符串";
dict["left"] = "左边 xxx";
auto it = dict.begin();
while (it != dict.end()) {
it->second += 'x';
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
for (auto& [k, v] : dict) {
cout << k << ":" << v << endl;
}
cout << endl;
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
jqj::map<string, int> countMap;
for (auto& e : arr) {
countMap[e]++;
}
for (auto& [k, v] : countMap) {
cout << k << ":" << v << endl;
}
cout << endl;
}
int main() {
Test_set();
Test_map();
return 0;
}
（程序输出展示了有序遍历的 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