宝山网站建设方案,pc软件开发工具,国内跨境电商建站系统,用aspx做的网站一、红黑树迭代器的实现
基本的框架和实现链表的迭代器思路是一样的#xff0c;都是对指针进行封装处理#xff0c;然后实现一些基本的运算符重载#xff0c;最重要的是operator#xff0c;需要不递归的实现走中序的规则#xff0c;这里只实现那最核心的几个基本功能都是对指针进行封装处理然后实现一些基本的运算符重载最重要的是operator需要不递归的实现走中序的规则这里只实现那最核心的几个基本功能用遍历和插入值去测试其余的一些零零散散的功能就不进行实现了
基本框架 operator的实现
按照中序遍历的规则首先是走左子树然后是根然后是右子树从begin位置开始可以认为此时是最左边的那一个此时的是要往该节点的右边去遍历而且是右边的最左边因此要先确定此时是否有右边然后走到右边的最左边就是下一个要遍历的节点如果右边为空则我们说明该节点已经遍历结束了此时往上走找到parent需要判断parent是否已经遍历过则需要再判断parent是否是其上一个节点的右边如果是右边则说明此时parent位置已经被遍历过且右子树遍历结束需要继续向上走 psoperator--的思路和是一样的不过啥反过来走右子树 根 左子树这里不过多分析 参考代码
templateclass T, class Ref, class Ptr
struct __RBTreeIterator
{typedef RBTreeNodeT Node;typedef __RBTreeIteratorT, Ref, Ptr Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}// 1、typedef __RBTreeIteratorT, T, T* itertaor; 拷贝构造// 2、 typedef __RBTreeIteratorT, const T, const T* const_itertaor;// 支持普通迭代器构造const迭代器的构造函数__RBTreeIterator(const __RBTreeIteratorT, T, T* it):_node(it._node){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator!(const Self s){return _node ! s._node;}Self operator(){if (_node-_right){// 1、右不为空下一个就是右子树的最左节点Node* subLeft _node-_right;while (subLeft-_left){subLeft subLeft-_left;}_node subLeft;}else{// 2、右为空沿着到根的路径找孩子是父亲左的那个祖先Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_right){cur parent;parent parent-_parent;}_node parent;}return *this;}Self operator--(){if (_node-_left){// 1、左不为空找左子树最右节点Node* subRight _node-_left;while (subRight-_right){subRight subRight-_right;}_node subRight;}else{// 2、左为空孩子是父亲的右的那个祖先Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_left){cur parent;parent parent-_parent;}_node parent;}return *this;}
}; 二、封装set和map
由于之前模拟实现的红黑树是为了模拟实现和学习其中的核心功能也就是如何完成插入以及明白其算法原理所以在其他的细节上与库里的对比做了很多的省略本次将用自己实现的红黑树通过封装红黑树模拟实现出set和map加深对set和map的理解和底层实现
我们对红黑树的改造目的是为了兼容set和map的复用因此得先了解set和map具体的使用区别
1.对红黑树的基本改造
虽然底层都是搜索二叉树但是节点内存的值类型是不同的从使用的角度来看可以认为k模型每个节点存的就是一个key搜索树的顺序和规则也是根据key的大小比较规则去执行的而kv模型则是每个节点内存着key和value搜索树以key的大小比较规则其执行而每个key都有一个关联性很强的value所以在节点的数据类型上看kv模型的节点数据类型pair类型的
此时红黑树需要兼容任意类型的模板参数都能实现相同的比较规则都是找到key去比较则需要像以下类模板定义
templateclass K,class T,class KeyOfT 接下来就是将所有关于比较的部分需要换上仿函数通过仿函数去取得key第一个参数K代表key当一些需要使用到key类型的地方返回参数等等时使用修改过后对set和map的基本封装就没有问题了至少可以实现插入功能了各自将框架搭起来然后复用Insert进行测试 2.对迭代器的封装
1set迭代器的封装
set的迭代器要求无论是iterator还是const_iterator都不能对值进行修改因为在set里面存着的值就是keykey不允许被修改所以我们封装时直接将两种迭代器都用红黑树的const_iterator去复用注意typedef一个类型名的时候需要在前面加上typename 但是如果红黑树的迭代器实现部分没有将普通迭代器转换成常量迭代器的函数则直接复用会报错 说的是在使用迭代器的时候返回的迭代器类型是普通迭代器类型但是返回参数类型的声明却是常量迭代器类型无法转换这是由于我们使用的是非const对象调用红黑树的迭代器则红黑树会则会穿一个普通迭代器但是我们iterator的类型实际是const_iterator因此无法转化报错解决这个问题的办法是在红黑树的迭代器实现部分提供一个能够将普通迭代器转化成const迭代器的函数 当传参为const类型的迭代器时该函数为拷贝构造当参数是普通迭代器时则那够构造一个const类型的迭代器返回 typedef typename RBTreeK, K, SetKeyOfT::const_iterator iterator;typedef typename RBTreeK, K, SetKeyOfT::const_iterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();} 2map的迭代器封装
map的值是pair类型first是key不允许修改second是value允许修改所以map的普通迭代器是允许修改值的但要保证key不能被修改在传参时传pairconst K,V 3.map的operator[ ]的实现
实现[ ]的重载需要先对红黑树中插入函数的返回值进行改造之前为了简化因此用bool值作为返回值现在需要完整的实现它返回值为pair类型first为插入成功位置的迭代器若是插入失败则说明书中已经有了一个值此时first返回已有的值的迭代器second则是bool值表示返回插入是否成功
改造结束后根据[ ]功能实现这个部分在之前有做过分析不详细分析提供参考代码
V operator[](const K key)
{pairiterator, bool ret _t.Insert(make_pair(key,V()));return ret.first-second;
} 三、测试
以上就是模拟封装set和map时需要注意的部分接下来就是通过一些最基本的测试去测试set和map是否能实现一些基本用法下面提供几个用于测试的代码
set测试迭代器和插入 void test_set1()//测试迭代器和插入{srand(time(0));const size_t N 1000;setint s;for (int i 0; i N; i){size_t x rand() % 100;s.Insert(x);}for (auto e : s){cout e ;}cout endl;}
map测试迭代器和插入 void test_map1()//测试插入和迭代器{srand(time(0));const size_t N 1000;mapint, int m;for (int i 0; i N; i){size_t x rand() % 100;m.Insert(make_pair(x, x));}for (auto e : m){cout e.first : e.second endl;}cout endl;}
map测试[ ]的重载 void test_map2()//测试[]的重载{mapstring, string m;m[字符串] string;m[清理] clear;m[想念] miss;m[错过] miss;m[错过] miss;for (auto e : m){cout e.first : e.second endl;}cout endl;} 总结
本篇模式实现了用红黑树对set和map的封装以及部分需要注意的难点还有对红黑树迭代器的实现进行了补充结合着对set和map迭代器的封装复用去一起整理的思路
