【红黑树进阶】手撕STL源码：从零封装RB-tree实现map和set

👇点击进入作者专栏：

《算法画解》 ✅

《linux系统编程》✅

《C++》 ✅

文章目录

• 一. 源码及框架分析
• • 1.1 STL源码中的设计思想
  • 1.2 STL源码框架分析
• 二. 模拟实现map和set（实现复用红黑树的框架）
• • 2.1 红黑树节点的定义
  • 2.2 红黑树的基本框架
  • 2.3 解决Key的比较问题：KeyOfT仿函数
  • 2.4 支持insert插入
  • 2.5 map和set的insert封装
• 三. 迭代器的实现
• • 3.1 迭代器结构设计
  • 3.2 迭代器的++操作
  • 3.3 迭代器的–操作
  • 3.4 RBTree中的迭代器接口
• 四. map和set对迭代器的封装
• • 4.1 set的迭代器封装
  • 4.2 map的迭代器封装
  • 4.3 测试迭代器
  • 五. map的operator[]实现
  • 5.1 operator[]的原理
  • • 5.2 实现步骤
  • 5.3 代码实现
  • 5.4 测试operator[]
• 六. const迭代器和const正确性
• • 6.1 const迭代器的使用场景
  • 6.2 为什么要支持const迭代器？
  • 6.3 set中key不可修改的保证
  • 6.4 map中key不可修改，value可修改
• 七. 完整代码实现
• • 7.1 RBTree.h（完整版）
  • 7.2 Myset.h（完整版）
  • • 7.3 Mymap.h（完整版）
• 八. 总结与思考
• • 8.1 设计亮点
  • 8.2 与STL源码的对比
  • 8.3 常见问题

一. 源码及框架分析

1.1 STL源码中的设计思想

在SGI-STL30版本中，map和set的实现基于一棵红黑树（rb_tree）。这种设计体现了C++泛型编程的强大之处：通过同一棵红黑树，既可以实现key-only的set，也可以实现key/value的map。

核心设计思想：

• rb_tree的节点中存储什么类型，由模板参数决定
• set传给rb_tree的是Key类型
• map传给rb_tree的是pair<const Key, T>类型

1.2 STL源码框架分析

// stl_set.h
template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
public:
typedef Key key_type;
typedef Key value_type; // set的value_type就是Key
private:
typedef rb_tree<key_type, value_type,
identity<value_type>, key_compare, Alloc> rep_type;
rep_type t; // 红黑树，存储的是Key类型
};

// 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; // map的value_type是pair
private:
typedef rb_tree<key_type, value_type,
select1st<value_type>, key_compare, Alloc> rep_type;
rep_type t; // 红黑树，存储的是pair<const Key, T>类型
};

// 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; // 节点存储的数据，Value类型由使用者决定
};

关键问题：为什么rb_tree需要两个模板参数Key和Value？

• Value：决定了节点中存储的数据类型（set是Key，map是pair）
• Key：用于查找和删除操作的参数类型（find/erase的参数类型）

对于set而言，Key和Value是相同的；对于map而言，Key是键的类型，Value是pair类型。这种设计使得一棵红黑树既能处理set场景，也能处理map场景。

二. 模拟实现map和set（实现复用红黑树的框架）

2.1 红黑树节点的定义

// RBTree.h
#pragma once

enum Colour
{
RED,
BLACK
};

template<class T>
struct RBTreeNode
{
T _data; // 节点存储的数据（泛型T）
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) // 新节点默认红色
{}
};

2.2 红黑树的基本框架

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;

// 构造函数
RBTree() = default;

// 析构函数
~RBTree()
{
Destroy(_root);
_root = nullptr;
}

// 插入接口
pair<Iterator, bool> Insert(const T& data);

// 查找接口
Iterator Find(const K& key);

// 迭代器相关
Iterator Begin();
Iterator End();
ConstIterator Begin() const;
ConstIterator End() const;

private:
// 旋转操作
void RotateL(Node* parent); // 左单旋
void RotateR(Node* parent); // 右单旋

// 销毁树
void Destroy(Node* root);

Node* _root = nullptr; // 根节点
};

2.3 解决Key的比较问题：KeyOfT仿函数

