什么网站可以做软件有哪些东西,能帮忙做网站建设,kilu wordpress,如何查找网站根目录目录 红黑树的完善默认成员函数迭代器的增加 红黑树的封装红黑树模板参数的控制仿函数解决取K问题对Key的非法操作 insert的调整map的[]运算符重载 在list模拟实现一文中#xff0c;介绍了如何使用同一份代码封装出list的普通迭代器和const迭代器。今天学习STL中两个关联式容器… 目录 红黑树的完善默认成员函数迭代器的增加 红黑树的封装红黑树模板参数的控制仿函数解决取K问题对Key的非法操作 insert的调整map的[]运算符重载 在list模拟实现一文中介绍了如何使用同一份代码封装出list的普通迭代器和const迭代器。今天学习STL中两个关联式容器map和set其底层就是红黑树而且是同一棵红黑树。所以今天学习如何用同一棵红黑树封装出map和set。 红黑树的完善
默认成员函数
map和set的底层是红黑树所以先将红黑树重要的四个默认成员函数完善好。这四个成员函数在介绍搜索二叉树时已进行过介绍这里不再讲解。
public://RBTree() default;RBTree():_root(nullptr){}RBTree(const RBTree t)//拷贝构造{_root Copy(t._root);}RBTree operator(RBTree t)//赋值重载{swap(_root, t._root);return *this;}~RBTree(){Destroy(_root);_root nullptr;}
private:Node* Copy(Node* root){if (root nullptr){return nullptr;}Node* newnode new Node(root-_kv);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;}迭代器的增加
map和set作为关联式容器迭代器是必不可少的而map和set都是由同一颗红黑树封装而成所以map和set的迭代器其实就是红黑树的迭代器。
map和set的迭代器都是双向迭代器也就是说都支持- -的操作。 红黑树的迭代器的结构和list的是类似的其成员都只有一个节点类只有一个构造函数初始化节点。
迭代器
templateclass T, class Ref, class Ptr
struct RBTreeIterator
{typedef RBTreeNodeT Node;typedef RBTreeIteratorT,Ref,Ptr self;Node* _node;//成员RBTreeIterator(Node* node):_node(node){}
};节点类
templateclass T
struct RBTreeNode
{T _kv;RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;Color _col;RBTreeNode(const T kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED)//默认为红色{}};对于自封装的迭代器解引用是否相等的比较是少不了的而这部分操作还是比较容易的不理解的可参考list迭代器的实现
注意此时要访问的的对象是_kv Ref operator*(){return _node-_kv;}Ptr operator-(){return _node-_kv;}bool operator(const self s){return _node s._node;}bool operator!(const self s){return _node ! s._node;}真正的难点是红黑是迭代器的遍历中序遍历红黑树便能得到一个升序序列而迭代器访问的顺序也是中序左根右。采用Inorde来遍历是很简单的但是它是不可控的只能一把把红黑树全遍历完。而迭代器必须是一个一个节点访问的这就增加了它实现的难度。 前置 对于即按中序访问下一个节点但查找时此时的节点已经为根所以查找的顺序为根右此时关注的点是下一个节点是否为空由此分为两种情况。
右子树不为空则右子树的最左节点即为下一个要访问的节点。右子树为空说明当前子树已经访问完了沿着到根节点的路径查找祖先节点中左孩子为父亲的节点即为下一个要访问的节点。 如果父节点为祖先节点的右孩子说明递归有一定深度需要不断向上查找。 self operator(){if (_node-_right){Node* leftMost _node-_right;while (leftMost-_left){leftMost leftMost-_left;}_node leftMost;//return self(leftMost);}else//说明当前子树访问完了{Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_right){cur parent;parent parent-_parent;}//return self(parent);_node parent;}return *this;}前置可以引用返回。 后置 后置逻辑与前置是一样的只不过返回的是之前的值。所以用ret保留原先的值再访问下一个节点最后返回ret即可。此时不能引用返回。 self operator(int){self ret *this;if (_node-_right){Node* leftMost _node-_right;while (leftMost-_left){leftMost leftMost-_left;}_node leftMost;}else//说明当前子树访问完了{Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_right){cur parent;parent parent-_parent;}_node parent;}return ret;}前置- - 红黑树的- -即访问当前节点的前一个节点。此时的查找顺序变为根左自身就作为根节点所以此时只需要注意左节点是否为空。
左节点不为空则按右根左的遍历顺序遍历访问左子树的最右孩子。左节点为空说明当前子树已经访问完了沿着到根节点的路径查找祖先节点中右孩子为父亲的节点即为下一个要访问的节点。 如果父节点为祖先节点的左孩子说明递归有一定深度需要不断向上查找 self operator--(){if (_node-_left){Node* rightMost _node-_left;while (rightMost-_right){rightMost rightMost-_right;}_node rightMost;}else//说明当前子树访问完了{Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_left){cur parent;parent parent-_parent;}_node parent;}return *this;} 后置- - 返回- -之前的节点。 self operator--(int){Node* ret *this;if (_node-_left){Node* rightMost _node-_left;while (rightMost-_right){rightMost rightMost-_right;}_node rightMost;}else//说明当前子树访问完了{Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_left){cur parent;parent parent-_parent;}_node parent;}return ret;}迭代器实现后我们需要在红黑树的实现当中进行迭代器类型的typedef。需要注意的是为了让外部能够使用typedef后的迭代器类型iterator需要在public区域进行typedef。
然后在红黑树当中实现成员函数begin和end
begin函数返回中序序列当中第一个结点的迭代器即最左结点。end函数返回中序序列当中最后一个结点下一个位置的迭代器这里直接用空指针构造一个迭代器。
实现时红黑树一层命名为与map和set作区分首字母大写。
templateclass K, class T,class KeyOfT//map时T为pairset时为K
class RBTree
{typedef RBTreeNodeT Node;
public:typedef RBTreeIteratorT, T, T* Iterator;typedef RBTreeIteratorT, const T, const T* Const_Iterator;//map和set的迭代器也是使用红黑树的迭代器但树的结构有所区别。//红黑树的迭代器Iterator Begin(){Node* leftMost _root;while (leftMost-_left){leftMost leftMost-_left;}return leftMost;//此时返回的是节点而返回类型为迭代器所以会发生隐式类型转化调用红黑树的迭代器构造函数构造一个迭代器}Iterator End()//与库里的带头红黑树不同我们这里不带头为空即尾{return nullptr;}Const_Iterator Begin()const{Node* leftMost _root;while (leftMost-_left){leftMost leftMost-_left;}return leftMost;}Const_Iterator End()const//与库里的带头红黑树不同我们这里不带头为空即尾{return nullptr;}private:Node* _root nullptr;};库中红黑树的结构实现 库里的红黑树结构中还有一个头节点headerheader的parent指针指向_root,_root的parent指针指向headerheader的左右指针分别指向红黑树的最小和最大节点。 由于结构不同所以我们迭代器的实现也有一定缺陷但不妨碍正常使用所以就不进行完善了。
红黑树的封装
都知道set是key模型而map是key_value模型如何才能使用同一棵红黑树满足二者的需求呢这就是封装的魅力。 了解map和set之后两者的冲突点主要有
map是KV模型set的K模型获取Key map和set储存数据的方式不一样红黑树的大多数操作都是需要支持用Key比大小的。 map和set的Key不可修改问题
红黑树模板参数的控制
关于set和map的不同模型问题先看看库中是如何解决这个问题的。 对于红黑树而言它是不知道上层是map还是set的但是这些都不重要底层红黑树利用泛型的思想将map和set传过来的参数实例化为模板这样一来上层map传对应的参数过来底层红黑树就将这些参数泛化成模板就能生成对应数据类型的红黑树了set也是同理。
如简化版的下图map和set的底层都是一棵红黑树其中map和set中的红黑树传入的第一个参数都为K而map的第二个参数传入的是一个键值对pair这也正是map的数据类型。set的第二个参数继续传入一个K作为set的数据类型。也正是这样的设计能够让一棵红黑树同时封装map和set。
这样一来你上层传的是pair底层红黑树实例出来的就是map传入的为K则为set。 第三个模板参数是解决下一个问题所提供的仿函数。 set中调用的红黑树为什么要传两次K set中传两次K确实有点多余但此时是map和set共用一棵红黑树在map的日常使用中如finderase这样的操作其参数就是一个K类型所以map中是需要有K的。
仿函数解决取K问题
所谓取K就是由于map和set的数据类型不一致一个是KV的键值对一个是模板参数K。作为而平衡二叉树的红黑树Key值的比对是少不了的如插入查找等功能都是需要有Key值的比对的。对于set来说可以直接用传入的K进行比对而map是pair需要解引用访问其first才能找到Key否则直接比对pair不一定是我们想要的比对结果。 所以为了解决这个问题继续参考上一个问题的解决方式在map和set调用红黑树传参时传入一个可以取Key的仿函数。仿函数介绍
map的仿函数要获取是数据是什么类型仿函数的参数就是什么类型。 struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};set的仿函数set的仿函数看起来有点多此一举但为了适配map的解决提供一个仿函数也无妨。 struct SetKeyOfT{const K operator()(const K key){return key;}};这样一来set容器传入底层红黑树的就是set的仿函数map容器传入底层红黑树的就是map的仿函数。
有了仿函数当底层红黑树需要进行两个结点之间键值的比较时都会通过传入的仿函数来获取相应结点的键值然后再进行比较下面以红黑树的查找函数为例。
Iterator Find(const T data){KeyOfT kot;if (_root nullptr){return nullptr;}Node* cur _root;//Node* parent nullptr;while (cur){if (kot(data) kot(cur-_kv)){//parent cur;cur cur-_right;}else if (kot(data) kot(cur-_kv)){//parent cur;cur cur-_left;}else{return cur;}}return nullptr;}对Key的非法操作
map和set都是不支持修改Key的
map对此的解决方案是pair对中的Key用const修饰
map成员的定义
private:RBTreeK, pairconst K, V, MapKeyOfT _rbt;set将红黑树的第二个参数改为const K好像也能解决问题但库里并没有采用这种方法。
简易办法使用const K禁止被修改。目前还没发现什么大问题如果发现问题请告知 set成员的定义 private:RBTreeK,const K, SetKeyOfT _rbt;第二种就是采用库里的方法。 set无论普通还是const迭代器都使用红黑树的const迭代器
public://库里的方法typedef typename RBTreeK, K, SetKeyOfT::Const_Iterator iterator;typedef typename RBTreeK, K, SetKeyOfT::Const_Iterator const_iterator;但是这样就会出现类型转化问题 原因如下 这里的迭代器不是原生指针的迭代器而是通过封装而来的借助模板实现了const和非const版的迭代器也就导致普通的无法转为const迭代器通过调试发现问题出现在获取迭代器上由于set的普通迭代器也由const迭代器封装而来set在获取普通迭代器时最底层的红黑树返回的是普通迭代器但set的普通迭代器实际为const迭代器此时就发生了类型不匹配的问题。 对此库中提供了如下解决方案在红黑树迭代器中提供一个构造函数 在红黑树迭代器中增加一个参数为普通迭代器类型的构造函数。该构造函数取参数中普通迭代器的节点重新构造一个迭代器const版。该方法绕过转化采用构造生成一个const版的迭代器自然就没有类型转化的问题。
虽然这个构造函数增加在红黑树的迭代器中但是map的迭代器不会有影响这个构造函数只会匹配到set对应的状况。 typedef RBTreeIteratorT, T, T* Iterator; //声明类型普通迭代器RBTreeIterator(const Iterator it)//类型为普通迭代器因为就是由于普通迭代器转化为const迭代器这一环出了 问题这里专门针对这一情况处理:_node(it._node)//此时需要的是一个const迭代器由于模板无法转化普通转const直接转化不行那么我们就在返回时利用隐式类型转化{}具体过程请看下图。
insert的调整
在AVL树红黑树阶段实现的insert的返回值都为bool在map和set中则是改为返回键值对pair。
以map为例
函数声明
pairiterator,bool insert (const value_type val);可以看到其返回值为pairpair的第一个成员为一个迭代器指向新插入的元素或者已存在的等效元素第二个成员为bool用来检测插入是否成功也就是说insert成功的话会返回一个指向新插入元素的迭代器其bool值为true的pair如果insert失败则会返回一个指向容器中原有的K的迭代器其bool值为false的pair。
map的[]运算符重载
map支持[]访问容器中Key值并返回Key对应的Valueset不支持[]重载因为只有一个Key。
也就是说[]的参数为pair中的第一个成员K其使用说明如下 如果K与容器中某个元素的键匹配则该函数返回K值关联的Value引用。如果K与容器中任何元素的键不匹配则该函数用该键插入一个新元素并返回对其映射值的引用。这个新元素会有默认值。 调用[]类似于下面的操作
(*((this-insert(make_pair(k,mapped_type()))).first)).second也就是说[]的实现是借助于insert实现的。而这样的话[]的用法就有两种
插入 如果K是map中不存在的那么这就是一个插入操作由于其返回值为第二个模板参数value的引用所以可以直接修改。 修改 如果K是map中已有的值那么insert将会返回已存在K的迭代器[]最终返回一个K的引用相当于支持修改操作。
所以[]重载运算符的实现如下。 //返回value的引用V operator[](const K key){pairiterator, bool ret _rbt.Insert({ key,V() });return ret.first-second;//不理解返回second的结合operator-看}返回值类型为第二个参数的引用所以支持直接修改。关于返回V为何是返回it.first-secondit 为接受的是insert返回的pair对其first为指向元素的迭代器-调用了迭代器的operator-此时返回的是存储KV的pair此时的second为V
