STL 中 Set 和 Map 容器的底层实现原理，基于红黑树数据结构进行泛型封装。通过模板参数设计区分 Key 与 Value 存储类型，利用仿函数 KeyOfT 统一提取键值逻辑，解决了单一红黑树适配两种场景的问题。核心内容包括红黑树节点结构、旋转平衡算法、迭代器中序遍历实现以及 key 不可修改约束。代码展示了从基础组件到完整 mySet 和 myMap 的实现过程，并包含测试验证，帮助理解 C++ 标准库容器的泛型设计与内存管理思想。
STL 的 map 和 set 是高频使用的关联式容器，其底层都依赖红黑树实现。本文结合源码框架与实现细节，从红黑树的泛型改造入手，一步步拆解 myMap 和 mySet 的封装逻辑，包括关键的仿函数设计、迭代器实现、key 不可修改约束及 map 的 [] 运算符重载，全程附可运行代码。
SGI-STL30 版本源代码中，map 和 set 的实现框架核心部分如下：
// stl_set.h
template<class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
public:
typedef Key key_type;
typedef Key value_type;
private:
typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type;
rep_type t; // red-black tree representing set
};
// stl_map.h
template<class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
public:
typedef Key key_type;
typedef T mapped_type;
typedef pair<const Key, T> value_type;
private:
typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type;
rep_type t; // red-black tree representing map
};
// stl_tree.h
struct __rb_tree_node_base {
typedef __rb_tree_color_type color_type;
typedef __rb_tree_node_base* base_ptr;
color_type color;
base_ptr parent;
base_ptr left;
base_ptr right;
};
template<class Value>
struct __rb_tree_node : public __rb_tree_node_base {
typedef __rb_tree_node<Value>* link_type;
Value value_field;
};
通过框架分析可以看到，rb_tree 用了一个巧妙的泛型思想实现。rb_tree 实现 key 的搜索场景还是 key/value 的搜索场景不是直接写死的，而是由第二个模板参数 Value 决定 _rb_tree_node 中存储的数据类型。
rb_tree 时第二个模板参数给的是 Key。rb_tree 时第二个模板参数给的是 pair<const Key, T>。
这样一颗红黑树既可以实现 key 搜索场景，也可以实现 key/value 搜索场景的 map。rb_tree 第二个模板参数 Value 已经控制了红黑树结点中的存储的数据类型，为什么还要传第一个模板参数 Key？对于 map 和 set，find/erase 时的函数参数都是 Key，所以第一个模板参数是传给 find/erase 等函数做形参的类型的。对于 set 而言两个参数是一样的，但是对于 map 而言就完全不一样了，map insert 的是 pair 对象，但是 find 和 erase 的 Key 对象。
STL 中 map 和 set 复用同一颗红黑树的核心是泛型编程 + 仿函数提取 key，解决了'一颗树适配两种数据场景'的问题。
红黑树需要支持存储两种数据类型：
因此红黑树的模板参数需抽象为 3 个：
template<class K, class T, class KeyOfT>
class RBTree {
// K：find/erase 时的 key 类型（统一接口参数）
// T：红黑树节点存储的实际数据类型（set 为 K，map 为 pair<const K, V>）
// KeyOfT：仿函数，从 T 中提取 K（解决 T 类型不统一的比较问题）
};
由于 T 的类型不固定（K 或 pair），红黑树插入 / 查找时无法直接获取 key，需通过仿函数 KeyOfT 统一提取，由 map 和 set 分别实现适配：
节点存储模板类型 T，包含左右子指针、父指针和颜色标记：
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;
enum Colour { Red, Black };
template<class T>
struct RBTreeNode {
T _data;
RBTreeNode<T>* _parent;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
Colour _col;
RBTreeNode(const T& data) : _parent(nullptr), _left(nullptr), _right(nullptr), _data(data), _col(Red) {}
};
#pragma once
#include "RBTree.h"
namespace MySTL {
template<class K>
class set {
struct SetKeyofT {
const K& operator()(const K& key) { return key; }
};
private:
RBTree<K, const K, SetKeyofT> _t;
};
}
#pragma once
#include "RBTree.h"
namespace MySTL {
template<class K, class V>
class map {
struct MapKeyofT {
const K& operator()(const pair<K, V>& kv) { return kv.first; }
};
private:
RBTree<K, pair<const K, V>, MapKeyofT> _t;
};
}
重点实现 Insert（返回 pair<Iterator, bool>，支持 map 的 []）和 Find，平衡维护逻辑与基础红黑树一致：
#pragma once
#include <iostream>
#include <assert.h>
using namespace std;
enum Colour { Red, Black };
template<class T>
struct RBTreeNode {
T _data;
RBTreeNode<T>* _parent;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
Colour _col;
RBTreeNode(const T& data) : _parent(nullptr), _left(nullptr), _right(nullptr), _data(data), _col(Red) {}
};
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) {}
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;
}
Ref operator*() { return _node->_data; }
Ptr operator->() { &(_node->_data); }
!=( Self& s) { _node != s._node; }
};
< , , >
{
RBTreeNode<T> Node;
:
RBTreeIterator<T, T&, T*> Iterator;
RBTreeIterator<T, T&, T*> ConstIterator;
~() { (_root); _root = ; }
{
(root == ) ;
(root->_left);
(root->_right);
root;
}
{
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* grandparent = parent->_parent;
(grandparent->_left == parent) {
Node* uncle = grandparent->_right;
(uncle && uncle->_col == Red) {
parent->_col = Black;
uncle->_col = Black;
grandparent->_col = Red;
cur = grandparent;
parent = cur->_parent;
} {
(cur == parent->_left) {
(grandparent);
parent->_col = Black;
grandparent->_col = Red;
} {
(parent);
(grandparent);
cur->_col = Black;
grandparent->_col = Red;
}
;
}
} {
Node* uncle = grandparent->_left;
(uncle && uncle->_col == Red) {
uncle->_col = Black;
parent->_col = Black;
grandparent->_col = Red;
cur = grandparent;
parent = cur->_parent;
} {
(parent->_right == cur) {
(grandparent);
parent->_col = Black;
grandparent->_col = Red;
} {
(parent);
(grandparent);
cur->_col = Black;
grandparent->_col = Red;
}
;
}
}
}
_root->_col = Black;
{ (newnode), };
}
{
KeyofT kot;
Node* cur = _root;
(cur) {
((cur->_data) < key) {
cur = cur->_right;
} ((cur->_data) > key) {
cur = cur->_left;
} {
(cur);
}
}
();
}
:
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
(subLR) subLR->_parent = parent;
Node* grandparent = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
(parent == _root) {
_root = subL;
subL->_parent = ;
} {
(grandparent->_left == parent) grandparent->_left = subL;
grandparent->_right = subL;
subL->_parent = grandparent;
}
}
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
(subRL) subRL->_parent = parent;
Node* grandparent = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
(_root == parent) {
_root = subR;
subR->_parent = ;
} {
(grandparent->_left == parent) grandparent->_left = subR;
grandparent->_right = subR;
subR->_parent = grandparent;
}
}
:
Node* _root = ;
};
#pragma once
#include "RBTree.h"
namespace MySTL {
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(); }
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> ;
};
}
#pragma once
#include "RBTree.h"
namespace MySTL {
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(); }
pair<iterator, bool> insert(const pair<K, V>& kv) { return _t.Insert(kv); }
iterator find(const K& key) { return _t.Find(key); }
V& []( K& key) {
[it, flag] = .({ key, () });
it->second;
}
:
RBTree<K, pair< K, V>, MapKeyofT> ;
};
}
#define _CRT_SECURE_NO_WARNINGS 1
#include "RBTree.h"
#include "Map.h"
#include "Set.h"
void test_set() {
MySTL::set<int> s;
s.insert(1); s.insert(2); s.insert(5); s.insert(0); s.insert(10);
MySTL::set<int>::iterator it = s.begin();
while (it != s.end()) {
cout << *it << " ";
++it;
}
cout << endl;
}
void test_map() {
MySTL::map<string, string> dict;
dict.insert({"sort", "排序"});
dict["string"] = "字符串";
auto it = dict.begin();
while (it != dict.end()) {
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
}
int main() {
cout << "测试 set:" << endl;
test_set();
cout << "------------------" << endl;
cout << "测试 map:" << endl;
();
;
}
myMap 和 mySet 的封装核心是红黑树的泛型复用：通过模板参数 T 适配不同数据类型，用仿函数 KeyOfT 统一 key 提取逻辑，再通过迭代器封装实现双向遍历。其中，key 不可修改的约束、map 的 [] 运算符重载、迭代器的 ++/-- 实现，都是 STL 容器设计的经典细节。掌握这套封装逻辑，不仅能理解 STL 容器的底层实现，更能学会'泛型编程 + 接口抽象'的设计思想。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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