C++学习：map/set源码剖析+利用红黑树封装map/set
·
前面我们已经学习了红黑树这个高级数据结构的实现。我们知道STL的map/set的底层数据结构为红黑树，本期就查看STL源码的map/set，并结合着这之前的红黑树的实现，模拟实现map和set的一部分功能
STL源码：楼田莉子/CPP代码学习
作者的个人gitee：楼田莉子/CPP代码学习喜欢请支持一下，谢谢
目录
复用之前红黑树的代码实现my_set/my_map，并实现Insert功能
STL——map/set源码剖析
源码核心部分：
//set.h
#ifndef __SGI_STL_SET_H
#define __SGI_STL_SET_H
#include <tree.h>
#include <stl_set.h>
#ifdef __STL_USE_NAMESPACES
using __STD::set;
#endif /* __STL_USE_NAMESPACES */
#endif /* __SGI_STL_SET_H */
//map.h
#ifndef __SGI_STL_MAP_H
#define __SGI_STL_MAP_H
#include <tree.h>
#include <stl_map.h>
#ifdef __STL_USE_NAMESPACES
using __STD::map;
#endif /* __STL_USE_NAMESPACES */
#endif /* __SGI_STL_MAP_H */
//stl_set.h
template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
public:
// typedefs:
typedef Key key_type;
typedef Key value_type;
typedef Compare key_compare;
typedef Compare value_compare;
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:
// typedefs:
typedef Key key_type;
typedef T data_type;
typedef T mapped_type;
typedef pair<const Key, T> value_type;
typedef Compare key_compare;
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;
static base_ptr minimum(base_ptr x)
{
while (x->left != 0) x = x->left;
return x;
}
static base_ptr maximum(base_ptr x)
{
while (x->right != 0) x = x->right;
return x;
}
};
template <class Value>
struct __rb_tree_node : public __rb_tree_node_base
{
typedef __rb_tree_node<Value>* link_type;
Value value_field;
};
template <class Key, class Value, class KeyOfValue, class Compare,
class Alloc = alloc>
class rb_tree {
protected:
typedef void* void_pointer;
typedef __rb_tree_node_base* base_ptr;
typedef __rb_tree_node<Value> rb_tree_node;
typedef simple_alloc<rb_tree_node, Alloc> rb_tree_node_allocator;
typedef __rb_tree_color_type color_type;
protected:
size_type node_count; // keeps track of size of tree
link_type header;
};解析
它们之间的关系为：
我们发现了红红黑树并不是像我们那样直接写死的，而是通过通过泛型决定红黑树存储什么
通过下面两张图，我们发现set实例化rb_tree时第⼆个模板参数给的是key，map实例化rb_tree时第⼆个模板参数给的是pair<const key, T>，这样⼀颗红⿊树既可以实现key搜索场景的set，也可以实现key/value搜索场景的map。
stl_set.h
stl-map.h 
注意：源码⾥⾯模板参数是⽤T代表value，⽽内部写的value_type不是我们我们⽇常
key/value场景中说的value，源码中的value_type反⽽是红⿊树结点中存储的真实的数据的类型。
rb_tree第⼆个模板参数Value已经控制了红⿊树结点中存储的数据类型，为什么还要传第⼀个模板参数Key呢？
对于map和set，find/erase时的函数参数都是Key，所以第⼀个模板参数是传给find/erase等函数做形参的类型的。对于set⽽⾔两个参数是⼀样的，但是对于map⽽⾔就完全不⼀样了，map insert的是pair对象，但是find和ease的是Key对象。
模拟实现set/map
复用之前红黑树的代码实现my_set/my_map，并实现Insert功能
仿照源码的形式，我们来模仿一下
我们这⾥相⽐源码调整⼀下，key参数就⽤K，value参数就⽤V，红⿊树中的数据类型，我们使⽤T。
因为RBTree实现了泛型不知道T参数导致是K，还是pair<K, V>，那么insert内部进⾏插⼊逻辑
⽐较时，就没办法进⾏⽐较（因为pair的默认⽀持的是key和value⼀起参与⽐较，我们需要时的任
何时候只⽐较key）
//作者自己为了可读性对格式稍做修改
// 源码中pair⽀持的<重载实现
template <class T1, class T2>
bool operator< (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
{
return lhs.first<rhs.first ||
(!(rhs.first<lhs.first) &&lhs.second<rhs.second);
}因此我们在map和set层分别实现⼀个MapKeyOfT和SetKeyOfT的仿函数传给RBTree的KeyOfT，然后RBTree中通过KeyOfT仿函数取出T类型对象中的key，再进⾏⽐较
源代码：
//my_set.h
#pragma once
#include"RBTree - 副本.h"
namespace The_Song_of_the_end_of_the_world
{
template<class K>
class Set
{
//取出set中所有的key值的仿函数
//照顾map而设计的泛型
struct SetKeyOf
{
const K& operator()(const K& k)
{
return k;
}
};
public:
bool Insert(const K& k)
{
return _t.Insert(k);
}
private:
RBTree<K,K,SetKeyOf> _t;
};
}
//my_map.h
#pragma once
#include"RBTree - 副本.h"
namespace The_Song_of_the_end_of_the_world
{
template<class K,class V>
class Map
{
//取出set中所有的key值的仿函数
//照顾map而设计的泛型
struct MapKeyOf
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
bool Insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
private:
RBTree<K, pair<K, V>,MapKeyOf> _t;
};
}
//RBTree - 副本.h
#pragma once
#include<iostream>
using namespace std;
// 枚举值表示颜色
enum Colour
{
RED,
BLACK
};
// 节点结构
//set
template<class T>
struct RBTreeNode
{
// 这里更新控制平衡也需要parent指针
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)
{
}
};
template<class K, class T,class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
//红黑树插入
//旋转代码的实现跟AVL树是一样的，只是不需要更新平衡因子
bool Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return 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 false;
}
}
cur = new Node(data);
// 新增节点。颜色红色给红色
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;
// g
// p u
if (parent == grandfather->_left)
{
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)
{
// g
// p u
//c
//单旋
RotateR(grandfather);
//变色
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p u
// c
//双旋
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
// g
// u p
Node * uncle = grandfather->_left;
// 叔叔存在且为红色-》变色
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else // 情况⼆：叔叔不存在或者存在为黑
{
// 情况⼆：叔叔不存在或者存在为黑
// 旋转+变色
// g
// u p
// c
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return true;
}
//红黑树的查找
Node* Find(const K& key)
{
Node* cur = _root;
while(cur)
{
if (kot(cur->_data) < key)
{
cur = cur->_right;
}
else if (cur->_kv.first > key)
{
cur = cur->_left;
}
else
{
return cur;
}
}
return nullptr;
}
private:
//右单旋
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 (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
Node* _root = nullptr;
};
使用案例：
#include <iostream>
using namespace std;
// 示例1：平台特定代码
#ifdef _WIN32
#define PLATFORM "Windows"
#elif __linux__
#define PLATFORM "Linux"
#elif __APPLE__
#define PLATFORM "macOS"
#else
#define PLATFORM "Unknown"
#endif
// 示例2：调试模式
#define DEBUG_MODE 1
// 示例3：功能开关
#define FEATURE_A_ENABLED
#define FEATURE_B_LEVEL 3
int main() {
// 平台检测
cout << "Running on: " << PLATFORM << endl;
// 调试代码
#if DEBUG_MODE
cout << "Debug information: Program started" << endl;
#endif
// 功能开关
#ifdef FEATURE_A_ENABLED
cout << "Feature A is enabled" << endl;
#endif
// 带值的条件编译
#if FEATURE_B_LEVEL > 2
cout << "Feature B at high level (" << FEATURE_B_LEVEL << ")" << endl;
#elif FEATURE_B_LEVEL > 0
cout << "Feature B at basic level (" << FEATURE_B_LEVEL << ")" << endl;
#else
cout << "Feature B is disabled" << endl;
#endif
// 头文件保护模拟
#ifndef MY_HEADER_GUARD
#define MY_HEADER_GUARD
cout << "This would be included only once" << endl;
#endif
// 尝试再次包含相同内容（不会执行）
#ifndef MY_HEADER_GUARD
cout << "This won't be printed" << endl;
#endif
return 0;
}红黑树的迭代器
迭代器的核心源码
struct __rb_tree_base_iterator
{
typedef __rb_tree_node_base::base_ptr base_ptr;
base_ptr node;
void increment()
{
if (node->right != 0) {
node = node->right;
while (node->left != 0)
node = node->left;
}
else{
base_ptr y = node->parent;
while (node == y->right) {
node = y;
y = y->parent;
}
if(node->right != y)
node = y;
}
}
void decrement()
{
if (node->color == __rb_tree_red &&
node->parent->parent == node)
node = node->right;
else if (node->left != 0) {
base_ptr y = node->left;
while (y->right != 0)
y = y->right;
node = y;
}
else{
base_ptr y = node->parent;
while (node == y->left) {
node = y;
y = y->parent;
}
node = y;
}
}
};
template <class Value, class Ref, class Ptr>
struct __rb_tree_iterator : public __rb_tree_base_iterator
{
typedef Value value_type;
typedef Ref reference;
typedef Ptr pointer;
typedef __rb_tree_iterator<Value, Value&, Value*> iterator;
__rb_tree_iterator() {}
__rb_tree_iterator(link_type x) { node = x; }
__rb_tree_iterator(const iterator& it) { node = it.node; }
reference operator*() const { return link_type(node)->value_field; }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
self& operator++() { increment(); return *this; }
self& operator--() { decrement(); return *this; }
inline bool operator==(const __rb_tree_base_iterator& x,
const __rb_tree_base_iterator& y) {
return x.node == y.node;
}
inline bool operator!=(const __rb_tree_base_iterator& x,
const __rb_tree_base_iterator& y) {
return x.node != y.node;
}
};迭代器实现思路
iterator实现的⼤框架跟list的iterator思路是⼀致的，⽤⼀个类型封装结点的指针，再通过重载运算符实现，迭代器像指针⼀样访问的⾏为。
源代码的迭代器：
set
//set
class set {
public:
// typedefs:
typedef Key key_type;
typedef Key value_type;
typedef Compare key_compare;
typedef Compare value_compare;
private:
typedef rb_tree<key_type, value_type,
identity<value_type>, key_compare, Alloc> rep_type;
rep_type t; // red-black tree representing set
//迭代器
public:
typedef typename rep_type::const_pointer pointer;
typedef typename rep_type::const_pointer const_pointer;
typedef typename rep_type::const_reference reference;
typedef typename rep_type::const_reference const_reference;
typedef typename rep_type::const_iterator iterator;
typedef typename rep_type::const_iterator const_iterator;
typedef typename rep_type::const_reverse_iterator reverse_iterator;
typedef typename rep_type::const_reverse_iterator const_reverse_iterator;
typedef typename rep_type::size_type size_type;
typedef typename rep_type::difference_type difference_type;
};map
//map
class map {
public:
// typedefs:
typedef Key key_type;
typedef T data_type;
typedef T mapped_type;
typedef pair<const Key, T> value_type;
typedef Compare key_compare;
private:
typedef rb_tree<key_type, value_type,
select1st<value_type>, key_compare, Alloc> rep_type;
rep_type t; // red-black tree representing map
//迭代器
public:
typedef typename rep_type::pointer pointer;
typedef typename rep_type::const_pointer const_pointer;
typedef typename rep_type::reference reference;
typedef typename rep_type::const_reference const_reference;
typedef typename rep_type::iterator iterator;
typedef typename rep_type::const_iterator const_iterator;
typedef typename rep_type::reverse_iterator reverse_iterator;
typedef typename rep_type::const_reverse_iterator const_reverse_iterator;
typedef typename rep_type::size_type size_type;
typedef typename rep_type::difference_type difference_type;
};红黑树
//红黑树
template <class Value, class Ref, class Ptr>
struct __rb_tree_iterator : public __rb_tree_base_iterator
{
typedef Value value_type;
typedef Ref reference;
typedef Ptr pointer;
typedef __rb_tree_iterator<Value, Value&, Value*> iterator;
typedef __rb_tree_iterator<Value, const Value&, const Value*> const_iterator;
typedef __rb_tree_iterator<Value, Ref, Ptr> self;
typedef __rb_tree_node<Value>* link_type;
template <class Key, class Value, class KeyOfValue, class Compare,
class Alloc = alloc>
};
class rb_tree {
protected:
typedef void* void_pointer;
typedef __rb_tree_node_base* base_ptr;
typedef __rb_tree_node<Value> rb_tree_node;
typedef simple_alloc<rb_tree_node, Alloc> rb_tree_node_allocator;
typedef __rb_tree_color_type color_type;
public:
typedef Key key_type;
typedef Value value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef rb_tree_node* link_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
//迭代器
typedef __rb_tree_iterator<value_type, reference, pointer> iterator;
typedef __rb_tree_iterator<value_type, const_reference, const_pointer>
const_iterator;
};
迭代器++/--
迭代器实现的难点是operator++和operator--的实现。之前我们知道map和set的迭代器⾛
的是中序遍历，左⼦树->根结点->右⼦树，那么begin()会返回中序第⼀个结点的iterator也就是10
所在结点的迭代器。
迭代器++的核⼼逻辑就是不看全局，只看局部，只考虑当前中序局部要访问的下⼀个结点。
迭代器++时，如果it指向的结点的右⼦树不为空，代表当前结点已经访问完了，要访问下⼀个结点是右⼦树的中序第⼀个，⼀棵树中序第⼀个是最左结点，所以直接找右⼦树的最左结点即可。
迭代器++时，如果it指向的结点的右⼦树空，代表当前结点已经访问完了且当前结点所在的⼦树也访问完了，要访问的下⼀个结点在当前结点的祖先⾥⾯，所以要沿着当前结点到根的祖先路径向上找。
如果当前结点是⽗亲的左，根据中序左⼦树->根结点->右⼦树，那么下⼀个访问的结点就是当前结点的⽗亲；如下图：it指向25，25右为空，25是30的左，所以下⼀个访问的结点就是30。
end()如何表⽰呢？如下图：当it指向50时，++it时，50是40的右，40是30的右，30是18的右，18到根没有⽗亲，没有找到孩⼦是⽗亲左的那个祖先，这是⽗亲为空了，那我们就把it中的结点指针置为nullptr，我们⽤nullptr去充当end。需要注意的是stl源码空，红⿊树增加了⼀个哨兵位头结点做为end()，这哨兵位头结点和根互为⽗亲，左指向最左结点，右指向最右结点。相⽐我们⽤nullptr作为end()，差别不⼤。只是--end()判断到结点时空，特殊处理⼀下，让迭代器结点指向最右结点。
迭代器--的实现跟++的思路完全类似，逻辑正好反过来即可，因为他访问顺序是右⼦树->根结点->左⼦树
set的iterator也不⽀持修改，我们把set的第⼆个模板参数改成const K即可
RBTree<K,const K, SetKeyOfT> _t;map的iterator不⽀持修改key但是可以修改value，我们把map的第⼆个模板参数pair的第⼀个参数改成const K即可
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
//迭代器
template<class T,class Ref,class Ptr>
struct TreeIterator
{
typedef RBTreeNode<T> Node;
typedef TreeIterator<T,Ref,Ptr> Self;
Node* _node;
TreeIterator(Node* node)
:_node(node)
{
}
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;
}
//前置--
Self& operator--()
{
// ...
return *this;
}
//前置++
Self& operator++()
{
//当前右不为空，下一个就是右子树有序第一个（最左结点）
if (_node->_right)
{
Node*min=_node->_right;
while (min->_left)
{
min=min->_left;
}
_node=min;
}
//当前右为空，下一个就是孩子是父亲左的那个祖先结点
else
{
Node* cur = _node;
Node* parent = _node->_parent;
while (parent&& cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
};map的[]插入
map要⽀持[]主要需要修改insert返回值⽀持，修改RBtree中的insert返回值为
pair<Iterator, bool> Insert(const T& data)通过insert实现[]插入
//RBTree.h
pair<Iterator, bool> Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(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(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else
{
return make_pair(Iterator(cur), false);
}
}
cur = new Node(data);
// 新增节点。颜色红色给红色
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;
// g
// p u
if (parent == grandfather->_left)
{
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)
{
// g
// p u
//c
//单旋
RotateR(grandfather);
//变色
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p u
// c
//双旋
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
// g
// u p
Node* uncle = grandfather->_left;
// 叔叔存在且为红色-》变色
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else // 情况⼆：叔叔不存在或者存在为黑
{
// 情况⼆：叔叔不存在或者存在为黑
// 旋转+变色
// g
// u p
// c
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return make_pair(Iterator(cur), true);
}
//my_set.h
pair<iterator, bool> Insert(const K& k)
{
return _t.Insert(k);
}
//my_map.h
pair<iterator, bool> Insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = _t.Insert({key,V()});
return ret.first->second;
//用迭代器访问value
}源代码
RBTree.h
#pragma once
#include <iostream>
using namespace std;
// 枚举值表示颜色
enum Colour
{
RED,
BLACK
};
// 节点结构
template<class T>
struct RBTreeNode
{
// 这里更新控制平衡也需要parent指针
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)
{
}
};
// 迭代器
template<class T, class Ref, class Ptr>
struct TreeIterator
{
typedef RBTreeNode<T> Node;
typedef TreeIterator<T, Ref, Ptr> Self;
typedef TreeIterator<T, T&, T*> Iterator;
Node* _node;
TreeIterator(Node* node)
:_node(node)
{
}
// 允许从普通迭代器构造const迭代器
TreeIterator(const Iterator& it)
:_node(it._node)
{
}
Ref operator* () const
{
return _node->_data;
}
Ptr operator->() const
{
return &_node->_data;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
// 前置--
Self& operator--()
{
if (_node->_left)
{
// 左子树存在，找左子树的最右节点
Node* max = _node->_left;
while (max->_right)
{
max = max->_right;
}
_node = max;
}
else
{
// 左子树不存在，向上找第一个是父节点右孩子的节点
Node* cur = _node;
Node* parent = _node->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
// 后置--
Self operator--(int)
{
Self tmp = *this;
--(*this);
return tmp;
}
// 前置++
Self& operator++()
{
// 当前右不为空，下一个就是右子树有序第一个（最左结点）
if (_node->_right)
{
Node* min = _node->_right;
while (min->_left)
{
min = min->_left;
}
_node = min;
}
// 当前右为空，下一个就是孩子是父亲左的那个祖先结点
else
{
Node* cur = _node;
Node* parent = _node->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
// 后置++
Self operator++(int)
{
Self tmp = *this;
++(*this);
return tmp;
}
};
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef TreeIterator<T, T&, T*> Iterator;
typedef TreeIterator<T, const T&, const T*> ConstIterator;
Iterator Begin()
{
Node* min = _root;
while (min && min->_left)
{
min = min->_left;
}
return Iterator(min);
}
Iterator End()
{
return Iterator(nullptr);
}
ConstIterator Begin() const
{
Node* min = _root;
while (min && min->_left)
{
min = min->_left;
}
return ConstIterator(min);
}
ConstIterator End() const
{
return ConstIterator(nullptr);
}
// 查找节点并返回const迭代器
ConstIterator Find(const K& key) const
{
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 ConstIterator(cur);
}
}
return End();
}
// 红黑树插入
// 旋转代码的实现跟AVL树是一样的，只是不需要更新平衡因子
pair<Iterator, bool> Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(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(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else
{
return make_pair(Iterator(cur), false);
}
}
cur = new Node(data);
// 新增节点。颜色红色给红色
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;
// g
// p u
if (parent == grandfather->_left)
{
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)
{
// g
// p u
//c
//单旋
RotateR(grandfather);
//变色
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p u
// c
//双旋
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
else
{
// g
// u p
Node* uncle = grandfather->_left;
// 叔叔存在且为红色-》变色
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
// 继续往上处理
cur = grandfather;
parent = cur->_parent;
}
else // 情况⼆：叔叔不存在或者存在为黑
{
// 情况⼆：叔叔不存在或者存在为黑
// 旋转+变色
// g
// u p
// c
if (cur == parent->_right)
{
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// u p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return make_pair(Iterator(cur), true);
}
private:
// 右单旋
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 (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
Node* _root = nullptr;
};my_set.h
#pragma once
#include"RBTree - 副本.h"
namespace The_Song_of_the_end_of_the_world
{
template<class K>
class Set
{
//取出set中所有的key值的仿函数
//照顾map而设计的泛型
struct SetKeyOf
{
const K& operator()(const K& k)
{
return k;
}
};
public:
//通过typename关键字来声明迭代器类型
typedef typename RBTree<K, K, SetKeyOf>::Iterator iterator;
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}
pair<iterator, bool> Insert(const K& k)
{
return _t.Insert(k);
}
private:
RBTree<K,K,SetKeyOf> _t;
};
}my_map.h
#pragma once
#include"RBTree - 副本.h"
namespace The_Song_of_the_end_of_the_world
{
template<class K,class V>
class Map
{
//取出set中所有的key值的仿函数
//照顾map而设计的泛型
struct MapKeyOf
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<const K, V>, MapKeyOf>::Iterator iterator;
iterator begin()
{
return _t.Begin();
}
iterator end()
{
return _t.End();
}
pair<iterator, bool> Insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = _t.Insert({key,V()});
return ret.first->second;
//用迭代器访问value
}
private:
RBTree<K, pair<const K, V>,MapKeyOf> _t;
};
}测试代码：
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include "my_map.h"
#include "my_set.h"
#include <string>
using namespace std;
//迭代器源码：
//struct __rb_tree_base_iterator
//{
// typedef __rb_tree_node_base::base_ptr base_ptr;
// base_ptr node;
// void increment()
// {
// if (node->right != 0) {
// node = node->right;
// while (node->left != 0)
// node = node->left;
// }
// else {
// base_ptr y = node->parent;
// while (node == y->right) {
// node = y;
// y = y->parent;
// }
// if (node->right != y)
// node = y;
// }
// }
// void decrement()
// {
// if (node->color == __rb_tree_red &&
// node->parent->parent == node)
// node = node->right;
// else if (node->left != 0) {
// base_ptr y = node->left;
// while (y->right != 0)
// y = y->right;
// node = y;
// }
// else {
// base_ptr y = node->parent;
// while (node == y->left) {
// node = y;
// y = y->parent;
// }
// node = y;
// }
// }
//};
//template <class Value, class Ref, class Ptr>
//struct __rb_tree_iterator : public __rb_tree_base_iterator
//{
// typedef Value value_type;
// typedef Ref reference;
// typedef Ptr pointer;
// typedef __rb_tree_iterator<Value, Value&, Value*> iterator;
// __rb_tree_iterator() {}
// __rb_tree_iterator(link_type x) { node = x; }
// __rb_tree_iterator(const iterator& it) { node = it.node; }
// reference operator*() const { return link_type(node)->value_field; }
//#ifndef __SGI_STL_NO_ARROW_OPERATOR
// pointer operator->() const { return &(operator*()); }
//#endif /* __SGI_STL_NO_ARROW_OPERATOR */
// self& operator++() { increment(); return *this; }
// self& operator--() { decrement(); return *this; }
// inline bool operator==(const __rb_tree_base_iterator& x,
// const __rb_tree_base_iterator& y) {
// return x.node == y.node;
// }
// inline bool operator!=(const __rb_tree_base_iterator& x,
// const __rb_tree_base_iterator& y) {
// return x.node != y.node;
// }
//};
void test_set()
{
The_Song_of_the_end_of_the_world::Set<int> s;
s.Insert(4);
s.Insert(2);
s.Insert(1);
s.Insert(6);
The_Song_of_the_end_of_the_world::Set<int>::iterator it = s.begin();
while (it != s.end())
{
cout<<*it<<" ";
++it;
}
}
void test_map()
{
The_Song_of_the_end_of_the_world::Map<string, string> map;
map.Insert({ "hello", "world" });
map.Insert({ "apple", "banana" });
map.Insert({ "dog", "cat" });
The_Song_of_the_end_of_the_world::Map<string, string>::iterator it = map.begin();
map["left"] = "左边，剩余";
map["insert"] = "插入";
map["string"];
while (it != map.end())
{
cout << it->first << " " << it->second << endl;
++it;
}
}
int main()
{
//test_set();
test_map();
return 0;
}
软件推荐：source insight
Source Insight 是一款为编写和阅读大型代码项目而设计的源代码编辑器和浏览器。它以其卓越的代码导航和分析能力而闻名，尤其在 C/C++ 开发领域拥有大量忠实用户。
1. 强大的代码导航与分析（核心优势）
这是 Source Insight 的立身之本。它能快速解析整个代码库，构建一个详细的符号数据库（函数、变量、类、宏等），从而实现：
-
关系浏览：轻松查看函数调用关系（谁调用这个函数、这个函数又调用了谁）、类继承关系、符号定义和引用。
-
快速跳转：
Ctrl+Click点击任何函数或变量，即可立即跳转到它的定义处。 -
上下文窗口：一个悬浮窗，显示当前函数或变量的定义，无需离开当前位置。
-
符号窗口：列出所有文件中的函数、变量、类等符号，方便快速导航。
2. 高效的源代码编辑
-
语法高亮：支持多种语言，并可高度自定义。
-
智能自动完成：基于其强大的符号数据库，提供的自动补全建议非常准确和智能。
-
代码片段：支持创建和使用代码片段模板，提高编码效率。
-
代码格式重排：可以按照自定义风格格式化代码。
3. 项目范围的理解
-
快速构建整个项目（而非单个文件）的符号数据库。
-
提供项目范围的搜索、查找引用、重构等功能，让你轻松理清大型项目中海量文件之间的复杂关系。
4. 语言支持
主要专注于C和C++，并对它们提供了最深层次的支持。同时也支持 Java、C#、Python、PHP、HTML 等多种语言，但其核心优势仍在 C/C++。
5. 其他特点
-
运行速度快：相较于许多重型 IDE，它非常轻快敏捷。
-
Windows 原生应用：界面符合 Windows 操作习惯。
-
高度可定制：快捷键、配色方案、命令等都可以自定义。
拓展：条件编译
已经阐述过了。因为条件编译实际上再项目中应用十分广泛因此作者在这里再说一遍
在之前的源码中stl_tree.h中有这么一段，实际含义是这样的
#ifndef __SGI_STL_SET_H // 如果没有定义 __SGI_STL_SET_H 宏
#define __SGI_STL_SET_H // 定义 __SGI_STL_SET_H 宏
#include <tree.h> // 包含树结构相关的头文件
#include <stl_set.h> // 包含STL集合实现
#ifdef __STL_USE_NAMESPACES // 如果定义了 __STL_USE_NAMESPACES 宏
using __STD::set; // 使用命名空间 __STD 中的 set 类
#endif /* __STL_USE_NAMESPACES */ // 结束条件编译
#endif /* __SGI_STL_SET_H */ // 结束头文件保护基本语法为：
#ifdef 宏名
// 如果宏已定义，编译此部分代码
#else
// 如果宏未定义，编译此部分代码
#endif
#ifndef 宏名
// 如果宏未定义，编译此部分代码
#else
// 如果宏已定义，编译此部分代码
#endif
#if 表达式
// 如果表达式为真，编译此部分代码
#elif 另一个表达式
// 如果前一个表达式为假且此表达式为真，编译此部分
#else
// 如果所有表达式都为假，编译此部分
#endif再举一个实际案例：
#include <iostream>
using namespace std;
// 示例1：平台特定代码
#ifdef _WIN32
#define PLATFORM "Windows"
#elif __linux__
#define PLATFORM "Linux"
#elif __APPLE__
#define PLATFORM "macOS"
#else
#define PLATFORM "Unknown"
#endif
// 示例2：调试模式
#define DEBUG_MODE 1
// 示例3：功能开关
#define FEATURE_A_ENABLED
#define FEATURE_B_LEVEL 3
int main() {
// 平台检测
cout << "Running on: " << PLATFORM << endl;
// 调试代码
#if DEBUG_MODE
cout << "Debug information: Program started" << endl;
#endif
// 功能开关
#ifdef FEATURE_A_ENABLED
cout << "Feature A is enabled" << endl;
#endif
// 带值的条件编译
#if FEATURE_B_LEVEL > 2
cout << "Feature B at high level (" << FEATURE_B_LEVEL << ")" << endl;
#elif FEATURE_B_LEVEL > 0
cout << "Feature B at basic level (" << FEATURE_B_LEVEL << ")" << endl;
#else
cout << "Feature B is disabled" << endl;
#endif
// 头文件保护模拟
#ifndef MY_HEADER_GUARD
#define MY_HEADER_GUARD
cout << "This would be included only once" << endl;
#endif
// 尝试再次包含相同内容（不会执行）
#ifndef MY_HEADER_GUARD
cout << "This won't be printed" << endl;
#endif
return 0;
}实际应用
跨平台开发
#ifdef _WIN32
#include <windows.h>
#else
#include <unistd.h>
#endif调试与版本发布
#ifdef DEBUG
#define LOG(msg) std::cout << "DEBUG: " << msg << std::endl
#else
#define LOG(msg)
#endif功能定制
#if VERSION == 2
// 版本2特有功能
#include "new_features.h"
#elif VERSION == 1
// 版本1功能
#include "basic_features.h"
#endif防止重复编译头文件
// myheader.h
#ifndef MYHEADER_H
#define MYHEADER_H
// 头文件内容
#endif
本期关于map/set的源码剖析和模拟实现功能到这里就结束了，喜欢请点个赞谢谢。
封面图自取：
更多推荐
25
0- 0
已为社区贡献19条内容
所有评论(0)