建设电影网站数据库脚本,wordpress 官网主题,云南手工活外发加工网,网店推广分为哪几种类型目录 1、map和set的整体框架
2、map和set迭代器的实现
3、map支持[]
4、完整源码
set.h
map.h
RBTree.h 1、map和set的整体框架
因为map和set的底层都是红黑树#xff0c;所以我们考虑用一个红黑树的类模版去实例化map和set对象#xff01;不过#xff0c;map节点中存…目录 1、map和set的整体框架
2、map和set迭代器的实现
3、map支持[]
4、完整源码
set.h
map.h
RBTree.h 1、map和set的整体框架
因为map和set的底层都是红黑树所以我们考虑用一个红黑树的类模版去实例化map和set对象不过map节点中存储的是一个pair对象而set中存储的是一个key对象。所以我们第一步就是先调整一下我们之前实现的红黑树的节点结构。
//节点结构不知道存储pair类型的key/val结构还是Key结构
templateclass T
struct RBTreeNode
{RBTreeNode(const T data):_data(data), _parent(nullptr), _left(nullptr), _right(nullptr), _col(RED){}T _data;RBTreeNode* _parent;RBTreeNode* _left;RBTreeNode* _right;Colour _col;//初始化为红色
};
无论是set还是map的查找都是根据key来进行的所以我们的红黑树类模版的第一个参数类型是接受上层传递过来的K类型。
再有set和map的insert插入一个是pair类型一个是key类型。所以我们的红黑树类模版的第二个参数类型是接受上层传递过来的T类型。
最后我们还要在上层传递一个仿函数用于底层红黑树查找和插入删除时用key比较。因为set直接插入一个key可以用于比较但是map插入一个pair而pair支持的比较是first和second一起比较而我们只希望用key比较。又因为底层并不知道上层是set还是map所以我们要在上层传递一个仿函数给到下层让下层用上层的仿函数拿到key来比较大小
set整体框架
namespace my_set
{templateclass Kclass set{//仿函数用于底层红黑树查找和插入删除时用key比较struct SetKeyOfT{const K operator()(const K key){return key;}};public:bool insert(const K key){return _t.insert(key);}private:RBTreeK, K, SetKeyOfT _t;};
}
map整体框架
namespace my_map
{templateclass K,class Vclass map{/*仿函数用于底层红黑树查找和插入删除时用key比较因为set直接插入一个key可以用于比较但是map插入一个pair而pair支持的比较是first和second一起比较而我们只希望用key比较又底层并不知道上层是set还是map所以我们要在上层传递一个仿函数给到下层让下层用上层的仿函数拿到key来比较大小*/struct MapKeyOfT{const K operator()(const pairK,V kv){return kv.first;}};public:bool insert(const pairK,V kv){return _t.insert(kv);}private:RBTreeK, pairK,V, MapKeyOfT _t;};
}
调整过后的底层红黑树
//枚举类型定义颜色
enum Colour
{RED,BLACK
};
//节点结构不知道存储pair类型的key/val结构还是Key结构
templateclass T
struct RBTreeNode
{RBTreeNode(const T data):_data(data), _parent(nullptr), _left(nullptr), _right(nullptr), _col(RED){}T _data;RBTreeNode* _parent;RBTreeNode* _left;RBTreeNode* _right;Colour _col;//初始化为红色
};//红黑树
templateclass K, class T,class KeyOfT
class RBTree
{typedef RBTreeNodeT Node;
public:KeyOfT kot;//默认构造RBTree() default;//拷贝构造RBTree(const T rbt){_root _copy(rbt._root);}// 赋值重载RBTreeK, T,KeyOfT operator(T tmp){std::swap(_root, tmp._root);return *this;}//二叉树的析构~RBTree(){_Destroy(_root);}//红黑树的查找Node* Find(const K key){Node* cur _root;while (cur){if (kot(cur-_data) kot(key)){cur cur-_right;}else if (kot(cur-_data) kot(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;while (cur){if (kot(data) kot(cur-_data))//小往左走{parent cur;cur parent-_left;}else if (kot(data) kot(cur-_data))//大往右走{parent cur;cur parent-_right;}else{return false;//不支持相同元素的插入}}cur new Node(data);cur-_col RED;if (kot(data) kot(parent-_data))//K小插入在左边parent-_left cur;else//K大插入在右边parent-_right cur;cur-_parent parent;//插入后进行维护红黑树规则的逻辑//parent存在且为红while (parent parent-_col RED){Node* grandfather parent-_parent;//p在g的右边if (parent grandfather-_right){//g//u pNode* uncle grandfather-_left;if (uncle uncle-_col RED)//uncle存在且为红{//变色处理uncle-_col parent-_col BLACK;grandfather-_col RED;//更新cur继续向上处理cur grandfather;parent cur-_parent;}else//uncle不存在或者存在且为黑{if (cur parent-_right){//g//u p// c//以g为旋转点进行左单旋RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{//g//u p// c//进行右左双旋RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}//旋转变色后链接祖先节点的节点为黑必然不会发生连续红色节点的情况直接break;break;}}else//p在g的左边{//g//p uNode* uncle grandfather-_right;if (uncle uncle-_col RED)//uncle存在且为红{//变色处理uncle-_col parent-_col BLACK;grandfather-_col RED;//更新cur继续向上处理cur grandfather;parent cur-_parent;}else//uncle不存在或者存在且为黑{if (cur parent-_left){//g//p u//c//以g为旋转点进行右单旋RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{//g//p u// c//进行左右双旋RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}//旋转变色后链接祖先节点的节点为黑必然不会发生连续红色节点的情况直接break;break;}}}//如果持续更新变色到根_root-_col BLACK;return true;}private://右单旋void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;Node* pParent parent-_parent;parent-_left subLR;if (subLR)//如果不为空subLR-_parent parent;subL-_right parent;parent-_parent subL;if (pParent nullptr){_root subL;subL-_parent nullptr;}else{if (pParent-_left parent){pParent-_left subL;}else{pParent-_right subL;}subL-_parent pParent;}}//左单旋void RotateL(Node* parent){Node* pParent parent-_parent;Node* subR parent-_right;Node* subRL subR-_left;subR-_left parent;parent-_parent subR;parent-_right subRL;if (subRL)subRL-_parent parent;if (pParent nullptr){_root subR;subR-_parent nullptr;}else{if (pParent-_left parent){pParent-_left subR;}else{pParent-_right subR;}subR-_parent pParent;}}//递归拷贝Node* _copy(Node* root){if (root nullptr)return nullptr;Node* newNode new Node(root-_data);newNode-_left _copy(root-_left);newNode-_right _copy(root-_right);return newNode;}//二叉树的销毁void _Destroy(Node* root){if (root nullptr)return;_Destroy(root-_left);_Destroy(root-_right);delete root;}private:Node* _root nullptr;
};
2、map和set迭代器的实现
map和set迭代器的实现其实思路与list迭代器的实现几乎一样它们都是由一个一个的节点组成的。所以我们都是通过封装一个节点的指针重载*、-、、--、比较等运算符
迭代器的整体框架
//封装一个节点指针作为迭代器
templateclass T,class Ref,class Ptr
struct RBTreeIterator
{typedef RBTreeNodeT Node;typedef RBTreeIteratorT,Ref,Ptr Self;Node* _node;Node* _root;RBTreeIterator(Node* node,Node* root):_node(node),_root(root){}//迭代器的Self operator(){}//迭代器的--Self operator--(){}//简单的运算符重载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;}
}; map和set迭代器的难点在于和--
iterator实现思路分析
• iterator实现的⼤框架跟list的iterator思路是⼀致的⽤⼀个类型封装结点的指针再通过重载运算 符实现迭代器像指针⼀样访问的⾏为。
• 这⾥的难点是operator和operator--的实现。之前使⽤部分我们分析了map和set的迭代器⾛ 的是中序遍历左⼦树-根结点-右⼦树那么begin()会返回中序第⼀个结点的iterator也就是10 所在结点的迭代器。
• 迭代器的核⼼逻辑就是不看全局只看局部只考虑当前中序局部要访问的下⼀个结点。
• 迭代器时如果it指向的结点的右⼦树不为空代表当前结点已经访问完了要访问下⼀个结点 是右⼦树的中序第⼀个⼀棵树中序第⼀个是最左结点所以直接找右⼦树的最左结点即可。
• 迭代器时如果it指向的结点的右⼦树空代表当前结点已经访问完了且当前结点所在的⼦树也 访问完了要访问的下⼀个结点在当前结点的祖先⾥⾯所以要沿着当前结点到根的祖先路径向上 找。
• 如果当前结点是⽗亲的左根据中序左⼦树-根结点-右⼦树那么下⼀个访问的结点就是当前结 点的⽗亲
如下图it指向2525右为空25是30的左所以下⼀个访问的结点就是30。
• 如果当前结点是⽗亲的右根据中序左⼦树-根结点-右⼦树当前当前结点所在的⼦树访问完 了当前结点所在⽗亲的⼦树也访问完了那么下⼀个访问的需要继续往根的祖先中去找直到找 到孩⼦是⽗亲左的那个祖先就是中序要问题的下⼀个结点。
如下图it指向1515右为空15是10 的右15所在⼦树话访问完了10所在⼦树也访问完了继续往上找10是18的左那么下⼀个 访问的结点就是18。
• 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即可 RBTreeconst K, SetKeyOfT _t;
• map的iterator不⽀持修改key但是可以修改value我们把map的第⼆个模板参数pair的第⼀个参 数改成const K即可 RBTreepair, MapKeyOfT _t;
• ⽀持完整的迭代器还有很多细节需要修改具体参考下⾯题的代码。 迭代器代码
//迭代器的
Self operator()
{//如果当前节点的右不为空那下一个节点就是右子树的最左节点if (_node-_right){Node* leftMost _node-_right;while (leftMost-_left){leftMost leftMost-_left;}_node leftMost;}/*如果当前节点的右为空则说明当前节点的中序已近完毕如果当前节点是父亲的右说明父亲的中序也完毕所以我们要找到祖先节点中是父亲的左的那个节点那下一个节点就是就是父亲*/else{Node* cur _node;Node* parent cur-_parent;//父亲不为空并且cur是父亲的右不断向上寻找while (parent cur parent-_right){cur parent;parent cur-_parent;}//走到这里父亲为空说明走到end不为空父亲则是中序的下一个_node parent;}return *this;
}
因为我们用空来代表数的末尾但我们--时如果此时迭代器恰好在end()位置那我们就要单独考虑这种情况。其他逻辑就和相反
要找到树的最右节点那么就还必须知道根节点_root所以我们在红黑树中构造一个迭代器时不仅要传递当前位置的节点还要传根节点
//迭代器的--
Self operator--()
{//--后为中序的最右那一个if (_node nullptr){Node* rightMost _root;while (rightMostrightMost-_right){rightMost rightMost-_right;}_node rightMost;}//如果当前节点的左不为空那下一个节点就是左子树的最右节点else if (_node-_left){Node* rightMost _node-_left;while (rightMost-_right){rightMost rightMost-_right;}_node rightMost;}/*如果当前节点的左为空则说明当前节点的中序已近完毕如果当前节点是父亲的左说明父亲的中序也完毕所以我们要找到祖先节点中是父亲的右的那个节点那下一个节点就是就是父亲*/else{Node* cur _node;Node* parent cur-_parent;//父亲不为空并且cur是父亲的左不断向上寻找while (parent cur parent-_left){cur parent;parent cur-_parent;}//走到这里父亲为空说明走到end不为空父亲则是中序的下一个_node parent;}return *this;
}
底层红黑树的begin和end
typedef RBTreeNodeT Node;
typedef RBTreeIteratorT, T, T* Iterator;
typedef RBTreeIteratorT, const T, const T* ConstIterator;
Iterator Begin()
{Node* leftMost _root;while (leftMost leftMost-_left){leftMost leftMost-_left;}return Iterator(leftMost, _root);
}
Iterator End()
{return Iterator(nullptr, _root);
}
ConstIterator CBegin() const
{Node* leftMost _root;while (leftMost leftMost-_left){leftMost leftMost-_left;}return Iterator(leftMost, _root);
}
ConstIterator CEnd() const
{return Iterator(nullptr, _root);
}
3、map支持[]
map的[]重载主要是复用了底层红黑树当中的insert接口insert充当查找和插入的功能
我们在使用[]时如果map中有和我们外面传递的key相同的key那insert就会插入失败并且返回这个key的迭代器。如果不存在那insert就会插入成功并且返回这个key的迭代器。所以我们要调整一下insert的返回值为pairiterator,bool
而map的[]还支持修改key所映射的val的功能insert返回的迭代器在修改val时发挥作用
V operator[](const K key)
{pairiterator, bool ret _t.Insert(make_pair(key, V()));return ret.first-second;
}
4、完整源码
set.h
#pragma once
#includeRBTree.h
namespace my_set
{templateclass Kclass set{//仿函数用于底层红黑树查找和插入删除时用key比较struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename RBTreeK, const K, SetKeyOfT::Iterator iterator;typedef typename RBTreeK, const K, SetKeyOfT::ConstIterator const_iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}const_iterator cbegin() const{return _t.CBegin();}const_iterator cend() const{return _t.CEnd();}pairiterator,bool insert(const K key){return _t.Insert(key);}iterator find(const K key){return _t.Find(key);}private:RBTreeK, const K, SetKeyOfT _t;};
}
map.h
#pragma once
#includeRBTree.h
namespace my_map
{templateclass K,class Vclass map{/*仿函数用于底层红黑树查找和插入删除时用key比较因为set直接插入一个key可以用于比较但是map插入一个pair而pair支持的比较是first和second一起比较而我们只希望用key比较又底层并不知道上层是set还是map所以我们要在上层传递一个仿函数给到下层让下层用上层的仿函数拿到key来比较大小*/struct MapKeyOfT{const K operator()(const pairK,V kv){return kv.first;}};public:typedef typename RBTreeK, pairconst K, V, MapKeyOfT::Iterator iterator;typedef typename RBTreeK, pairconst K, V, MapKeyOfT::ConstIterator const_iterator;iterator begin(){return _t.Begin();}iterator end(){return _t.End();}const_iterator cbegin() const{return _t.CBegin();}const_iterator cend() const{return _t.CEnd();}pairiterator, bool insert(const pairK,V kv){return _t.Insert(kv);}iterator find(const K key){return _t.Find(key);}V operator[](const K key){pairiterator, bool ret _t.Insert(make_pair(key, V()));return ret.first-second;}private:RBTreeK, pairconst K,V, MapKeyOfT _t;};
}
RBTree.h #pragma once
#includeiostream
using namespace std;//枚举类型定义颜色
enum Colour
{RED,BLACK
};//节点结构不知道存储pair类型的key/val结构还是Key结构
templateclass T
struct RBTreeNode
{RBTreeNode(const T data):_data(data), _parent(nullptr), _left(nullptr), _right(nullptr), _col(RED){}T _data;RBTreeNode* _parent;RBTreeNode* _left;RBTreeNode* _right;Colour _col;//初始化为红色
};//封装一个节点指针作为迭代器
templateclass T,class Ref,class Ptr
struct RBTreeIterator
{typedef RBTreeNodeT Node;typedef RBTreeIteratorT,Ref,Ptr Self;Node* _node;Node* _root;RBTreeIterator(Node* node,Node* root):_node(node),_root(root){}//迭代器的Self operator(){//如果当前节点的右不为空那下一个节点就是右子树的最左节点if (_node-_right){Node* leftMost _node-_right;while (leftMost-_left){leftMost leftMost-_left;}_node leftMost;}/*如果当前节点的右为空则说明当前节点的中序已近完毕如果当前节点是父亲的右说明父亲的中序也完毕所以我们要找到祖先节点中是父亲的左的那个节点那下一个节点就是就是父亲*/else{Node* cur _node;Node* parent cur-_parent;//父亲不为空并且cur是父亲的右不断向上寻找while (parent cur parent-_right){cur parent;parent cur-_parent;}//走到这里父亲为空说明走到end不为空父亲则是中序的下一个_node parent;}return *this;}//迭代器的--Self operator--(){//--后为中序的最右那一个if (_node nullptr){Node* rightMost _root;while (rightMostrightMost-_right){rightMost rightMost-_right;}_node rightMost;}//如果当前节点的左不为空那下一个节点就是左子树的最右节点else if (_node-_left){Node* rightMost _node-_left;while (rightMost-_right){rightMost rightMost-_right;}_node rightMost;}/*如果当前节点的左为空则说明当前节点的中序已近完毕如果当前节点是父亲的左说明父亲的中序也完毕所以我们要找到祖先节点中是父亲的右的那个节点那下一个节点就是就是父亲*/else{Node* cur _node;Node* parent cur-_parent;//父亲不为空并且cur是父亲的左不断向上寻找while (parent cur parent-_left){cur parent;parent cur-_parent;}//走到这里父亲为空说明走到end不为空父亲则是中序的下一个_node parent;}return *this;}//简单的运算符重载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;}
};//红黑树
templateclass K, class T,class KeyOfT
class RBTree
{
public:typedef RBTreeNodeT Node;typedef RBTreeIteratorT, T, T* Iterator;typedef RBTreeIteratorT, const T, const T* ConstIterator;Iterator Begin(){Node* leftMost _root;while (leftMost leftMost-_left){leftMost leftMost-_left;}return Iterator(leftMost, _root);}Iterator End(){return Iterator(nullptr, _root);}ConstIterator CBegin() const{Node* leftMost _root;while (leftMost leftMost-_left){leftMost leftMost-_left;}return Iterator(leftMost, _root);}ConstIterator CEnd() const{return Iterator(nullptr, _root);}KeyOfT kot;//默认构造RBTree() default;//拷贝构造RBTree(const T rbt){_root _copy(rbt._root);}// 赋值重载RBTreeK, T,KeyOfT operator(T tmp){std::swap(_root, tmp._root);return *this;}//二叉树的析构~RBTree(){_Destroy(_root);}//红黑树的查找Node* Find(const K key){Node* cur _root;while (cur){if (kot(cur-_data) kot(key)){cur cur-_right;}else if (kot(cur-_data) kot(key)){cur cur-_left;}else{return Iterator(cur,_root);}}return End();}//红黑树的插入pairIterator,bool Insert(const T data){//如果树为空在根插入并且颜色为黑色if (_root nullptr){_root new Node(data);_root-_col BLACK;return make_pair(Iterator(_root,_root),true);}//树不为空按搜索树规则先进行插入Node* parent nullptr;Node* cur _root;while (cur){if (kot(data) kot(cur-_data))//小往左走{parent cur;cur parent-_left;}else if (kot(data) kot(cur-_data))//大往右走{parent cur;cur parent-_right;}else{return make_pair(Iterator(cur, _root), false);//不支持相同元素的插入}}cur new Node(data);Node* newnode cur;cur-_col RED;if (kot(data) kot(parent-_data))//K小插入在左边parent-_left cur;else//K大插入在右边parent-_right cur;cur-_parent parent;//插入后进行维护红黑树规则的逻辑//parent存在且为红while (parent parent-_col RED){Node* grandfather parent-_parent;//p在g的右边if (parent grandfather-_right){//g//u pNode* uncle grandfather-_left;if (uncle uncle-_col RED)//uncle存在且为红{//变色处理uncle-_col parent-_col BLACK;grandfather-_col RED;//更新cur继续向上处理cur grandfather;parent cur-_parent;}else//uncle不存在或者存在且为黑{if (cur parent-_right){//g//u p// c//以g为旋转点进行左单旋RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{//g//u p// c//进行右左双旋RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}//旋转变色后链接祖先节点的节点为黑必然不会发生连续红色节点的情况直接break;break;}}else//p在g的左边{//g//p uNode* uncle grandfather-_right;if (uncle uncle-_col RED)//uncle存在且为红{//变色处理uncle-_col parent-_col BLACK;grandfather-_col RED;//更新cur继续向上处理cur grandfather;parent cur-_parent;}else//uncle不存在或者存在且为黑{if (cur parent-_left){//g//p u//c//以g为旋转点进行右单旋RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{//g//p u// c//进行左右双旋RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}//旋转变色后链接祖先节点的节点为黑必然不会发生连续红色节点的情况直接break;break;}}}//如果持续更新变色到根_root-_col BLACK;return make_pair(Iterator(newnode, _root), true);}private://右单旋void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;Node* pParent parent-_parent;parent-_left subLR;if (subLR)//如果不为空subLR-_parent parent;subL-_right parent;parent-_parent subL;if (pParent nullptr){_root subL;subL-_parent nullptr;}else{if (pParent-_left parent){pParent-_left subL;}else{pParent-_right subL;}subL-_parent pParent;}}//左单旋void RotateL(Node* parent){Node* pParent parent-_parent;Node* subR parent-_right;Node* subRL subR-_left;subR-_left parent;parent-_parent subR;parent-_right subRL;if (subRL)subRL-_parent parent;if (pParent nullptr){_root subR;subR-_parent nullptr;}else{if (pParent-_left parent){pParent-_left subR;}else{pParent-_right subR;}subR-_parent pParent;}}//递归拷贝Node* _copy(Node* root){if (root nullptr)return nullptr;Node* newNode new Node(root-_data);newNode-_left _copy(root-_left);newNode-_right _copy(root-_right);return newNode;}//二叉树的销毁void _Destroy(Node* root){if (root nullptr)return;_Destroy(root-_left);_Destroy(root-_right);delete root;}
private:Node* _root nullptr;
};
