罗源城乡建设网站,彩票网站开发是否合法,如何做一款app,thinkphp做网站教程简单了解map 和 set 的实现 首先我们要知道#xff0c;map 和 set 的底层就是 红黑树#xff0c;但是 STL 当中 #xff0c;map 和 set 并不是我们想象的#xff0c;直接使用一个 pair 对象来存储一个 key-value 或者 是 一个 key。具体如下所示#xff1a;
set#xff…简单了解map 和 set 的实现 首先我们要知道map 和 set 的底层就是 红黑树但是 STL 当中 map 和 set 并不是我们想象的直接使用一个 pair 对象来存储一个 key-value 或者 是 一个 key。具体如下所示
set 在set 当中只需要存储一个 key 就可以了因为 set 是 key 的结构。但是在库当中把 key typedef 了两个值 key_type 和value_type map 在map 当中也是使用了 key_type 和 value_type但是map 本身就是 key-value 的结构。然后我们又发现map 的 value_type 又是 使用 pair 类进行封装存储的 我们在来看 红黑树的 部分源代码 也就是说在 map 和 set 当中的值真正存入 红黑树当中的其实是 Value。按照上述的说法set 存入红黑树的是 Keymap 存入红黑树的是 一个 pair 对象对象当中存储的 是key-value 。 所以现在你就搞清楚为什么 set 多搞出来的 key 和 map 的 Value 为什么要用 pair 来设计这两者到底用到哪里去了。
而 在STL 当中 的红黑树 的结点类 套了两层先实现了 __rb_tree_node_base类这个类当中就是 一个结点的三叉链还有颜色等等的结点成员 然后用一个 _rb_tree_node 类 去继承这个类 此时的 set 或者 map 当中的 key 或者 key-value 就直接通过模版继承到 __rb_tree_node 的 Value 当中了 也就是说在红黑树结点类当中不管传入的是 key 的结构还是 key-value 的结构都是存储在 红黑树结点类的 Value 当中的这里利用模版搞了一个泛型。
那么为什么在 set 当中要用 两个 key 在 map 当中也要和 用一个 key 多在模版当中传如呢 如上这个函数在 set 和 map 当中肯定是要实现的如果我们set当中只有一个 key在map 当中也是只有 pair 来存储键值对那么在上述函数调用的时候对于set 还好因为 set 的value 就是一个 key 但是 map 的value是一个pairpair 如果作为参数来传入这个 find 函数的话在find当中的实现又是直接使用 x 这个key 来实现的pair 当中的key 要单独访问。所以map 直接传入 pair 是不行的。
所以在map 当中就把 key 单独拿出来了set 为了适配 map和 map 保持一致也跟着把 key 单独多列一个出来。
红黑树的代码 和 setmap当中的大体框架 关于红黑树的实现请看下面这篇博客C - 红黑树 介绍 和 实现_chihiro1122的博客-CSDN博客 在上述博客当中写的红黑树其中的就是简单 key-value 结构用 pair 存储是写死的。而上述我们修改出来的红黑树就是一个 泛型。红黑树的结点当中的值不在值存储 pair还可以支持 set 单独存储 key。
大致结构 注意因为上述上述可能需要多个 头文件如果 头文件在 cpp 文件当中没有包含的话头文件是不会进行 编译的那么其中的错误就不会编译出来。 而且对于 红黑树当中的 insert插入函数其中参数是 插入 value但是set 是 keymap 是 key-value所以我们这里直接使用 模版参数 T 传入就行 但是又遇到了一个大问题在 insert比较函数当中我们使用的是 key 值来进行比较的但是 此时 T 的模版参数是 pair 的话我们之前使用 key 来作为参数比较的规则就不适用了。 这时候就需要去重载 pair 类的 运算符 了其实在 pair 的实现当中官方就已经重载了运算符重载函数 但是你仔细观察其实这里面的比较规则 不是我们想要的比较规则比如小于他这里实现的是first 小 就小否则second 小就小。 但是我们只期望用 key 来比。 库当中已经实现了所以这里我们不能直接去重载 pair 当中的 大于小于运算符重载函数参数也是一样的两者之间不好重载。
所以这里我们就要使用仿函数的方式去实现。仿函数的博客可以看以下博客C - 优先级队列priority_queue的介绍和模拟实现 - 反向迭代器的适配器实现 - 仿函数_c priority_queue迭代器_chihiro1122的博客-CSDN博客 但是在上述优先级队列当中实现的仿函数该仿函数的功能是比较大小但是在红黑树当中的仿函数不是比较大小。
在 库当中的红黑树还有一个 参数是 KeyOfValue 这个 KeyOfValue 模版参数意思就是把 value 当中的 key 取出来。
所以我们要想 优先级队列当中仿函数的使用规则一样把仿函数的类通过模版参数传入进去。
因为 这个 仿函数的类不是写给用户来控制的是写给 map 和set 来使用的所以关于仿函数的类我们可以直接在 set 和 map 当中使用内部类来构造关于 set 和 map 的内部类仿函数构造如下
set
#pragma once
#includeRBTree.hnamespace Mynamespace
{templateclass Kclass set{struct SetKeyOfT{// 和 map 对照的标准写法//const k operator()(const pairK, K kv)//{// return p.first;//}// 其实可以直接这样写const k operator()(const K key){return key;}};private:RBTreeK, K , SetKeyOfT _t;};
} map
#pragma once
#includeRBTree.hnamespace Mynamespace
{templateclass K, class Vclass map{struct MapKeyOfT{const k operator()(const pairK, K kv){return p.first;}};private:RBTreeK, pairK , V , MapKeyOfT _t;};
}
两者的仿函数的返回值都是把 set 的 key 和 map 的pair里的key 取出来作为函数的返回值返回。
这样的话我们就可以在 红黑树的 insert函数当中使用仿函数来取出 对应的 key 值然后进行key 值的比较了。
红黑树当中对仿函数的调用如下例子 这里就调用 kot 对象当中的仿函数把 _data 当中的 key 值取出来如果这个 _data 是set 的那么 key 就是直接返回如果是 map 的就需要从 pair 当中取出。 这里之所以不想之前在优先级队列当中的仿函数一样直接仿函数的那种进行比较因为我们直接在仿函数当中进行比较的话不好进行比较不清楚到底怎样取出 key 。只有像上述一样写两个仿函数的类然后通过模版参数知道此时我需要怎样取出 key 值。 这一个仿函数只实现 取出 key 的功能是因为要和 比较方式分离如果我们在 取出 key 的仿函数当中就把 如何比较 实现了当然是可以的但是如果这样做的话相当于是把比较方式写死了如果我们想要用 仿函数的方式来在 set 和 map 当中进行 区别比较方式的话那么在 set 和map 的模版参数当中就需要再实现一个 区别 比较方式的 仿函数类。
但是对于 我们刚刚实现的 MapKeyOfT 和 SetKeyOfT 这两个仿函数类如果是单独使用 set 和 map 的人是不会关心的因为这两个仿函数是供给 内部用的外部根本就不需要。所以我们发现在官方库的 红黑树当中 除了 有一个 控制 取出不同key 的方式的仿函数之外还有一个 控制比较方式的仿函数这样就控制在 内部了树一层。 看一个例子就明白了 如上述的 find函数当中的比较就是 _data 和 key 的比较而在 insert当中的比较就是 _data 和 _data 的比较两种比较的方式就不一样的不能单独的直接写死如果我又想用仿函数去控制的话那么比较的方式这么多得写多少仿函数。 所以库当中使用的是 两种 仿函数一个吧 key 值取出的方式set 和 map 不同取出然后直接在外部比较 key 值就行了而且只用控制 除了 取出 key 值不同的之外的 比较方式。如大于小于的不同和 key value的比较方式
u而 set 当中的 返回的就是 key 其实 本身就是可以比较的但是为了和 map 构成泛型要多调用一次仿函数。 如上图所示是库当中 红黑树的 模版参数发现还有一个 Compare 参数这个就是用来控制比较方式的 仿函数。
红黑树的代码
#pragma once
#includeiostream
using namespace std;// 节点的颜色
enum Colour
{RED,BLACK
};templateclass T
struct RBTreeNode
{RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;T _data;Colour _col;RBTreeNode(const T data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};templateclass T
struct __TreeIterator
{typedef RBTreeNodeT Node;typedef __TreeIteratorT Self;Node* _node;__TreeIterator(Node* node):_node(node){}T operator*(){return _node-_data;}T* operator-(){return _node-_data;}bool operator!(const Self s){return _node ! s._node;}Self operator--();Self operator(){// 此时就是最简单的情况// 直接找出该结点的右子树的最小结点if (_node-_right){// 右树的最左节点(最小节点)Node* subLeft _node-_right;while (subLeft-_left){subLeft subLeft-_left;}_node subLeft;}else //_node-_left{Node* cur _node;Node* parent cur-_parent;// 找孩子是父亲左的那个祖先节点就是下一个要访问的节点while (parent){if (cur parent-_left){break; // 说明已经找到parent此时就是下一次需要迭代的结点}// 如果程序走到这里该结点和 父亲结点的左右子树都遍历完了// 就要往上迭代// 直到找到 父亲 的右子树没有找完的情况else //cur parent-_right{cur cur-_parent;parent parent-_parent;}}_node parent;}return *this;}
};// set-RBTreeK, K, SetKeyOfT _t;
// map-RBTreeK, pairK, V, MapKeyOfT _t;// 红黑树节点的定义
templateclass K, class T, class KeyOfT
struct RBTree
{typedef RBTreeNodeT Node;
public:typedef __TreeIteratorT iterator;// const_iteratoriterator begin(){Node* leftMin _root;// 加上 subleft 这个条件是为了防止 这棵树是空while (leftMin leftMin-_left){leftMin leftMin-_left;}return iterator(leftMin);}iterator end(){// end不用像上述一样 找最大值// 通过迭代器当中的 operator函数我们知道中序最后都是遍历到 nullptr 的// 这个 nullptr就是 根结点的父亲指针指向的 nullptrreturn iterator(nullptr);}Node* Find(const K key){Node* cur _root;KeyOfT kot;while (cur){if (kot(cur-_data) key){cur cur-_right;}else if (kot(cur-_data) 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;KeyOfT kot;while (cur){// 如果当前新插入的 key 值比 当前遍历的结点 key 值大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 false;}}// 此时已经找到 应该插入的位置cur new Node(data);cur-_col RED;// 再次判断大小判断 cur应该插入到 parent 的那一边if (kot(parent-_data) kot(data)){parent-_right cur;}else{parent-_left cur;}// 链接 新插入结点 cur 的_parent 指针cur-_parent parent;// 红黑树调整高度平衡高度的逻辑while (parent parent-_col RED){// parent 为 红parent-_parent 一定不为空Node* grandfather parent-_parent;// 如果父亲是在 祖父的左if (parent grandfather-_left){Node* uncle grandfather-_right;// u存在且为红if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续向上处理cur grandfather;parent cur-_parent;}else // u不存在 或 存在且为黑{if (cur parent-_left){// g// p// cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;// 不需要再往上更新}}else // parent grandfather-_right{Node* uncle grandfather-_left;// u存在且为红if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续向上处理cur grandfather;parent cur-_parent;}else// 不存在 或者 存在且为黑色{if (cur parent-_right){// g// p// cRotateL(grandfather);grandfather-_col RED;parent-_col BLACK;}else{// g// p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}// 不管上述如何修改红黑树的根结点永远是黑的// 所以我们这里既直接硬性处理_root-_col BLACK;return true;}void RotateL(Node* parent){Node* cur parent-_right; // 存储 parent 的右孩子Node* curleft cur-_left; // 存储 cur 的左孩子parent-_right curleft;if (curleft) // 判断 cur 的左孩子是否为空{curleft-_parent parent; // 不为空就 修改 cur 的左孩子的_parent 指针}cur-_left parent;// 留存一份 根结点指针Node* ppnode parent-_parent;parent-_parent cur;// 如果parent 是根结点if (parent _root){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}}void RotateR(Node* parent){Node* cur parent-_left;Node* curRight cur-_right;parent-_left curRight;if (curRight){curRight-_parent parent;}cur-_right parent;Node* ppnode parent-_parent;parent-_parent cur;if (parent _root){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}}bool CheckColor(Node* root, int blacknum, int benchamark){// 当走到叶子结点的 null 指针处也就是 NIL结点处if (root nullptr){// 如果计算出的路径黑色结点长度 和 外部计算的不一样// 说明不是红黑树if (blacknum ! benchamark){cout 路径黑色结点个数不一样 endl;return false;}return true;}// 用于递归计算 路径的黑色结点个数if (root-_color BLACK)blacknum;// 如果当前结点为 红色且当前结点的父亲也是红色就不是红黑树if (root-_parent root-_parent-_color RED root-_color RED){cout 有连续红色 endl;return false;}// 左右子树递归return CheckColor(root-_left, blacknum, benchamark) CheckColor(root-_right, blacknum, benchamark);}// 外部调用接口bool isBalance(){return isBalance(_root);}// 内部封装函数bool isBalance(Node* root){if (root nullptr)return true;// 如果整棵树的 根结点不是 黑色的就不是红黑树if (root-_color ! BLACK){cout 根结点不是黑色 endl;return false;}// 基准值// 在递归外部计算出左路第一条路径的 黑色结点值int benchmark 0;Node* cur root;while (cur){if (cur-_color BLACK)benchmark;cur cur-_left;}return CheckColor(root, 0, benchmark);}
private:Node* _root nullptr;
}; 红黑树的迭代器 二叉搜索树的遍历无非就是 中序遍历但是在迭代器实现当中还有 operator和 operator--这些函数比如说 该如何实现呢 框架和一些简单函数实现
// 红黑树迭代器的实现
templateclass T
struct __Treeiterator
{typedef RBTreeNodeT Node;typedef __TreeiteratorT Self;Node* _node;T operator*(){return _node-_data;}T* operator-(){return _node-_data;}bool operator!(const Self s){return _node s._node;}
} begin 和 end 一个迭代器的基本使用方式无非就是下述的使用方式 那么首先我们要找到 begin和 end指向的位置。begin在二叉搜索树当中就是中序遍历结果 第一个值那么就是 这个树当中的最小值所以就是 这棵树的最左边那个结点的值而 edn就是 最右边的结点的值了。
end不用像上述一样 找最大值通过迭代器当中的 operator函数我们知道中序最后都是遍历到 nullptr 的这个 nullptr就是 根结点的父亲指针指向的 nullptr。 typedef __TreeiteratorT iterator;iterator begin(){Node* subleft _root;// 加上 subleft 这个条件是为了防止 这棵树是空while (subleft subleft-left){subleft subleft-_left;}return iterator(subleft);}iterator end(){// end不用像上述一样 找最大值// 通过迭代器当中的 operator函数我们知道中序最后都是遍历到 nullptr 的// 这个 nullptr就是 根结点的父亲指针指向的 nullptrreturn iterator(nullptr);} operator函数
而对于函数如下图所示 假设 it 此时是指向 8 的那么此时要对 it迭代器 那么就应该去找 8 的右子树的最小结点也就是右子树的 最左结点。 如果 it 指向 5 此时 it迭代器要 就要分两种情况因为中序的是左子树 根 右子树所以看 右子树是否为空
右不为空就要去访问右子树当中最左边的结点最小结点。
右不为空此时说明该结点已经访问完了要访问祖先注意不是 不一定是父亲应为此时 该结点可能为父亲的左 也有可能为 父亲的右如果为父亲的左说明 父亲还没有访问结束那么就访问父亲如果 该结点是父亲的右说明父亲已经访问完了此时就要访问父亲的父亲。 operator函数代码
Self operator(){// 此时就是最简单的情况// 直接找出该结点的右子树的最小结点if (_node-_right){Node* subleft _node-_right;while (subleft-_left){subleft subleft-_left;}_node subleft;}else //_node-_left{Node* cur _node;Node* parent cur-_parent;while (parent){if (cur parent-_left){break; // 说明已经找到parent此时就是下一次需要迭代的结点}// 如果程序走到这里该结点和 父亲结点的左右子树都遍历完了// 就要往上迭代// 直到找到 父亲 的右子树没有找完的情况else //cur parent-_right{cur cur-parent;parent parent-_parent;}}_node parent;}} 模拟实现set
insert
直接套用 红黑树当中的 insert函数 public:bool insert(const T key){// 因为底层是哟个红黑树实现的直接套用红黑树的 插入return _t.insert(key);} 迭代器 因为set 和 map 的底层都是用红黑树来实现的在红黑树当中已经实现了 迭代器那么我们完全可以使用 红黑树当中的迭代器来复用在 set 和 map 当中。
public:typedef typename RBTreeK, K, SetKeyOfT::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();} 注意上述 使用了 typename 关键字修饰 是因为RBTreeK, K, SetKeyOfT 是一个模版模版是没有实例化的也就是说此时在模版当中的代码是没有进行编译的那么里面除了可能会出现错误的情况下在模版当中的 很多使用了模版参数的地方还没有进行实例化替换那么此时编译器在 set 当中就会找不到 RBTree 类当中 typedef 出来的 iterator。 而且set 当中只存储 key 所以不允许利用 *it 10 这样的方式来对 set 当中的key 进行修改。
库当中的实现方式非常简单就是无论是否是 const 的 迭代器都 认为是 const 的迭代器也就是说其实 在 set 当中就一个迭代器只有一个 const 的迭代器 模拟实现 map
insert public:bool insert(const T key){// 因为底层是哟个红黑树实现的直接套用红黑树的 插入return _t.insert(key);}
迭代器 public:typedef typename RBTreeK, pairK, V, MapKeyOfT::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}
map 当中 允许修改 value 但是不允许修改 key 所以map 当中不能像 set 当中一样只实现一个 const 迭代器在map 当中的迭代器还是正常的 map 是在存储层解决这个问题的 他的 T 都是好的但是key 是 const 的。
意思就是当我们在外部取到 first 的时候这个 first 就是一个 const 修饰的值不能进行修改了;
