从零带你封装 C++ STL 的 map 和 set ——红黑树底层实现全解析
目录
写在前面
🎯 这篇文章能帮你：
第一章：红黑树究竟是啥？
1.1 红黑树定义（通俗易懂版）
1.2 节点结构大揭秘
1.3 左旋：节点的"换位大法"
第二章：map的内部乾坤
2.1 map是个啥？
2.2 map的模板实现
第三章：性能大比拼
时间复杂度
空间复杂度
💡 干货小贴士
第四章：迭代器的前世今生
4.1 迭代器是什么？
4.2 迭代器的基本分类
4.3 迭代器的实现原理
第五章：map的深度剖析
5.1 map的基本概念
5.2 map的典型使用场景
5.3 map的内部实现
第六章：set的实现原理
6.1 set的基本特征
6.2 set的典型使用场景
第七章：实际应用场景
7.1 词频统计
7.2 缓存实现
结语
推荐阅读
写在前面
嘿，程序员们！👋 今天我们要揭秘C++中最牛的数据结构之一——红黑树！相信很多小伙伴对map和set的内部实现一直很好奇，今天我们就一起"解剖"它们！💪
🎯 这篇文章能帮你：
-
彻底搞懂红黑树的神秘面纱
-
了解map和set的内部乾坤
-
手写一个迷你版STL容器（装逼利器！）
第一章：红黑树究竟是啥？
1.1 红黑树定义（通俗易懂版）
想象红黑树就像是一个有严格纪律的家族：
-
族长（根节点）必须是黑色的
-
所有的"旁系"（叶子节点）都是黑色
-
红色成员不能生红色后代
-
每个分支的黑色成员数量必须一致
1.2 节点结构大揭秘
// 颜色枚举，红黑树的"身份证" enum Color { RED, // 红色成员 BLACK // 黑色成员 }; // 节点：红黑树的基本单元 template struct RBTreeNode { T data; // 数据 Color color; // 颜色标记 RBTreeNode* parent; // 父节点指针 RBTreeNode* left; // 左孩子 RBTreeNode* right; // 右孩子 // 新成员默认是红色的 RBTreeNode(const T& value) : data(value), color(RED), parent(nullptr), left(nullptr), right(nullptr) {} };1.3 左旋：节点的"换位大法"
// 左旋：想象成一个节点向左侧"倒下" void rotateLeft(RBTreeNode* x) { RBTreeNode* y = x->right; // 找到要"顶替"的节点 x->right = y->left; // 调整关系 // 一系列复杂的指针重连接... if (y->left != nullptr) y->left->parent = x; // 更新根节点或父节点的子节点 if (x->parent == nullptr) root = y; else if (x == x->parent->left) x->parent->left = y; else x->parent->right = y; y->left = x; x->parent = y; }第二章：map的内部乾坤
2.1 map是个啥？
map就像是一个高级的"翻译官"：
-
存储键值对
-
自动排序
-
键值唯一
-
底层是红黑树
2.2 map的模板实现
template class MyMap { private: RBTree tree; public: // 插入操作 void insert(const std::pair& kvPair) { tree.insertUnique(kvPair); } // 牛逼的下标访问 Value& operator[](const Key& key) { // 如果没有就自动创建 return tree.findOrInsert(key); } };第三章：性能大比拼
时间复杂度
-
尽量使用emplace替代insert
-
对于小型数据，考虑使用unordered_map/unordered_set
-
避免频繁拷贝大型对象
容器 插入 查找 删除 map O(log n) O(log n) O(log n) set O(log n) O(log n) O(log n) 操作 平均时间复杂度 插入 O(log n) 查找 O(log n) 删除 O(log n) 空间复杂度
-
每个节点存储额外颜色信息
-
总体空间复杂度：O(n)
💡 干货小贴士
-
红黑树是平衡二叉树的王者
-
map和set的高效源于红黑树
-
深入源码，提升代码功力
在C++的世界里，map和set绝对是最常用且最强大的容器之一。它们不仅仅是简单的数据结构，更是算法和数据管理的利器。本文将带你全方位解析这两个容器的方方面面。
第四章：迭代器的前世今生
4.1 迭代器是什么？
迭代器可以理解为容器和算法之间的桥梁。它就像一个"智能指针"，能够遍历容器中的元素，同时屏蔽不同容器的内部细节。
4.2 迭代器的基本分类
C++中迭代器主要分为五类：
-
输入迭代器
-
输出迭代器
-
前向迭代器
-
双向迭代器
-
随机访问迭代器
4.3 迭代器的实现原理
template class MyIterator { private: T* ptr; // 底层指针 public: // 构造函数 MyIterator(T* p) : ptr(p) {} // 解引用操作符 T& operator*() { return *ptr; } // 前置++操作符 MyIterator& operator++() { ++ptr; return *this; } // 比较操作符 bool operator!=(const MyIterator& other) { return ptr != other.ptr; } };第五章：map的深度剖析
5.1 map的基本概念
map是一个关联容器，它存储键值对(key-value)，并且：
-
根据键自动排序
-
键的唯一性
-
底层基于红黑树实现
5.2 map的典型使用场景
// 词频统计 std::map wordCount; // 添加元素 wordCount["hello"] = 10; wordCount["world"] = 20; // 遍历 for (const auto& pair : wordCount) { std::cout
-
-
-
-
