set和map的封装

目录

介绍

红黑树代码 

set

insert的迭代器转换问题

为什么会有这样的问题?

如何解决

代码 

map

注意点

代码

---

介绍

set和map的底层都是红黑树,所以我们可以在自己实现的红黑树(简易版)的基础上,进行封装,成为简易的set和map

红黑树代码 

#pragma once#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <cassert>
#include <cstdlib>
#include <utility>// 有迭代器的红黑树
namespace my_RB_Tree
{enum colour{black,red};template <class T>struct RBTreeNode // 结点{RBTreeNode(const T& data): _left(nullptr),_right(nullptr),_parent(nullptr),_col(red),_data(data){}RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;colour _col;T _data;};template <class T, class Ptr, class Ref> // T是元素类型,ptr是指针类型,ref是引用类型(后两种会有const类型)struct RBTreeIterator                    // 迭代器{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ptr, Ref> Self;//为了可以能让普通迭代器初始化const迭代器,需要来一个普通迭代器对象typedef RBTreeIterator<T, T*, T&> iterator;Node* _pNode;RBTreeIterator(Node* pNode): _pNode(pNode){}RBTreeIterator(const iterator& it) // const迭代器时,它是一个初始化;普通迭代器时,它是一个拷贝: _pNode(it._pNode){}// 让迭代器具有类似指针的行为Ref operator*(){return _pNode->_data;}Ptr operator->(){return &(_pNode->_data);}// 让迭代器可以移动：前置/后置++Self& operator++(){Increament();return *this;}Self operator++(int){Self tmp(*this);Increament();return tmp;}// 让迭代器可以移动：前置/后置--Self& operator--(){DeIncreament();return *this;}Self operator--(int){Self tmp(*this);DeIncreament();return tmp;}// 让迭代器可以比较bool operator!=(const Self& s) const{return _pNode != s._pNode;}bool operator==(const Self& s) const{return _pNode == s._pNode;}private:void Increament();void DeIncreament();};// 为了后序封装map和set，本代码的红黑树会有一个作为哨兵位的头结点template <class K, class T, class KeyOfT> // K是关键字的类型,T是元素类型(区分这两个的原因:会用该红黑树封装成set和map,而map是key_value的)// keyofT是返回关键字类型的值(否则map无法返回)class RBTree                              // 红黑树{public:typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, T*, T&> iterator;typedef RBTreeIterator<T, const T*, const T&> const_iterator;public:RBTree(){_pHead = new Node(T());_pHead->_left = _pHead;_pHead->_parent = nullptr;_pHead->_right = _pHead;}// 在红黑树中插入值为data的节点，插入成功返回true，否则返回falsestd::pair<iterator, bool> Insert(const T& data);// 检测红黑树中是否存在值为data的节点，存在返回该节点的地址，否则返回nullptrNode* Find(const K& data);// 获取红黑树最左侧节点Node* LeftMost() const;// 获取红黑树最右侧节点Node* RightMost() const;iterator begin(){return iterator(LeftMost());}iterator end(){return iterator(_pHead);}const_iterator begin() const{return const_iterator(LeftMost());}const_iterator end() const{return const_iterator(_pHead);}// 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测bool IsValidRBTRee(){Node* root = _pHead->_parent;if (root->_col == red){return false;}int count = 0;find_blacknode(count, _pHead->_parent);return _IsValidRBTRee(_pHead->_parent, count, 0);}private:bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack);// 左单旋void RotateL(Node* pParent);// 右单旋void RotateR(Node* pParent);// 为了操作树简单起见：获取根节点Node*& GetRoot(){return _pHead->_parent;}void find_blacknode(int& count, Node* root){if (root == nullptr){return;}if (root->_col == black){++count;}find_blacknode(count, root->_left);find_blacknode(count, root->_right);}private:Node* _pHead = nullptr;};template <class K, class T, class KeyOfT>void RBTree<K, T, KeyOfT>::RotateL(Node* pParent){Node* cur = pParent->_right, * curleft = cur->_left;// 连接p和cur左树,因为该位置被p占据pParent->_right = curleft;if (curleft){curleft->_parent = pParent;}// 连接父结点if (pParent->_parent != _pHead){Node* ppnode = pParent->_parent;if (ppnode->_left == pParent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}else{_pHead->_parent = cur;cur->_parent = _pHead;}// 连接p和curpParent->_parent = cur;cur->_left = pParent;}template <class K, class T, class KeyOfT>void RBTree<K, T, KeyOfT>::RotateR(Node* pParent){Node* cur = pParent->_left, * curright = cur->_right;// 连接p和cur右树,因为该位置被p占据pParent->_left = curright;if (curright){curright->_parent = pParent;}// 连接父结点if (pParent->_parent != _pHead){Node* ppnode = pParent->_parent;if (ppnode->_left == pParent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}else{_pHead->_parent = cur;cur->_parent = _pHead;}// 连接p和curpParent->_parent = cur;cur->_right = pParent;}template <class K, class T, class KeyOfT>typename RBTree<K, T, KeyOfT>::Node* RBTree<K, T, KeyOfT>::LeftMost() const{Node* cur = _pHead->_parent;while (cur->_left){cur = cur->_left;}return cur;}template <class K, class T, class KeyOfT>typename RBTree<K, T, KeyOfT>::Node* RBTree<K, T, KeyOfT>::RightMost() const{Node* cur = _pHead->_parent;while (cur->_right){cur = cur->_right;}return cur;}template <class K, class T, class KeyOfT>typename RBTree<K, T, KeyOfT>::Node* RBTree<K, T, KeyOfT>::Find(const K& data) // 注意这里,{Node* cur = _pHead->_parent;KeyOfT kot;while (cur){if (data > kot(cur->_data)){cur = cur->_right;}else if (data < kot(cur->_data)){cur = cur->_left;}else{return cur;}}return nullptr;}template <class K, class T, class KeyOfT>std::pair<typename RBTree<K, T, KeyOfT>::iterator, bool> RBTree<K, T, KeyOfT>::Insert(const T& data) // 为了和map适配,要返回pair类型//(first是插入元素所在的迭代器,second是bool值,判断是否成功插入){KeyOfT kot;Node* newnode = nullptr;if (_pHead->_parent == nullptr){newnode = new Node(data);newnode->_col = black;_pHead->_parent = newnode;newnode->_parent = _pHead;return std::make_pair(iterator(newnode), true);}else{Node* cur = _pHead->_parent, * parent = cur;while (cur){if (kot(data) > kot(cur->_data)){parent = cur;cur = cur->_right;}else if (kot(data) < kot(cur->_data)){parent = cur;cur = cur->_left;}else{return std::make_pair((iterator)cur, false);}}newnode = new Node(data);cur = newnode;cur->_parent = parent;if (kot(parent->_data) > kot(cur->_data)){parent->_left = cur;}else{parent->_right = cur;}Node* grandfather = nullptr;while (parent != _pHead && parent->_col == red){grandfather = parent->_parent; // 因为父结点是红色,所以肯定有爷爷结点(注意红黑树规则:根结点必须是黑色)if (grandfather->_left == parent) // 确定父亲位置{Node* uncle = grandfather->_right; // 也就能确定叔叔位置if (uncle && uncle->_col == red){parent->_col = uncle->_col = black;grandfather->_col = red;}else // 如果uncle不存在/为黑,就需要旋转+变色了{// 需要先判断旋转类型(也就是判断 -- parent和cur的相对位置)if (parent->_left == cur){// 一条偏右的直线,需要右旋RotateR(grandfather);// 旋转完后parent成为根结点// 更改完结点指向后,就可以改颜色了(都是根结点为黑,另外两个为红)parent->_col = black;cur->_col = grandfather->_col = red; // 和cur一层}else{// 拐角在左边,也就是先左旋,再右旋RotateL(parent);RotateR(grandfather);// cur成为根结点// 改颜色cur->_col = black;parent->_col = grandfather->_col = red;}break;}}else // parent在grandfather的右树{Node* uncle = grandfather->_left;if (uncle && uncle->_col == red){parent->_col = uncle->_col = black;grandfather->_col = red;}else // 如果uncle不存在/为黑,就需要旋转+变色了{// 需要先判断旋转类型(也就是判断 -- parent和cur的相对位置)if (parent->_right == cur){// 一条偏左的直线,需要左旋RotateL(grandfather);parent->_col = black;cur->_col = grandfather->_col = red; // 和cur一层}else{// 拐角在右边,也就是先右旋,再左旋RotateR(parent);RotateL(grandfather);// 改颜色cur->_col = black;parent->_col = grandfather->_col = red;}break;}}cur = grandfather; // 注意,这里会改cur的指向,但返回值需要返回插入位置的迭代器,所以需要另外保存parent = cur->_parent;}(_pHead->_parent)->_col = black; // 根结点必须为黑(防止它在上面的循环中被修改)}_pHead->_left = LeftMost();_pHead->_right = RightMost();//std::cout << (_pHead->_left)->_data << " " << (_pHead->_right)->_data << std::endl;return std::make_pair(iterator(newnode), true);}template <class K, class T, class KeyOfT>bool RBTree<K, T, KeyOfT>::_IsValidRBTRee(Node* cur, size_t blackCount, size_t pathBlack){if (cur == nullptr){// 到空结点后,就说明一条路径已经走通了,可以用得到的黑色结点数与基准数对比,不一样就说明红黑树错误if (pathBlack != blackCount){return false;}else{return true;}}if (cur->_parent){Node* ppnode = cur->_parent;if (cur->_col == red && ppnode->_col == red){return false;}}if (cur->_col == black){++pathBlack;}return _IsValidRBTRee(cur->_left, blackCount, pathBlack) && _IsValidRBTRee(cur->_right, blackCount, pathBlack);}template <class T, class Ptr, class Ref>void RBTreeIterator<T, Ptr, Ref>::Increament(){Node* cur = _pNode, * parent = _pNode->_parent;if (cur->_right){// 找到右子树的最小结点Node* curright = cur->_right;while (curright->_left){curright = curright->_left;}_pNode = curright;}else{while (parent->_parent != cur && parent->_right == cur) // 找到cur是parent的左结点的位置,这样parent的位置就是下一个位置{cur = parent;parent = parent->_parent;}_pNode = parent;}}template <class T, class Ptr, class Ref>void RBTreeIterator<T, Ptr, Ref>::DeIncreament(){Node* cur = _pNode, * parent = _pNode->_parent;if (cur->_left){// 找到左子树的最大结点Node* curleft = cur->_left;while (curleft->_right){curleft = curleft->_right;}_pNode = curleft;}else{while (parent->_parent != cur && parent->_left == cur) // 找到cur是parent的左结点的位置,这样parent的位置就是下一个位置{cur = parent;parent = parent->_parent;}_pNode = parent;}}
}