问题：红黑树在插入时需要比较键的大小，但T可能是Key类型，也可能是pair类型。pair的比较规则是first和second一起比较，不符合我们的需求（我们只想比较key）。

解决方案：使用仿函数KeyOfT，从T对象中取出Key进行比较。

// Mymap.h – map中定义的KeyOfT仿函数
namespace bit
{
template<class K, class V>
class map
{
// 仿函数：从pair中取出key
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first; // 返回pair的first（键）
}
};

// … 其他代码
};
}

// Myset.h – set中定义的KeyOfT仿函数
namespace bit
{
template<class K>
class set
{
// 仿函数：直接返回key本身
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key; // 直接返回key
}
};

// … 其他代码
};
}

2.4 支持insert插入

RBTree中的Insert实现（关键部分是使用KeyOfT进行比较）

template<class K, class T, class KeyOfT>
pair<typename RBTree<K, T, KeyOfT>::Iterator, bool>
RBTree<K, T, KeyOfT>::Insert(const T& data)
{
// 1. 空树情况
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK; // 根节点必须是黑色
return make_pair(Iterator(_root, _root), true);
}

// 2. 查找插入位置
KeyOfT kot; // 创建仿函数对象
Node* parent = nullptr;
Node* cur = _root;

while (cur)
{
// 使用kot取出key进行比较
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);
}
}

// 3. 创建新节点并链接
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;

// 4. 红黑树性质修复（与之前实现的插入逻辑相同）
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是grandfather的右孩子
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);
}

2.5 map和set的insert封装

// Mymap.h – map的insert
namespace bit
{
template<class K, class V>
class map
{
// … 前面的代码

public:
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv); // 直接调用RBTree的Insert
}

private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
}

// Myset.h – set的insert
namespace bit
{
template<class K>
class set
{
// … 前面的代码

public:
pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key); // 直接调用RBTree的Insert
}

private:
RBTree<K, const K, SetKeyOfT> _t;
};
}

三. 迭代器的实现

3.1 迭代器结构设计

迭代器需要支持：

• operator++：前往中序下一个节点
• operator–：前往中序上一个节点
• operator*：解引用，获取节点数据
• operator->：通过指针访问成员
• operator==/!=：比较两个迭代器是否相等

// RBTree.h
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ref, Ptr> Self;

Node* _node; // 当前迭代器指向的节点
Node* _root; // 根节点（用于–end()特殊处理）

// 构造函数
RBTreeIterator(Node* node, Node* root)
: _node(node)
, _root(root)
{}

// 前置++
Self& operator++();

// 前置–
Self& operator—();

// 解引用
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.2 迭代器的++操作

中序遍历的顺序是：左子树 → 根 → 右子树

template<class T, class Ref, class Ptr>
typename RBTreeIterator<T, Ref, Ptr>::Self&
RBTreeIterator<T, Ref, Ptr>::operator++()
{
if (_node == nullptr)
return *this; // end()不能++

if (_node->_right)
{
// 情况1：右子树不为空
// 中序下一个是右子树的最左节点
Node* leftMost = _node->_right;
while (leftMost->_left)
{
leftMost = leftMost->_left;
}
_node = leftMost;
}
else
{
// 情况2：右子树为空
// 向上找：孩子是父亲左的那个祖先
Node* cur = _node;
Node* parent = cur->_parent;

while (parent && cur == parent->_right)
{
cur = parent;
parent = cur->_parent;
}
_node = parent; // 可能是nullptr（到达end）
}

return *this;
}

3.3 迭代器的–操作

template<class T, class Ref, class Ptr>
typename RBTreeIterator<T, Ref, Ptr>::Self&
RBTreeIterator<T, Ref, Ptr>::operator—()
{
if (_node == nullptr) // –end()特殊处理
{
// end()应该走到中序最后一个节点（整棵树的最右节点）
Node* rightMost = _root;
while (rightMost && rightMost->_right)
{
rightMost = rightMost->_right;
}
_node = rightMost;
}
else if (_node->_left)
{
// 情况1：左子树不为空
// 中序上一个节点是左子树的最右节点
Node* rightMost = _node->_left;
while (rightMost->_right)
{
rightMost = rightMost->_right;
}
_node = rightMost;
}
else
{
// 情况2：左子树为空
// 向上找：孩子是父亲右的那个祖先
Node* cur = _node;
Node* parent = cur->_parent;

while (parent && cur == parent->_left)
{
cur = parent;
parent = cur->_parent;
}
_node = parent; // 可能是nullptr（到达rend？）
}

return *this;
}

