简单了解map 和 set 的实现

 首先我们要知道，map 和 set 的底层就是 红黑树，但是 STL 当中 ，map 和 set 并不是我们想象的，直接使用一个 pair 对象来存储一个 key-value 或者 是 一个 key。具体如下所示：

set：

 在set 当中，只需要存储一个 key 就可以了，因为 set  是 key 的结构。但是在库当中，把 key  typedef 了两个值 key_type 和value_type：

map：

 在map 当中也是使用了 key_type 和 value_type，但是map 本身就是 key-value 的结构。然后我们又发现，map 的 value_type 又是 使用 pair 类进行封装存储的：

 我们在来看 红黑树的 部分源代码：
 

 也就是说，在 map 和 set 当中的值，真正存入 红黑树当中的，其实是 Value。按照上述的说法，set 存入红黑树的是 Key；map 存入红黑树的是 一个 pair 对象，对象当中存储的 是key-value 。

 所以，现在你就搞清楚，为什么 set 多搞出来的 key ，和 map 的 Value 为什么要用 pair 来设计，这两者到底用到哪里去了。

而 在STL 当中 的红黑树 的结点类 套了两层，先实现了 __rb_tree_node_base类，这个类当中就是 一个结点的三叉链，还有颜色等等的结点成员， 然后用一个 _rb_tree_node 类 去继承这个类：
 

 此时的 set 或者 map 当中的 key 或者 key-value 就直接通过模版继承到 __rb_tree_node 的 Value 当中了：
 

 也就是说，在红黑树结点类当中，不管传入的是 key 的结构还是 key-value 的结构，都是存储在 红黑树结点类的 Value 当中的，这里利用模版搞了一个泛型。

那么为什么在 set 当中要用 两个 key ，在 map 当中也要和 用一个 key 多在模版当中传如呢？

 如上，这个函数在 set 和 map 当中肯定是要实现的，如果我们set当中只有一个 key，在map 当中也是只有 pair 来存储键值对，那么在上述函数调用的时候，对于set 还好，因为 set 的value 就是一个 key ，但是 map 的value是一个pair，pair 如果作为参数来传入这个 find 函数的话，在find（）当中的实现又是直接使用 x 这个key 来实现的，pair 当中的key 要单独访问。所以，map 直接传入 pair 是不行的。

所以，在map 当中就把 key 单独拿出来了，set 为了适配 map，和 map 保持一致，也跟着把 key 单独多列一个出来。

红黑树的代码  和 set，map当中的大体框架

 关于红黑树的实现，请看下面这篇博客：
C++ - 红黑树 介绍 和 实现_chihiro1122的博客-CSDN博客

 在上述博客当中写的红黑树，其中的就是简单  key-value 结构，用 pair 存储，是写死的。而上述我们修改出来的红黑树就是一个 泛型。红黑树的结点当中的值，不在值存储 pair，还可以支持 set 单独存储 key。

大致结构：

 注意，因为上述上述可能需要多个 头文件，如果 头文件在 cpp 文件当中没有包含的话，头文件是不会进行 编译的，那么其中的错误就不会编译出来。

 而且，对于 红黑树当中的 insert（）插入函数，其中参数是 插入 value，但是，set 是 key，map 是 key-value，所以，我们这里直接使用 模版参数 T 传入就行：
 

 但是，又遇到了一个大问题，在  insert（）比较函数当中，我们使用的是 key 值来进行比较的，但是 此时 T 的模版参数是 pair 的话，我们之前使用 key 来作为参数比较的规则就不适用了。

 这时候，就需要去重载  pair 类的  "<" ">" 运算符 了，其实在 pair 的实现当中官方就已经重载了运算符重载函数：

但是，你仔细观察，其实这里面的比较规则 不是我们想要的比较规则，比如小于：他这里实现的是，first 小 就小，否则，second 小就小。 但是我们只期望用 key 来比。

 库当中已经实现了，所以，这里我们不能直接去重载 pair 当中的 大于小于运算符重载函数，参数也是一样的，两者之间不好重载。

所以，这里我们就要使用仿函数的方式去实现。仿函数的博客可以看以下博客：C++ - 优先级队列（priority_queue）的介绍和模拟实现 - 反向迭代器的适配器实现 - 仿函数_c++ priority_queue迭代器_chihiro1122的博客-CSDN博客

 但是，在上述优先级队列当中实现的仿函数，该仿函数的功能是比较大小；但是在红黑树当中的仿函数不是比较大小。

在 库当中的红黑树，还有一个 参数是 KeyOfValue：

 这个 KeyOfValue 模版参数意思就是把 value 当中的 key 取出来。

所以，我们要想 优先级队列当中仿函数的使用规则一样，把仿函数的类通过模版参数传入进去。

