动漫做的游戏 迅雷下载网站,大型网络游戏排行榜2021前十名,网站建设网站多少钱,网站后台上传word目录
map与set的模拟实现
1.基本框架
2.模拟实现map与set所需要做的事
1.使用模板 , 达到泛性编程
2.比较问题
3.迭代器
RBTree中:
operator
operator--
4.map [ ] 的实现
5.使用普通迭代器构造const迭代器
效果 map与set的模拟实现
1.基本框架
map set 2.模拟实…目录
map与set的模拟实现
1.基本框架
2.模拟实现map与set所需要做的事
1.使用模板 , 达到泛性编程
2.比较问题
3.迭代器
RBTree中:
operator
operator--
4.map [ ] 的实现
5.使用普通迭代器构造const迭代器
效果 map与set的模拟实现
1.基本框架
map set 2.模拟实现map与set所需要做的事 调用模板, 使得用map与set复用同一棵树(解决map存pair, set存key的问题)比较问题迭代器中, ,--的实现(遍历二叉树)map[ ] 的实现维护底层搜索二叉树的性质, 要使用const迭代器, set可以都用const迭代器, 但是map需要达到key不能修改, 但允许value可以修改, 所以红黑树也需要实现普通迭代器,--使得key不能修改--map再传递pair的时候,给K加上const就行 --set的iterator 是红黑树中的const_iterator const_iterator也是const_iterator --map的使用了iterator 与 const_iterator set的iterator调用的时候, 会发生隐式类型转换, 普通迭代器--const迭代器 如果没提供普通迭代器到const迭代器的构造会报错 -- 需要提供 1.使用模板 , 达到泛性编程 map: kv类型 set : k类型
map: set: 2.比较问题
由于使用了泛性编程, RBTreeNode里面的_data类型不确定, 可能是K, 也可能是pair
--如果是K(set)的比较,不会有问题
--如果是pair(map)的比较, 比较会出现问题
pair的比较: 如果first小就小, 如果first不小, 比较second, second小就小 但我们只期望按K去比较 解决: 使用仿函数
红黑树并不知道传过来的T是K类型还是pair类型, 但是上一层知道, 于是我们给它加一个仿函数,
这个仿函数在map/set里面实现 用来获取key,然后传递给红黑树, 让其根据key来比较
像这样: map set 用法:
data 为T类型, 可能是K类型, 也可能是pair类型,我们将其传递给仿函数,来获取key
1.插入 2.查找 Node* cur -_data 为T类型, 可能是K类型, 也可能是pair类型,我们将其传递给仿函数,来获取key 3.迭代器 map与set的迭代器是使用红黑树内部的迭代器 1.注意: 当我们去取一个类模板的内嵌类型的时候, 前面要加一个typename 2. 原因: 因为编译器无法区分, 你取得是类型还是静态变量 加上typename告诉编译器所取得是类型, 等该类模板实例化后, 再去找这个类型 3.示例: map set 框架: RBTree中: begin 使用最左边的节点构造迭代器 end 1.使用空节点构造迭代器(一般是最右边的节点的下一个---是nullptr) 2.实现的时候增加哨兵位 --此时如果it走到最后一个节点,再, 就直接走到end --特殊处理: 优点:end--的时候, 直接到最右边的节点 operator 左子树, 根 , 右子树 (中序,找完右子树后, 其树就被访问完了) 思路: 1.有右子树: 就往右子树走--找右子树的最左节点 2.没有右子树: 看是不是parent的左子树 --是的话就把parent给it --不是的话向上调整 (调整最后没有父亲节点了,跳空) 沿着根路径, 找孩子是父亲左孩子的那个祖先 对以下情况演示: 1.该节点有右子树 2.该节点没有右子树 3.走到最后一个节点 代码: Self operator() {//1.右子树不为空,找右子树的最左节点if (_node-_right) {Node* subRL _node-_right;while (subRL-_left) {subRL subRL-_left;}_node subRL;}//2.右子树为空, 找节点是父亲左孩子的祖先else {Node* cur _node;Node* parent cur-_parent;while (parent parent-_right cur){cur parent;parent parent-_parent;}_node parent;}return *this;} operator-- 和上面基本一样,只是换了个方向: 右子树, 根 , 左子树(该顺序访问, 走完左子树,该树就走完) 思路: 1.有左子树, 就往左子树走---找左子树里最右边节点 2.没有左子树, 就找节点是父亲的右孩子的祖先 --如果当前节点就是父亲的右孩子, 直接把parent给it --如果当前节点不是父亲的右孩子, 沿根路径向上调整, 找到为止(或找到p为nullptr) 找到了就把parent给it 代码: Self operator--(){//1.如果有左子树,就往左子树走,找其最右边的节点if (_node-_left) {Node* subLR _node-_left;while (subLR-_right) {subLR subLR-_right;}//然后把这个节点给it_node subLR;}//2.如果没有左子树, 就找节点是父亲右孩子的祖先else {Node* cur _node;Node* parent cur-_parent;while (parent parent-_left cur) {cur parent;parent parent-_parent;}//然后把这个节点给it_node parent;}return *this;} 4.map [ ] 的实现 1.修改insert的返回值为pairiterator,bool --修改RBTree里Insert的返回值: --空树插入成功 --非空树插入失败 --非空树插入成功 这里使用newnode记录以下cur节点, 下面需要对红黑树调整, cur 可能会发生改变 2.[ ]的实现 --调用RBTree里的Insert函数 --返回其second pairiterator, bool insert(const pairconst K,V kv){return _t.Insert(kv);}//[]的实现V operator[](const K key) {pairiterator,bool ret _t.Insert(make_pair(key, V()));return ret.first-second;} 5.使用普通迭代器构造const迭代器 1.问题:如果使用普通迭代器, 那么key的值会被修改, 不满足二叉搜索树性质 示例: 2.我们使用const迭代器 出现报错 --原因:发生隐式类型转换, 但我们没有提供使用普通迭代器构造const迭代器的构造函数, 转换不了, 会报错 --解决: 提供一个支持普通迭代器到const迭代器的转换 --为什么RBTree不都返回const迭代器?? ---因为map与set复用的是同一个红黑树来set全用const可以, 但map允许修改V 代码: --当Ref是T, Ptr是T*的时候, 调用这个构造函数就是拷贝构造 --当Ref是constT ,Ptr是constT*的时候, 调用这个构造函数就是支持普通迭代器构造const迭代器的转换 效果 代码:Map and Set/Map and Set · 朱垚/数据结构练习 - 码云 - 开源中国 (gitee.com)