–end()的特殊处理：

• end()迭代器指向nullptr
• 当对end()执行–操作时，应该得到最后一个有效节点（最右节点）
• 所以需要记录_root来找到最右节点

3.4 RBTree中的迭代器接口

template<class K, class T, class KeyOfT>
class RBTree
{
// … 前面的代码

public:
typedef RBTreeIterator<T, T&, T*> Iterator;
typedef RBTreeIterator<T, const T&, const T*> ConstIterator;

// begin() -> 最左节点
Iterator Begin()
{
Node* leftMost = _root;
while (leftMost && leftMost->_left)
{
leftMost = leftMost->_left;
}
return Iterator(leftMost, _root);
}

// end() -> nullptr
Iterator End()
{
return Iterator(nullptr, _root);
}

// const版本
ConstIterator Begin() const
{
Node* leftMost = _root;
while (leftMost && leftMost->_left)
{
leftMost = leftMost->_left;
}
return ConstIterator(leftMost, _root);
}

ConstIterator End() const
{
return ConstIterator(nullptr, _root);
}
};

四. map和set对迭代器的封装

4.1 set的迭代器封装

// Myset.h
namespace bit
{
template<class K>
class set
{
// … 前面的代码

public:
// 类型重命名：从RBTree中取出迭代器类型
typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;

// begin/end接口
iterator begin()
{
return _t.Begin();
}

iterator end()
{
return _t.End();
}

const_iterator begin() const
{
return _t.Begin();
}

const_iterator end() const
{
return _t.End();
}

private:
RBTree<K, const K, SetKeyOfT> _t;
};
}

4.2 map的迭代器封装

// Mymap.h
namespace bit
{
template<class K, class V>
class map
{
// … 前面的代码

public:
// 类型重命名
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;

// begin/end接口
iterator begin()
{
return _t.Begin();
}

iterator end()
{
return _t.End();
}

const_iterator begin() const
{
return _t.Begin();
}

const_iterator end() const
{
return _t.End();
}

private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
}

4.3 测试迭代器

// 测试set
void test_set()
{
bit::set<int> s;
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };

for (auto e : a)
{
s.insert(e);
}

// 范围for测试（依赖begin/end）
for (auto e : s)
{
cout << e << " "; // 输出：1 2 3 4 5 6 7 14 15 16
}
cout << endl;
}

五. map的operator[]实现

5.1 operator[]的原理

map的operator[]是一个非常方便的特性：

• 如果key存在，返回对应的value引用
• 如果key不存在，插入一个默认value并返回其引用

5.2 实现步骤

5.3 代码实现

// Mymap.h
namespace bit
{
template<class K, class V>
class map
{
// … 前面的代码

public:
V& operator[](const K& key)
{
// 尝试插入：如果key不存在，插入{key, V()}
// V()会调用V类型的默认构造函数（内置类型为0）
pair<iterator, bool> ret = insert(make_pair(key, V()));

// ret.first是插入位置（新节点或已存在节点）的迭代器
// 返回该节点的second（value）的引用
return ret.first->second;
}
};
}

5.4 测试operator[]

void test_map()
{
bit::map<string, string> dict;

// 插入操作
dict.insert({ "sort", "排序" });
dict.insert({ "left", "左边" });
dict.insert({ "right", "右边" });

// operator[]的三种用法
dict["left"] = "左边，剩余"; // 修改已存在key的value
dict["insert"] = "插入"; // 插入新key-value
dict["string"]; // 插入新key，value为默认值（空字符串）

// 遍历输出
for (auto& kv : dict)
{
// 不能修改first，可以修改second
// kv.first += 'x'; // 错误！
kv.second += 'x'; // 正确：value可以修改

cout << kv.first << ":" << kv.second << endl;
}
}

输出结果：

insert:插入x
left:左边，剩余x
right:右边x
sort:排序x
string:x

六. const迭代器和const正确性

6.1 const迭代器的使用场景