set

set我们只实现它的插入和迭代器部分,大概可以看到效果就行

insert的迭代器转换问题

不考虑别的,因为insert返回的都是pair类型的,都是迭代器+布尔值,所以set直接调用红黑树的插入即可

但是,编译过不去!

大概就是说,普通迭代器无法转换为const迭代器

为什么会有这样的问题?

注意,set中,无论是普通迭代器还是const迭代器,其实都封装的是红黑树的const迭代器

stl源码中就是这么定义的:

• 但是,tree的insert返回的是普通迭代器,而set的insert要返回的是const迭代器
• 这就存在一个普通迭代器向const迭代器转换的过程

如何解决

所以我们需要在红黑树的迭代器类中增加这一功能

typedef RBTreeNode<T> Node;
typedef RBTreeIterator<T, Ptr, Ref> Self;
//为了可以能让普通迭代器初始化const迭代器,需要来一个普通迭代器对象
typedef RBTreeIterator<T, T*, T&> iterator;
Node* _pNode;RBTreeIterator(Node* pNode): _pNode(pNode)
{}
RBTreeIterator(const iterator& it) // const迭代器时,它是一个初始化;普通迭代器时,它是一个拷贝: _pNode(it._pNode)
{}

代码 

#include "RB_Tree.hpp"namespace my_set
{template <class K>class set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename my_RB_Tree::RBTree<K, K, SetKeyOfT>::const_iterator iterator;typedef typename my_RB_Tree::RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;const_iterator begin() const{return _t.begin();}const_iterator end() const{return _t.end();}std::pair<iterator, bool> insert(const K& data) {//return _t.Insert(data);//这里在构建时,set的insert调用tree的insert//而tree中insert的返回值,返回的pair中,第一个成员是tree的普通迭代器//然后回到该函数,该函数返回的pair的第一个成员是set中的普通迭代器(实质上是tree中的const迭代器)//所以我们本质上是用不同类型的pair在赋值//所以要先转换std::pair<typename my_RB_Tree::RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(data); //这里是tree的普通迭代器iterator it(ret.first);return std::pair<iterator, bool>(it,ret.second); //这里是要用普通迭代器初始化一个const迭代器,所以需要在tree迭代器中增加这个功能}private:my_RB_Tree::RBTree<K, K, SetKeyOfT> _t;};
}

map

注意点

map的重点就在insert和[ ]的重载上

也没啥别的了,就需要自己先构建一个pair类型,其他的就注意返回值和接收值到底是谁

K:key值类型    V:value类型     T:map的元素类型

代码

#include "RB_Tree.hpp"namespace my_map
{template <class K, class V>class map{public:typedef std::pair<const K, V> T; // map中key不能变，value可以变struct MapKeyOfT{const V &operator()(const T &data){return data.second;}};typedef typename my_RB_Tree::RBTree<K, T, MapKeyOfT>::iterator iterator;typedef typename my_RB_Tree::RBTree<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();}std::pair<iterator, bool> insert(const T &data){return _t.Insert(data);}V &operator[](const K &data){auto ret = insert(std::make_pair(data,V()));return (ret.first)->second;}private:my_RB_Tree::RBTree<K, T, MapKeyOfT> _t;};
}