因为 ，这个 仿函数的类不是写给用户来控制的，是写给 map 和set 来使用的，所以，关于仿函数的类我们可以直接在 set 和 map 当中使用内部类来构造，关于 set 和 map 的内部类仿函数构造如下：

set：

#pragma once
#include"RBTree.h"namespace Mynamespace
{template<class K>class set{struct SetKeyOfT{// 和 map 对照的标准写法//const k& operator()(const pair<K, K>& kv)//{//	return p.first;//}// 其实可以直接这样写const k& operator()(const K& key){return key;}};private:RBTree<K, K , SetKeyOfT> _t;};
}

 map：

#pragma once
#include"RBTree.h"namespace Mynamespace
{template<class K, class V>class map{struct MapKeyOfT{const k& operator()(const pair<K, K>& kv){return p.first;}};private:RBTree<K, pair<K , V> , MapKeyOfT> _t;};
}

两者的仿函数的返回值都是把 set 的 key 和 map 的pair里的key 取出来，作为函数的返回值返回。

这样的话，我们就可以在 红黑树的 insert（）函数当中，使用仿函数来取出 对应的 key 值，然后进行key 值的比较了。

红黑树当中对仿函数的调用如下例子：

这里就调用 kot 对象当中的仿函数，把 _data 当中的 key 值取出来，如果这个 _data 是set 的，那么 key 就是直接返回，如果是 map 的，就需要从 pair 当中取出。

 这里之所以不想之前，在优先级队列当中的仿函数一样直接仿函数的那种进行比较，因为我们直接在仿函数当中进行比较的话，不好进行比较，不清楚到底怎样取出 key 。只有像上述一样，写两个仿函数的类，然后通过模版参数，知道此时我需要怎样取出 key 值。

 这一个仿函数只实现 取出 key 的功能，是因为要和 比较方式分离，如果我们在 取出 key 的仿函数当中就把 如何比较 实现了，当然是可以的，但是，如果这样做的话，相当于是把比较方式写死了，如果我们想要用 仿函数的方式来在 set 和 map 当中进行 区别比较方式的话，那么在 set 和map 的模版参数当中就需要再实现一个 区别 比较方式的 仿函数类。

但是，对于 我们刚刚实现的 MapKeyOfT 和 SetKeyOfT 这两个仿函数类，如果是单独使用 set 和 map 的人是不会关心的，因为这两个仿函数是供给 内部用的，外部根本就不需要。所以我们发现，在官方库的 红黑树当中 除了 有一个 控制 取出不同key 的方式的仿函数之外，还有一个 控制比较方式的仿函数，这样就控制在 内部了（树一层）。

 看一个例子就明白了：

 如上述的 find（）函数当中的比较，就是 _data 和 key 的比较；而在 insert（）当中的比较就是 _data 和 _data 的比较，两种比较的方式就不一样的，不能单独的直接写死，如果我又想用仿函数去控制的话，那么比较的方式这么多，得写多少仿函数。

 所以，库当中使用的是 两种 仿函数，一个吧 key 值取出的方式（set 和 map 不同）取出，然后直接在外部比较 key 值就行了，而且只用控制 除了 （取出 key 值不同的之外的 比较方式。如：大于小于的不同，和 key + value的比较方式）

u而 set 当中的 返回的就是 key ，其实 本身就是可以比较的，但是为了和 map 构成泛型，要多调用一次仿函数。

如上图所示，是库当中 红黑树的 模版参数，发现还有一个 Compare 参数，这个就是用来控制比较方式的 仿函数。

红黑树的代码：
 

#pragma once
#include<iostream>
using namespace std;// 节点的颜色
enum Colour
{RED,BLACK
};template<class T>
struct RBTreeNode
{RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};template<class T>
struct __TreeIterator
{typedef RBTreeNode<T> Node;typedef __TreeIterator<T> Self;Node* _node;__TreeIterator(Node* node):_node(node){}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}Self& operator--();Self& operator++(){// 此时就是最简单的情况// 直接找出该结点的右子树的最小结点if (_node->_right){// 右树的最左节点(最小节点)Node* subLeft = _node->_right;while (subLeft->_left){subLeft = subLeft->_left;}_node = subLeft;}else  //_node->_left{Node* cur = _node;Node* parent = cur->_parent;// 找孩子是父亲左的那个祖先节点，就是下一个要访问的节点while (parent){if (cur == parent->_left){break;   // 说明已经找到，parent此时就是下一次需要迭代的结点}// 如果程序走到这里，该结点和 父亲结点的左右子树都遍历完了// 就要往上迭代// 直到找到 父亲 的右子树没有找完的情况else  //cur == parent->_right{cur = cur->_parent;parent = parent->_parent;}}_node = parent;}return *this;}
};// set->RBTree<K, K, SetKeyOfT> _t;
// map->RBTree<K, pair<K, V>, MapKeyOfT> _t;// 红黑树节点的定义
template<class K, class T, class KeyOfT>
struct RBTree
{typedef RBTreeNode<T> Node;
public:typedef __TreeIterator<T> iterator;// const_iteratoriterator begin(){Node* leftMin = _root;// 加上 subleft 这个条件是为了防止 这棵树是空while (leftMin && leftMin->_left){leftMin = leftMin->_left;}return iterator(leftMin);}iterator end(){// end（）不用像上述一样 找最大值// 通过迭代器当中的 operator++（）函数我们知道，中序最后都是遍历到 nullptr 的// 这个 nullptr就是 根结点的父亲指针指向的 nullptrreturn iterator(nullptr);}Node* Find(const K& key){Node* cur = _root;KeyOfT kot;while (cur){if (kot(cur->_data) < key){cur = cur->_right;}else if (kot(cur->_data) > key){cur = cur->_left;}else{return cur;}}return nullptr;}bool Insert(const T& data){// 搜索二叉树的插入逻辑// // 如果当前树为空，直接用头指针只想新结点if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return true;}// 不为空接着走Node* parent = nullptr;  // 用于首次插入时候指针的迭代Node* cur = _root;KeyOfT kot;while (cur){// 如果当前新插入的 key 值比 当前遍历的结点 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 false;}}// 此时已经找到 应该插入的位置cur = new Node(data);cur->_col = RED;// 再次判断大小，判断 cur应该插入到 parent 的那一边if (kot(parent->_data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}// 链接 新插入结点 cur 的_parent 指针cur->_parent = parent;// 红黑树调整高度（平衡高度）的逻辑while (parent && parent->_col == RED){// parent 为 红，parent->_parent 一定不为空Node* grandfather = parent->_parent;// 如果父亲是在 祖父的左if (parent == grandfather->_left){Node* uncle = grandfather->_right;// u存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else // u不存在 或 存在且为黑{if (cur == parent->_left){//     g//   p// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   p//		cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;// 不需要再往上更新}}else // parent == grandfather->_right{Node* uncle = grandfather->_left;// u存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else// 不存在 或者 存在且为黑色{if (cur == parent->_right){// g//	  p//       cRotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{// g//	  p// cRotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}// 不管上述如何修改，红黑树的根结点永远是黑的// 所以我们这里既直接硬性处理_root->_col = BLACK;return true;}void RotateL(Node* parent){Node* cur = parent->_right; // 存储 parent 的右孩子Node* curleft = cur->_left; // 存储 cur 的左孩子parent->_right = curleft;if (curleft)                // 判断 cur 的左孩子是否为空{curleft->_parent = parent;  // 不为空就 修改 cur 的左孩子的_parent 指针}cur->_left = parent;// 留存一份 根结点指针Node* ppnode = parent->_parent;parent->_parent = cur;// 如果parent 是根结点if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}void RotateR(Node* parent){Node* cur = parent->_left;Node* curRight = cur->_right;parent->_left = curRight;if (curRight){curRight->_parent = parent;}cur->_right = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}bool CheckColor(Node* root, int blacknum, int benchamark){// 当走到叶子结点的 null 指针处，也就是 NIL结点处if (root == nullptr){// 如果计算出的路径黑色结点长度 和 外部计算的不一样// 说明不是红黑树if (blacknum != benchamark){cout << "路径黑色结点个数不一样" << endl;return false;}return true;}// 用于递归计算 路径的黑色结点个数if (root->_color == BLACK)blacknum++;// 如果当前结点为 红色，且当前结点的父亲也是红色，就不是红黑树if (root->_parent && root->_parent->_color == RED && root->_color == RED){cout << "有连续红色" << endl;return false;}// 左右子树递归return CheckColor(root->_left, blacknum, benchamark)&& CheckColor(root->_right, blacknum, benchamark);}// 外部调用接口bool isBalance(){return isBalance(_root);}// 内部封装函数bool isBalance(Node* root){if (root == nullptr)return true;// 如果整棵树的 根结点不是 黑色的就不是红黑树if (root->_color != BLACK){cout << "根结点不是黑色" << endl;return false;}// 基准值// 在递归外部计算出左路第一条路径的 黑色结点值int benchmark = 0;Node* cur = root;while (cur){if (cur->_color == BLACK)benchmark++;cur = cur->_left;}return CheckColor(root, 0, benchmark);}
private:Node* _root = nullptr;
};

 红黑树的迭代器

 二叉搜索树的遍历无非就是 中序遍历，但是，在迭代器实现当中还有 operator++（）和 operator--（）这些函数，比如说 ++ 该如何实现呢？

 框架和一些简单函数实现

// 红黑树迭代器的实现
template<class T>
struct __Treeiterator
{typedef RBTreeNode<T> Node;typedef __Treeiterator<T> Self;Node* _node;T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node == s._node;}
}

 begin（） 和 end（）

 

一个迭代器的基本使用方式无非就是下述的使用方式：
 

 那么，首先我们要找到 begin（）和 end（）指向的位置。begin（）在二叉搜索树当中就是中序遍历结果 第一个值，那么就是 这个树当中的最小值，所以就是 这棵树的最左边那个结点的值；而 edn（）就是 最右边的结点的值了。

end（）不用像上述一样 找最大值，通过迭代器当中的 operator++（）函数我们知道，中序最后都是遍历到 nullptr 的，这个 nullptr就是 根结点的父亲指针指向的 nullptr。

 

	typedef __Treeiterator<T> iterator;iterator begin(){Node* subleft = _root;// 加上 subleft 这个条件是为了防止 这棵树是空while (subleft && subleft->left){subleft = subleft->_left;}return iterator(subleft);}iterator end(){// end（）不用像上述一样 找最大值// 通过迭代器当中的 operator++（）函数我们知道，中序最后都是遍历到 nullptr 的// 这个 nullptr就是 根结点的父亲指针指向的 nullptrreturn iterator(nullptr);}

operator++（）函数

而，对于++函数，如下图所示：
 

 假设 it 此时是指向 8 的，那么此时要对 it迭代器 ++，那么就应该去找 8 的右子树的最小结点，也就是右子树的 最左结点。

 

 如果 it 指向 5 ，此时 it迭代器要 ++，就要分两种情况（因为中序的是左子树 根 右子树，所以看 右子树是否为空）：

右不为空，就要去访问右子树当中最左边的结点（最小结点）。

右不为空，此时说明该结点已经访问完了，要访问祖先，注意不是 不一定是父亲，应为此时 该结点可能为父亲的左 也有可能为 父亲的右，如果为父亲的左说明 父亲还没有访问结束，那么就访问父亲；如果 该结点是父亲的右，说明父亲已经访问完了，此时就要访问父亲的父亲。

 operator++（）函数代码：

Self& operator++(){// 此时就是最简单的情况// 直接找出该结点的右子树的最小结点if (_node->_right){Node* subleft = _node->_right;while (subleft->_left){subleft = subleft->_left;}_node = subleft;}else  //_node->_left{Node* cur = _node;Node* parent = cur->_parent;while (parent){if (cur == parent->_left){break;  // 说明已经找到，parent此时就是下一次需要迭代的结点}// 如果程序走到这里，该结点和 父亲结点的左右子树都遍历完了// 就要往上迭代// 直到找到 父亲 的右子树没有找完的情况else //cur == parent->_right{cur = cur->parent;parent = parent->_parent;}}_node = parent;}}

模拟实现set

insert（）：

直接套用 红黑树当中的 insert（）函数：
 

	public:bool insert(const T& key){// 因为底层是哟个红黑树实现的，直接套用红黑树的 插入return _t.insert(key);}

 迭代器

 因为，set 和 map 的底层都是用红黑树来实现的，在红黑树当中已经实现了 迭代器，那么我们完全可以使用 红黑树当中的迭代器来复用在 set 和 map 当中。

public:typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}

 注意：上述 使用了 typename 关键字修饰：

 是因为，RBTree<K, K, SetKeyOfT> 是一个模版，模版是没有实例化的，也就是说此时在模版当中的代码是没有进行编译的，那么里面除了可能会出现错误的情况下，在模版当中的 很多使用了模版参数的地方还没有进行实例化替换，那么此时编译器在 set 当中就会找不到 RBTree 类当中 typedef 出来的 iterator。

 而且，set 当中只存储 key ，所以不允许利用 *it = 10 这样的方式来对 set 当中的key 进行修改。

库当中的实现方式非常简单，就是无论是否是 const 的 迭代器都 认为是 const 的迭代器，也就是说其实 在 set 当中就一个迭代器，只有一个 const 的迭代器：
 

 

模拟实现 map

insert（）：

	public:bool insert(const T& key){// 因为底层是哟个红黑树实现的，直接套用红黑树的 插入return _t.insert(key);}

迭代器

 

public:typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}

map 当中 允许修改 value 但是不允许修改 key ，所以，map 当中不能像 set 当中一样，只实现一个 const 迭代器，在map 当中的迭代器还是正常的：

 map 是在存储层解决这个问题的：

 他的 T 都是好的，但是key 是 const 的。

意思就是当我们在外部取到 first 的时候，这个 first 就是一个  const 修饰的值，不能进行修改了;