网站建设对电子商务的作用,怎样安装免费的wordpress,适合女生的十大热门专业,女生做网站运营目录
一、set/map的底层结构
1、set/map的源码
2、利用模板区分set/map
3、利用仿函数控制比较大小
二、set/map的迭代器#xff08;红黑树的迭代器#xff09;
1、红黑树的begin、end迭代器
2、红黑树迭代器的operator
3、红黑树迭代器的operator--
三、set的const… 目录
一、set/map的底层结构
1、set/map的源码
2、利用模板区分set/map
3、利用仿函数控制比较大小
二、set/map的迭代器红黑树的迭代器
1、红黑树的begin、end迭代器
2、红黑树迭代器的operator
3、红黑树迭代器的operator--
三、set的const迭代器
四、map的const迭代器
五、迭代器类的拷贝构造
六、整体代码
1、RBTree.h
2、Set.h
3、map.h 本文相关往期内容可按需查阅 1、【C】set/multiset、map/multimap的使用
2、【数据结构】二叉搜索树的实现
3、【数据结构】平衡二叉树
4、【数据结构】手撕红黑树
本文难点使用红黑树封装set和map必须保证两种数据结构复用同一棵红黑树且满足set和map的性质set的value不可被改变而map的value可以被改变。
一、set/map的底层结构
1、set/map的源码 扒一扒STL库中set和map的底层结构不难发现set和map的底层用的都是红黑树且均为key/value模型。
只不过set的key/value均为key值填充而map的key/value使用key和pairconst Key,T进行填充。因此set和map中底层虽然都是红黑树但这两种数据结构中的红黑树实例化类型并不相同。
那么使用同一颗红黑树的模板如何实例化出适配set和/map的对象
2、利用模板区分set/map
template class T//T类型代表value
struct RBTreeNode
{RBTreeNode(const T data):_parent(nullptr), _left(nullptr), _right(nullptr), _data(data), _col(RED){}RBTreeNodeT* _parent;RBTreeNodeT* _left;RBTreeNodeT* _right;T _data;Color _col;
}; map和set的区别在于value的不同红黑树模板参数T代表value用以区分set和map。
3、利用仿函数控制比较大小 我们会发现红黑树的插入等接口会对key值进行比较大小像set直接对key进行比较这没问题但是map中的节点装的是pairK,V,pair的比较规则是first比完之后可能会再去比较second而我们仅仅想要比较first该比较规则不适用。
通过源码启发我们可以对红黑树新增一个模板参数仿函数KeyOfT在set和map类中完善该仿函数的比较对象用于区分set和map的比较
template class K
class set
{//仿函数用于比较大小struct SetKeyOfT{const K operator()(const K key)//传入节点的值{return key;//返回key}};
private:RBTreeK, K, SetKeyOfT _t;
};
class map
{struct MapKeyOfT{const K operator()(const pairK, V kv)//传入节点的值{return kv.first;//返回kv.first}};
private:RBTreeconst K, pairK,V, MapKeyOfT _t;
};
//利用模板确定传入对象是set还是map
template class K, class T,class KeyOfT
class RBTree//红黑树
{}; 利用仿函数传入节点的值set将会返回key值map将会的返回pair的first。这样就解决了比较大小的规则问题。 二、set/map的迭代器红黑树的迭代器
因为红黑树的中序遍历是有序的可以根据中序遍历作为迭代器--的依据。
STL源码采用下图结构多搞了一个头结点。迭代器begin()可以指向header的左迭代器end()指向header。 不过本文采用无头结点的常规红黑树仿写红黑树的迭代器。
1、红黑树的begin、end迭代器 2、红黑树迭代器的operator
1、如果当前节点的右不为空迭代器返回右子树的最左节点
2、如果当前节点的右为空迭代器返回祖先当前节点是父亲的左(end()-1迭代器返回nullptr即end())
template class T
struct __RBTreeIterator
{typedef RBTreeNodeT Node;typedef __RBTreeIteratorT Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}//1、右不为空下一个节点是右树的最小节点//2、右为空去找右是父亲左的最近祖先Self operator()//找中序的下一个节点,即根的右树的最左节点,返回值是一个迭代器的对象{if (_node-_right ! nullptr){Node* min _node-_right;while (min-_left ! nullptr){min min-_left;}_node min;}else{Node* cur _node;Node* parent cur-_parent;while (parent ! nullptr cur parent-_right){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;}bool operator!(const Self s){return _node ! s._node;}
}; 3、红黑树迭代器的operator--
1、如果当前节点的左不为空迭代器--返回左子树的最右节点
2、如果当前节点的左为空迭代器--返回祖先当前节点是父亲的右
template class T
struct __RBTreeIterator
{typedef RBTreeNodeT Node;typedef __RBTreeIteratorT Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}Self operator--(){if (_node-_left!nullptr){Node* max _node;while (max-_right){max max-_right;}_node max;}else{Node* cur _node;Node* parent cur-_parent;while (parent ! nullptr cur parent-_left){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;}
}; 三、set的const迭代器
对于set和map它们的key都是不能改的。set的value不能修改map的value可以修改。
因为set的value是不能改的所以它的底层将普通迭代器和const迭代器全部封装成const迭代器来“解决”
//自己实现的不代表STL
typedef typename RBTreeK, K, SetKeyOfT::const_iterator iterator;
typedef typename RBTreeK, K, SetKeyOfT::const_iterator const_iterator; 封装之后又会出现新问题set使用迭代器其实都是在使用const迭代器但是自己实现的红黑树的迭代器接口返回普通类型的迭代器在Set.h中对this加上const“解决”
iterator begin()const
{return _t.begin();
}
iterator end()const
{return _t.end();
} 这时使用迭代器调用上方函数会发现红黑树返回了普通迭代器类型的迭代器类型不匹配。在红黑树中补齐const版本的迭代器函数解决
const_iterator begin()const//找红黑树最左节点
{Node* left _root;while (left ! nullptr left-_left ! nullptr){left left-_left;}return const_iterator(left);
}
const_iterator end()const
{return const_iterator(nullptr);
} 四、map的const迭代器
map的value是可以改的所以要分别设计普通迭代器和const迭代器。
typedef typename RBTreeconst K, pairconst K, V, MapKeyOfT::iterator iterator;
typedef typename RBTreeconst K, pairconst 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();
} 五、迭代器类的拷贝构造
STL库中的普通迭代器都可以转换为const迭代器这是迭代器类的拷贝构造所支持的。
这个拷贝构造有点特殊
//红黑树的迭代器
template class T,class Ref,class Ptr//key/value、T、T*
struct __RBTreeIterator
{typedef RBTreeNodeT Node;typedef __RBTreeIteratorT, Ref, Ptr Self;typedef __RBTreeIteratorT, T, T* iterator;Node* _node;__RBTreeIterator(Node* node):_node(node){}__RBTreeIterator(const iterator it)//const iterator本质还是普通迭代器:_node(it._node){}
}; 1、当这个模板的的Ref和PTR被实例化为T和T*时__RBTreeIterator(const iterator it)就是一个拷贝构造(没啥意义)
2、当这个模板的的Ref和PTR被实例化为const T和const T*时__RBTreeIterator(const iterator it)就是一个构造函数支持用普通迭代器去构造const迭代器。此时const迭代器的拷贝构造函数则由编译器自动生成刚好满足迭代器值拷贝的特点。
六、整体代码
1、RBTree.h
#pragma once
#include iostream
#include map
#include set
#include string
using namespace std;
enum Color
{RED,BLACK,
};
template class T//T类型代表value
struct RBTreeNode
{RBTreeNode(const T data):_parent(nullptr), _left(nullptr), _right(nullptr), _data(data), _col(RED){}RBTreeNodeT* _parent;RBTreeNodeT* _left;RBTreeNodeT* _right;T _data;Color _col;
};
//红黑树的迭代器
// key/value T T*
template class T,class Ref,class Ptr
struct __RBTreeIterator
{typedef RBTreeNodeT Node;typedef __RBTreeIteratorT, Ref, Ptr Self;typedef __RBTreeIteratorT, T, T* iterator;Node* _node;__RBTreeIterator(Node* node):_node(node){}__RBTreeIterator(const iterator it):_node(it._node){}Ref operator*(){return _node-_data;}Ptr operator-()//返回类型的地址{return _node-_data;}//1、右不为空下一个节点是右树的最小节点//2、右为空去找右是父亲左的最近祖先Self operator()//找中序的下一个节点,即根的右树的最左节点,返回值是一个迭代器的对象{if (_node-_right ! nullptr){Node* min _node-_right;while (min-_left ! nullptr){min min-_left;}_node min;}else{Node* cur _node;Node* parent cur-_parent;while (parent ! nullptr cur parent-_right){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;}Self operator--(){if (_node-_left!nullptr){Node* max _node;while (max-_right){max max-_right;}_node max;}else{Node* cur _node;Node* parent cur-_parent;while (parent ! nullptr cur parent-_left){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;}bool operator!(const Self s)const{return _node ! s._node;}bool operator(const Self s)const{return _node s._node;}
};
//pair的比较是如果first小还要比second我们只要比first所以加了仿函数KeyOfT用以取出first进行比较
//set-RBTreeK, K, SetKeyOfT
//map-RBTreeconst K, pairK,V, MapKeyOfT
template class K, class T,class KeyOfT
class RBTree
{
public:typedef __RBTreeIteratorT,T,T* iterator;typedef __RBTreeIteratorT, const T, const T* const_iterator;iterator begin()//找红黑树最左节点{Node* left _root;while (left!nullptrleft-_left!nullptr){left left-_left;}return iterator(left);}iterator end(){return iterator(nullptr);}const_iterator begin()const//找红黑树最左节点{Node* left _root;while (left ! nullptr left-_left ! nullptr){left left-_left;}return const_iterator(left);}const_iterator end()const{return const_iterator(nullptr);}typedef RBTreeNodeT Node;pairiterator,bool Insert(const T data)//对于map来说data是pair{if (_root nullptr){_root new Node(data);_root-_col BLACK;//根节点给黑色return make_pair(iterator(_root), true);//返回插入的节点}KeyOfT kot;//搞一个仿函数对象//_root不为空Node* parent nullptr;Node* cur _root;while (cur){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 make_pair(iterator(cur),false);//插入失败说明找到了返回被查找节点的迭代器}//开始插入cur new Node(data);Node* newNode cur;//记录cur的地址make_pair返回插入节点的地址cur-_col RED;//新插入节点给红色可能违反规则。如果给黑色会导致其他路径的黑色节点数量不相同必定违反规则。 if (kot(parent-_data) kot(data)){parent-_right cur;cur-_parent parent;//维护cur的父指针}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 ! nullptr uncle-_col RED){//变色parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else//情况二或情况三{if (cur parent-_left)//情况二直线{RotateRight(grandfather);//右单旋parent-_col BLACK;grandfather-_col RED;}else//情况三折线{RotateLeft(parent);//左单旋RotateRight(grandfather);//右单旋cur-_col BLACK;grandfather-_col RED;}break;}}else//如果父亲是祖父的右孩子{Node* uncle grandfather-_left;if (uncle ! nullptr uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else{if (cur parent-_right)//情况二直线{//g// p// cRotateLeft(grandfather);//左单旋parent-_col BLACK;grandfather-_col RED;}else//情况三折线{//g// p//c RotateRight(parent);//右单旋RotateLeft(grandfather);//左单旋cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return make_pair(iterator(newNode), true);//返回插入的节点}void Inorder(){_Inorder(_root);}bool IsBalance(){return _IsBalance();}
private:void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout kot(root-_data) : root-_data.second endl;_Inorder(root-_right);}bool Check(Node* root, int blackNum, const int ref)//检查有没有连续红节点{if (root nullptr){if (blackNum ! ref){cout 路径上黑节点数量不一致 endl;return false;}return true;}if (root-_col BLACK){blackNum;}if (root-_col RED root-_parent-_col RED){cout 违反规则父子均为红 endl;return false;}return Check(root-_left, blackNum, ref) Check(root-_right, blackNum, ref);}bool _IsBalance(){if (_root nullptr)return true;if (_root-_col ! BLACK){return false;}//数一下一条路径黑色节点数量int ref 0;//统计一条路上黑色节点的数量Node* left _root;while (left ! nullptr){if (left-_col BLACK){ref;}left left-_left;}return Check(_root, 0, ref);}void RotateLeft(Node* parent)//左单旋{Node* grandfather parent-_parent;Node* cur parent-_right;if (parent _root){_root cur;cur-_parent nullptr;}else{if (grandfather-_left parent)//需要判定parent原来属于grandfather的哪一边grandfather-_left cur;elsegrandfather-_right cur;cur-_parent grandfather;}parent-_right cur-_left;if (cur-_left ! nullptr)cur-_left-_parent parent;cur-_left parent;parent-_parent cur;}void RotateRight(Node* parent)//右单旋{Node* grandfather parent-_parent;Node* cur parent-_left;if (parent _root){_root cur;cur-_parent nullptr;}else{if (grandfather-_left parent){grandfather-_left cur;cur-_parent grandfather;}else{grandfather-_right cur;cur-_parent grandfather;}}parent-_parent cur;parent-_left cur-_right;if (cur-_right ! nullptr)cur-_right-_parent parent;cur-_right parent;}
private:Node* _root nullptr;
}; 迭代器的begin(),end()接口放在红黑树这个类中而operator--放在迭代器这个类中自己写一下循环遍历红黑树的代码就知道为什么这样设计了。
2、Set.h
#pragma once
#include RBTree.h
namespace jly
{template class Kclass set{struct SetKeyOfT{const K operator()(const K key)//传入value{return key;}};public:typedef typename RBTreeK, K, SetKeyOfT::const_iterator iterator;typedef typename RBTreeK, K, SetKeyOfT::const_iterator const_iterator;pairiterator, bool insert(const K key){pairtypename RBTreeK, K, SetKeyOfT::iterator,bool ret _t.Insert(key);return pairiterator, bool(ret.first, ret.second);}iterator begin()const{return _t.begin();}iterator end()const{return _t.end();}private:RBTreeK, K, SetKeyOfT _t;};void test2(){//int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };//int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };//int a[] { 9,8,7,6,5,4,3,2,1};setint s;for (auto e : a){s.insert(e);}setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}}
} 3、map.h
#pragma once
#include RBTree.h
namespace jly
{template class K,class Vclass map{struct MapKeyOfT{const K operator()(const pairK, V kv)//传入value{return kv.first;}};public://typename是C中用于指定一个类的类型的关键字。//通常用于表示某个类型是一个类类型而不是其他类型如int等。//这里不加typedef编译器无法区分iterator是一个类型还是一个静态变量。因为他俩都可以这么写。。//所以从类模板取出内嵌类型就需要加typedeftypedef typename RBTreeconst K, pairconst K, V, MapKeyOfT::iterator iterator;typedef typename RBTreeconst K, pairconst K, V, MapKeyOfT::const_iterator const_iterator;pairiterator,bool insert(const pairK, V kv){return _t.Insert(kv);}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)//传入key值{pairiterator,bool ret _t.Insert(key,V());return ret.first-second;//找到retmake_pairiterator,bool的first解引用找到节点value}private:RBTreeconst K, pairconst K,V, MapKeyOfT _t;};void test1(){int a[] { 8, 3, 1, 10, 6, 4, 7, 14, 13 };//int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };//int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };//int a[] { 9,8,7,6,5,4,3,2,1};mapint,int m;for (auto e : a){m.insert(make_pair(e,e));}mapint, int::iterator it m.begin();while (it ! m.end()){cout (* it).first ;it;}cout endl;for (auto e : m){cout e.first ;}}
}