// 接收const引用的函数
void Print(const bit::set<int>& s)
{
// 这里只能用const_iterator，因为s是const的
bit::set<int>::const_iterator it = s.begin();
while (it != s.end())
{
// *it += 10; // 错误！const迭代器不允许修改
cout << *it << " ";
++it;
}
cout << endl;
}

6.2 为什么要支持const迭代器？

• const对象只能用const迭代器：保证const对象的内容不会被修改
• 语义清晰：表明这段代码只读不写
• 编译器检查：帮助捕获意外的修改

6.3 set中key不可修改的保证

在set中，key是不可修改的。实现方式：

// Myset.h
template<class K>
class set
{
private:
// RBTree第二个模板参数传入 const K
RBTree<K, const K, SetKeyOfT> _t;
};

这样，迭代器解引用得到的是const K&，无法修改。

6.4 map中key不可修改，value可修改

// Mymap.h
template<class K, class V>
class map
{
private:
// RBTree第二个模板参数传入 pair<const K, V>
// key是const的，value是可修改的
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

• 迭代器解引用得到pair<const K, V>&
• first是const，不能修改
• second不是const，可以修改

七. 完整代码实现

7.1 RBTree.h（完整版）

#pragma once

#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)
{}
};

// 迭代器
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 == nullptr)
return *this;

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;
}
};

// 红黑树
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;

RBTree() = default;

~RBTree()
{
Destroy(_root);
_root = nullptr;
}

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;

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);
}
}

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 (parent == grandfather->_left)
{
Node* uncle = grandfather->_right;

if (uncle && uncle->_col == RED)
{
// 情况1：变色
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 make_pair(Iterator(newnode, _root), true);
}

// 查找
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, _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* 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;
}
}

// 右单旋
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 (parentParent == nullptr)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
parentParent->_left = subL;
else
parentParent->_right = subL;

subL->_parent = parentParent;
}
}

// 销毁树
void Destroy(Node* root)
{
if (root == nullptr)
return;

Destroy(root->_left);
Destroy(root->_right);
delete root;
}

Node* _root = nullptr;
};

7.2 Myset.h（完整版）

#pragma once

#include "RBTree.h"

namespace bit
{
template<class K>
class set
{
// 仿函数：从数据中取出key
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};

public:
// 迭代器类型（从RBTree中取出）
typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;
typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator const_iterator;

// begin/end
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;
};

// 测试函数
void Print(const set<int>& s)
{
set<int>::const_iterator it = s.begin();
while (it != s.end())
{
// *it += 2; // 错误！不能修改
cout << *it << " ";
++it;
}
cout << endl;
}

void test_set()
{
set<int> s;
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };

for (auto e : a)
{
s.insert(e);
}

// 范围for
for (auto e : s)
{
cout << e << " ";
}
cout << endl;

Print(s);
}
}

7.3 Mymap.h（完整版）

#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;

// begin/end
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);
}

// operator[]
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}

private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

void test_map()
{
map<string, string> dict;

dict.insert({ "sort", "排序" });
dict.insert({ "left", "左边" });
dict.insert({ "right", "右边" });

dict["left"] = "左边，剩余";
dict["insert"] = "插入";
dict["string"];

map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
// it->first += 'x'; // 错误！不能修改key
it->second += 'x'; // 可以修改value

cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
}
}

八. 总结与思考

8.1 设计亮点

8.2 与STL源码的对比

8.3 常见问题

Q1：为什么set的迭代器不能修改key？

• set中的元素本身就是key，修改key会破坏BST的有序性
• 实现中通过RBTree<K, const K, SetKeyOfT>保证存储的是const K

Q2：为什么map的迭代器能修改value但不能修改key？

• map存储的是pair<const K, V>，key是const的，value不是const
• 修改key会破坏有序性，修改value不会影响树的组织结构

Q3：为什么要实现const_iterator？

• const对象只能用const_iterator遍历
• 明确表达只读语义，帮助编译器检查

Q4：迭代器–操作中为什么要保存_root？

• 为了处理–end()的情况，需要找到最右节点
• 没有_root无法从nullptr找到最右节点

加油！志同道合的人会看到同一片风景。 看到这里请点个赞，关注，如果觉得有用就收藏一下吧。后续还会持续更新的。 创作不易，还请多多支持！