map和set底层实现【C++】

底层实现【C++】"/>

map和set底层实现【C++】

文章目录

• map和set模板参数
• 红黑树结点中的数据
• 模板参数中的仿函数
• 正向迭代器
• • ++运算符重载
  • --运算符重载
• 库里的写法
• set
• map
• RBTree

map和set模板参数

set是K模型的容器，而map是KV模型的容器
如何用一棵KV模型的红黑树同时实现map和set

  template<class K ,class V>class map{// ...private:RBTree<K, pair<const K, V>, MapKeyOfT> _t; //map，MapKeyOfT是仿函数};

	class set{//...private:RBTree<K,K,SetKeyOfT> _t;};//set，SetKeyOfT是仿函数

红黑树结点中的数据

红黑树的节点是K还是T，对于set都是一样的 ,对于map,底层红黑树就只能存储T了。底层红黑树不知道上层容器是map还是set，因此红黑树的结点当中直接存储T就行了。

当上层容器是set，结点当中存储的是键值Key；当上层容器是map，结点当中存储的就是<Key, Value>键值对。

template<class T >
struct RBTreeNode
{RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;//颜色
};

模板参数中的仿函数

	class set{//仿函数struct SetKeyOfT{const K & operator()( const K &key){return key;}};private:RBTree<K,K,SetKeyOfT> _t;};

class map{//仿函数struct MapKeyOfT{const K& operator()( const pair<K,V> & kv){return kv.first;}};private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};

当上层容器是set，T就是键值Key，直接用T进行比较即可
当上层容器是map，此时我们需要从<Key, Value>键值对当中取出键值Key后，再用Key值进行比较
上层容器map需要向底层红黑树提供一个仿函数，用于获取T当中的键值Key，当底层红黑树当中需要比较两个结点的键值时，就可以通过这个仿函数来获取T当中的键值了

对于底层红黑树，它并不知道上层容器是map还是set，因此当需要进行两个结点键值的比较时，底层红黑树都会通过传入的仿函数来获取键值Key，进而进行两个结点键值的比较。

因此，set容器也需要向底层红黑树传入一个仿函数，虽然这个仿函数单独看起来没什么用，但却是必不可少的。

当底层红黑树需要进行两个结点之间键值的比较时，都会通过传入的仿函数来获取相应结点的键值，然后再进行比较 例如：

//查找函数
iterator Find(const K& key)
{KeyOfT kot;Node* cur = _root;while (cur){if (key < kot(cur->_data)) //key值小于该结点的值{cur = cur->_left; //在该结点的左子树当中查找}else if (key > kot(cur->_data)) //key值大于该结点的值{cur = cur->_right; //在该结点的右子树当中查找}else //找到了目标结点{return iterator(cur); //返回该结点}}return end(); //查找失败
}

正向迭代器

struct  _TreeIterator
{typedef RBTreeNode<T> Node;typedef _TreeIterator<T,Ptr,Ref> Self;typedef _TreeIterator<T, T*, T&> iterator;
};
//构造函数
__TreeIterator(Node* node):_node(node) //根据所给结点指针构造一个正向迭代器
{}

++运算符重载

1、右子树不为空，访问右树的最左节点（即为下一个节点）
2、如果当前结点的右子树为空，则++操作后应该在该结点的祖先结点中，找到孩子不在父亲右的祖先。

Self & operator++()//前置++，返回++之后的值{//右子树不为空，访问右树的最左节点//左子树不为空，如何解决？if (_node->_right != nullptr){//右树的最左节点(右树的最小节点)Node* subLeft = _node->_right;while (subLeft->_left != nullptr){subLeft = subLeft->_left;}_node = subLeft;}else//_node->_left != nulltptr{// 下一个要访问的节点，找孩子是父亲左的那个祖先节点Node* cur = _node;Node* parent = cur->_parent;while (parent!=nullptr){if (parent->_left != cur){//往上更新cur = parent;parent = parent->_parent;}else//parent->_left == cur{break;}}_node = parent;}return *this;}

–运算符重载

1、左子树存在 ，找当前节点的左子树中最右边的节点，就是所需要的节点
2、如果当前结点的左子树为空，则–操作后应该在该结点的祖先结点中，找到孩子不在父亲左的祖先。

	Self& operator--()//前置-- //右子树 、根 、左子树（中序反过来） {// 左子树存在 //将当前节点的左子树中最右边的节点，就是所需要的节点if (_node->_left != nullptr){Node* subRight = _node->_left;while (subRight && subRight->_right){subRight = subRight->_right;}_node = subRight;}//右子树存在//找孩子是父亲的右的那个节点else//_node->_right != nullptr{Node* cur = _node;Node* parent = cur->_parent;while (parent!=nullptr){//向上调整 cur = parent;parent = parent->_parent;}_node = parent;		}return *this;}

库里的写法

上述所实现的迭代器是有缺陷的，因为理论上我们对end()位置的正向迭代器进行–操作后，应该得到最后一个结点的正向迭代器，但我们实现end()时，是直接返回由nullptr构造得到的正向迭代器的，因此上述实现的代码无法完成此操作

C++SLT库当中的实现逻辑：

在红黑树的根结点处增加了一个头结点，
该头结点的左指针指向红黑树当中的最左结点，
右指针指向红黑树当中的最右结点，父指针指向红黑树的根结点。

在该结构下，实现begin()时，直接用头结点的左孩子构造一个正向迭代器即可，实现rbegin()时，直接用头结点的右孩子构造一个反向迭代器即可（实际是先用该结点构造一个正向迭代器，再用正向迭代器构造出反向迭代器），而实现end()和rend()时，直接用头结点构造出正向和反向迭代器即可。此后，通过对逻辑的控制，就可以实现end()进行–操作后得到最后一个结点的正向迭代器。

set

#pragma once #include "RBTree.h"
namespace cxq
{template<class K>//set只有一个模板参数class set{//仿函数struct SetKeyOfT{const K & operator()( const K &key){return key;}};public: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(kv); //这样写return的是pair<RBTree::iterator , bool>,所以不能这样写//库里面的写法pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key); //这个iterator是普通迭代器return pair<iterator, bool>(ret.first, ret.second);//这个iterator是const_iterator}private:RBTree<K,K,SetKeyOfT> _t;};
}

map

#pragma once 
#include"RBTree.h"
namespace cxq
{template<class K ,class V>class map{//仿函数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>::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();}V &operator[] ( const  K & key ){pair<iterator, bool > ret = insert(make_pair(key, V())); //V()-匿名对象return  ret.first->second;}pair<iterator, bool> insert(const pair<K,V > & kv){return _t.Insert(kv);}private:RBTree<K, pair<const K, V>, MapKeyOfT> _t;};
}

RBTree

#pragma once 
#include<iostream>
#include<assert.h>
#include<vector>
using namespace std;
enum Colour
{RED,BLACK
};template<class T >
struct RBTreeNode
{RBTreeNode(const T& data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;Colour _col;//颜色};template <class T,class Ptr,class Ref>
struct  _TreeIterator
{typedef RBTreeNode<T> Node;typedef _TreeIterator<T,Ptr,Ref> Self;typedef _TreeIterator<T, T*, T&> iterator;//？？_TreeIterator(const iterator & it):_node(it._node){}//构造函数 _TreeIterator(Node* node):_node(node){}Ref operator*() //T& operator*(){return _node->_data;}Ptr operator->()// T * operator->(){return &_node->_data;}bool operator!=(const Self & s){return _node != s._node;}Self& operator--()//前置-- //右子树 、根 、左子树（中序反过来） {// 左子树存在 //将当前节点的左子树中最右边的节点，就是所需要的节点if (_node->_left != nullptr){Node* subRight = _node->_left;while (subRight && subRight->_right){subRight = subRight->_right;}_node = subRight;}//右子树存在//找孩子是父亲的右的那个节点else//_node->_right != nullptr{Node* cur = _node;Node* parent = cur->_parent;while (parent!=nullptr){//向上调整 cur = parent;parent = parent->_parent;}_node = parent;		}return *this;}Self & operator++()//前置++，返回++之后的值{//右子树不为空，访问右树的最左节点//左子树不为空，如何解决？if (_node->_right != nullptr){//右树的最左节点(右树的最小节点)Node* subLeft = _node->_right;while (subLeft->_left != nullptr){subLeft = subLeft->_left;}_node = subLeft;}else//_node->_left != nulltptr{// 下一个要访问的节点，找孩子是父亲左的那个祖先节点Node* cur = _node;Node* parent = cur->_parent;while (parent!=nullptr && cur == parent->_right){//	往上更新cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}Node* _node;};template <class K, class T,class KeyOfT >
struct RBTree
{typedef RBTreeNode<T> Node;public://同一个类模板，传的不同参数，实例化不同的类型typedef _TreeIterator<T,T* ,T&> iterator;typedef _TreeIterator<T, const T* , const T &> const_iterator;//const的位置如何选择 
public:iterator begin(){//最左边即最小值节点Node* leftMin = _root;while (leftMin!=nullptr && leftMin->_left!=nullptr){leftMin = leftMin->_left;}return iterator(leftMin);//支持单参数构造支持隐式类型转换}iterator end() {return iterator(nullptr);//支持单参数构造支持隐式类型转换}const_iterator begin()const{//最左边即最小值节点Node* leftMin = _root;while (leftMin != nullptr && leftMin->_left != nullptr){leftMin = leftMin->_left;}return const_iterator(leftMin);//支持单参数构造支持隐式类型转换}const_iterator end()const{return const_iterator(nullptr);//支持单参数构造支持隐式类型转换}Node * Find(const K & key){Node* cur = _root;KeyOfT kot;while (cur!= nullptr){	if (kot(cur->_data) < key){cur = cur->_left;}else if (kot(cur->_data) > key){cur = cur->_right;}else{return cur;}}return nullptr;}pair<iterator, bool> Insert(const T & data){//找到插入位置//空树if (_root == nullptr){_root = new Node(data);_root->_col = BLACK;return make_pair(iterator(_root), true);}//不是空树 Node* cur = _root;Node* parent = nullptr;KeyOfT kot;while (cur != nullptr){//用仿函数比较 if (kot(cur->_data	) > kot(data )){parent = cur;cur = cur->_left;}else if (kot(cur->_data)  < kot(data) ){parent = cur;cur = cur->_right;}else{return make_pair(  iterator(cur) ,false);}}cur = new Node(data);cur->_col = RED;Node* newnode = cur;//将插入节点插入到树中 if (kot(parent->_data) > kot(data) ) //用仿函数 {parent->_left = cur;}else//kot(parent->_data) < kot(data){parent->_right = cur;}cur->_parent = parent;//如果插入节点的父节点是红色，分三种情况进行调整 while (parent!=nullptr &&parent->_col == RED){Node* grandfather = parent->_parent;assert(grandfather);assert(grandfather->_col == BLACK);if (parent == grandfather->_left){Node* uncle = grandfather->_right;//插入结点的叔叔存在，且颜色是红色if (uncle != nullptr && uncle->_col == RED){//parent 、uncle  变黑//grandfather变红parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//向上处理 cur = grandfather;parent = cur->_parent;}//插入结点的叔叔存在，且颜色是黑色//插入节点的叔叔不存在//这两种情况统一处理else  if (uncle != nullptr && uncle->_col == BLACK || uncle == nullptr){//先旋转再变色if (cur == parent->_left){RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else//cur == parent->_right {RotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else//parent == grandfather->_right{Node* uncle = grandfather->_left;//插入结点的叔叔存在，且颜色是红色if (uncle != nullptr && uncle->_col == RED){//parent 、uncle  变黑//grandfather变红parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;//向上处理 cur = grandfather;parent = cur->_parent;}//插入结点的叔叔存在，且颜色是黑色//插入节点的叔叔不存在//这两种情况统一处理else  if (uncle != nullptr && uncle->_col == BLACK || uncle == nullptr){//先旋转再变色if (cur == parent->_left){//双旋	RotateR(parent);RotateL(grandfather); cur->_col = BLACK;grandfather->_col = RED;}else//cur == parent->_right {RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(iterator(newnode),true);}void RotateL(Node* parent){_rotateCount++;Node* cur = parent->_right;Node* curleft = cur->_left;//parent和curleft链接parent->_right = curleft;if (curleft != nullptr){curleft->_parent = parent;}//cur和parent链接cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;//parent 是根节点if (parent == _root){cur->_parent = nullptr;_root = cur;}else//parent 是一个子树 {//parent是一个左子树if (ppnode->_left == parent){//3和ppnode链接ppnode->_left = cur;cur->_parent = ppnode;}//parent是一个右子树else{//3和ppnode链接ppnode->_right = cur;cur->_parent = ppnode;}}}void RotateR(Node* parent){_rotateCount++;Node* cur = parent->_left;Node* curright = cur->_right;//cur和parent 链接 cur->_right = parent;Node* ppnode = parent->_parent;parent->_parent = cur;//curright和parent链接 parent->_left = curright;if (curright != nullptr){curright->_parent = parent;}if (parent == _root)//parent是根节点{cur->_parent = nullptr;_root = cur;//更新根节点}else//parent一个子树 {//parent是左子树 if (ppnode->_left == parent){ppnode->_left = cur;cur->_parent = ppnode;}else//(ppnode->_right == parent)//parent是右子树 {ppnode->_right = cur;cur->_parent = ppnode;}}}bool CheckColour(Node* root, int blacknum, int benchMark){if (root == nullptr){//blacknum是一条路径上的黑色节点总数 if (blacknum != benchMark){return  false;}return false;}else if (root->_col == BLACK){blacknum++;}else if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << "连续的红节点：" << root->_kv.first << endl;return false;}return   CheckColour(root->_left, blacknum, benchMark)&& CheckColour(root->_right, blacknum, benchMark);}bool IsBalance(){return 	_IsBalance(_root);}bool _IsBalance(Node* root){if (root == nullptr){return  true;}//根节点必须是黑色if (root->_col != BLACK){return false;}//基准值//求最左路径的黑色节点int benchMark = 0;Node* cur = _root;while (cur != nullptr){if (cur->_col == BLACK){benchMark++;}cur = cur->_left;}return CheckColour(root, 0, benchMark);}int Height(){return _Height(_root);}int _Height(Node *root){if (root == nullptr){return 0;}int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return  leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}
private:Node* _root = nullptr;
public:int _rotateCount = 0;
};