一、set介绍
1.1 概念
1.2 常用接口
（1）insert
（2）erase
（3）swap
（4）clear
（5）find
（6）count
（7）size
（8）empty
1.3 multiset
二、map介绍
三、红黑树改造
四、模拟实现set
五、模拟实现map
一、set介绍
1.1 概念
set是C++STL库中的一个关联式容器，类似于Python中的集合，其特点是内部的元素是一个值（Key），它们有序且唯一，所以可用于对一个序列的排序和去重。
1.2 常用接口
（1）insert
pair<iterator,bool> insert (const value_type& val);
pair<iterator,bool> insert (value_type&& val);
插入一个元素，返回一个pair对象，其中包含一个迭代器和bool值
如果插入成功（set中没有该元素），pair中存放插入位置的迭代器和true
如果插入失败（set中已经存在该元素），pair中存放对应元素的迭代器和false
（2）erase
size_type erase (const value_type& val);
删除一个元素，返回删除的元素个数
（3）swap
void swap (set& x);
交换两个set中的元素
（4）clear
void clear() noexcept;
清除set中的所有元素
（5）find
const_iterator find (const value_type& val) const;
iterator find (const value_type& val);
在set中寻找目标元素并返回其位置的迭代器
如果没有该元素，则返回end()
（6）count
size_type count (const value_type& val) const;
返回set中值为val的元素个数
因为set的去重性，所以返回值只会是0或1
（7）size
size_type size() const noexcept;
返回set中的元素个数
（8）empty
bool empty() const noexcept;
判断set是否为空
1.3 multiset
基本与set相同，区别在于multiset可以插入相同的值
二、map介绍
map也是C++STL库中的一个关联式容器，类似于Python中的字典。
和set不同的是，map中的元素不是单一的key，而是一个key/value模型，也就是键值对。所以map中的元素都是pair对象
在map中，key必须是唯一的，但是value可以重复。排序时根据key进行排序
它可以通过查找key来获取value值。
map的接口使用方法和set差不多，只是把key换成了键值对
map重载了方括号，我们可以像使用下标一样用key来查找value
mapped_type& operator[] (const key_type& k);
mapped_type& operator[] (key_type&& k);
重载后的方括号可以用于插入元素和查找元素，方括号中传入key，就会返回value
三、红黑树改造
set是key结构，而map是key/value模型，要想让两者底层使用相同的代码，则需要对红黑树进行一定的改造
首先需要改造红黑树的模板参数。set只需要指定key的类型，但是map除了需要指定key的类型还需要指定value的类型，所以原先的模板参数是无法做到通用的，因为你不知道红黑树中存的是key还是pair对象。
因此我们可以设定一个class K接收key的类型，再设定一个class T接收容器内元素的类型。如果是set的话T的类型就是key的类型，如果是map的话T的类型就是一个pair。
但是在容器中我们需要获得key来进行许多操作，例如插入、查找。如果是map，我们可以用.first来拿到key，但是这种方法又不适用于set了。因此我们再设定一个class KeyOfT来接收二者传入的仿函数，用该仿函数来获取key即可。因为我们可以在map和set中个性化定义仿函数的内部细节，所以可以做到代码复用。
其他地方基本不需要做什么改动
完整代码如下：
#pragma onceenum 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, 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;}Self& operator--(){Node* parent = _node->_parent;if (_node->_left)_node = _node->_left;else if (_node == parent->_right)_node = parent;else{Node* cur = _node;while (parent && cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}Self& operator++(){if (_node->_right){Node* cur = _node->_right;while (cur->_left)cur = cur->_left;_node = cur;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}_node = parent;}return *this;}bool operator!=(const Self& s){return _node != s._node;}
};//K是key的类型，T是元素的类型（set中的T和K一样，map中T是一个pair类型），KeyOfT是获取key的仿函数
//因为该红黑树是set和map共用的，所以需要作此处理。因为虽然map中的pair类型元素可以直接用.first获取key，但是如果是set的话同样的代码就无法通用了
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*> const_iterator;iterator begin(){Node* cur = _root;while (cur && cur->_left)cur = cur->_left;return iterator(cur);}iterator end(){return iterator(nullptr);}const_iterator begin() const{Node* cur = _root;while (cur && cur->_left)cur = cur->_left;return const_iterator(cur);}const_iterator end() const{return const_iterator(nullptr);}pair<Node*, bool> insert(const T& data){if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(_root, true);}Node* parent = nullptr;Node* cur = _root;KeyOfT kot;while (cur){parent = cur;if (kot(data) > kot(cur->_data))cur = cur->_right;else if (kot(data) < kot(cur->_data))cur = cur->_left;elsereturn make_pair(cur, false);}cur = new Node(data);Node* newnode = cur;cur->_col = RED; //新节点默认为红色if (kot(data) > kot(parent->_data)){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}while (parent && parent->_col == RED) //若父节点不存在说明走到根，若父节点为黑色则不需要处理{Node* grandfather = parent->_parent; //记录祖父节点if (grandfather->_left == parent) //父节点在祖父节点左边时{Node* uncle = grandfather->_right; //记录叔叔节点if (uncle && uncle->_col == RED) //如果叔叔节点存在且为红色{//变色parent->_col = uncle->_col = BLACK; //将父节点与叔叔节点都变为黑色grandfather->_col = RED; //将祖父节点变为红色//继续向上处理cur = grandfather;parent = cur->_parent; }else //叔叔节点不存在或为黑色{//需要旋转+变色if (parent->_left == cur) //cur节点在父节点左边，右单旋{RotateRight(grandfather);//变色parent->_col = BLACK;grandfather->_col = RED;}else //cur节点在父节点右边，左右双旋{RotateLeft(parent);RotateRight(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 (parent->_right == cur){RotateLeft(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{RotateRight(parent);RotateLeft(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK; //无论如何，都将根变为黑色return make_pair(newnode, true);}void RotateLeft(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;Node* parentParent = parent->_parent;if (parent != _root){subR->_parent = parentParent;if (parent == parentParent->_left)parentParent->_left = subR;elseparentParent->_right = subR;}else{_root = subR;subR->_parent = nullptr;}subR->_left = parent;parent->_parent = subR;}void RotateRight(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;if (parent != _root){subL->_parent = parentParent;if (parent == parentParent->_left)parentParent->_left = subL;elseparentParent->_right = subL;}else{_root = subL;subL->_parent = nullptr;}subL->_right = parent;parent->_parent = subL;}void InOrder(){_InOrder(_root);cout << endl;}bool IsBalance(){if (_root == nullptr)return true;if (_root->_col == RED){cout << "异常：根为红色" << endl;return false;}//预先求出某条路径的黑色节点数量size_t blackcount = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)blackcount++;cur = cur->_left;}size_t k = 0;return _IsBalance(_root, k, blackcount);}iterator Find(const K& key){Node* cur = _root;KeyOfT kot;while (cur){if (key > kot(cur->_data))cur = cur->_right;else if (key < kot(cur->_data))cur = cur->_left;elsereturn iterator(cur);}return iterator(nullptr);}int Height(){return _Height(_root);}size_t Size(){return _Size(_root);}
private:void _InOrder(Node* root){KeyOfT kot;if (root == nullptr)return;_InOrder(root->_left);cout << kot(root->_data) << " ";_InOrder(root->_right);}bool _IsBalance(Node* root, size_t k, size_t blackcount){if (root == nullptr){if (k != blackcount){cout << "异常：路径黑节点数目不同" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << "异常：出现连续红节点" << endl;return false;}if (root->_col == BLACK)k++;return _IsBalance(root->_left, k, blackcount)&& _IsBalance(root->_right, k, blackcount);}int _Height(Node* root){if (root == nullptr)return 0;int higher = max(_Height(root->_left), _Height(root->_right));return higher + 1;}size_t _Size(Node* root){if (root == nullptr)return 0;return _Size(root->_left) + _Size(root->_right) + 1;}
private:Node* _root = nullptr;
};四、模拟实现set
在实现set和map的时候主要把仿函数实现出来就行了，其他接口直接封装红黑树的方法即可
因为红黑树中没有实现删除，所以set和map的删除也不实现了（纯懒）
#pragma once
#include "RBTree.h"namespace Eristic
{template<class K>class set {public:struct SetKeyOfT{const K& operator()(const K& key){return key;}};//在set和map中重命名迭代器时不加typename，迭代器运行的时候会报错//域作用限定符可以取类型或者静态变量，但是因为变量不能被typedef，所以我们需要用typename告诉编译器是对类型重命名typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator; typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;iterator begin() const{return _t.begin();}iterator end() const{return _t.end();}pair<iterator, bool> insert(const K& key){return _t.insert(key);}void InOrder(){_t.InOrder();}private:RBTree<K, K, SetKeyOfT> _t;};
}五、模拟实现map
#pragma once
#include "RBTree.h"namespace Eristic
{template<class K,class T>class map{public:struct MapKeyOfT{const K& operator()(const pair<K, T>& kv){return kv.first;}};typedef typename RBTree<K, pair<const K, T>, MapKeyOfT>::iterator iterator;typedef typename RBTree<K, pair<const K, T>, MapKeyOfT>::const_iterator const_iterator;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, T>& kv){return _t.insert(kv);}void InOrder(){_t.InOrder();}T& operator[](const K& key){pair<iterator, bool> p = insert(make_pair(key, T()));return p.first->second;}private:RBTree<K, pair<const K, T>, MapKeyOfT> _t;};
}完.
