网站后台更新无法在网页显示,潮流资讯类网站建设策划,网站专题设计软件,泰安网站建设方案书文章目录 前言一、STL源码分析二、红黑树的构建三、map与set整体框架的搭建与解析四、如何取出进行比较#xff1f;1. met与set的数据是不同的2. 取出数据进行比较1#xff09;问题发现2#xff09;仿函数解决 五、封装插入六、迭代器的实现1. operator* 与operator-2. … 文章目录 前言一、STL源码分析二、红黑树的构建三、map与set整体框架的搭建与解析四、如何取出进行比较1. met与set的数据是不同的2. 取出数据进行比较1问题发现2仿函数解决 五、封装插入六、迭代器的实现1. operator* 与operator-2. operator!3. operator4. operator- -5. 套用普通迭代器 七、const迭代器八、查找总结 前言
之前我们学习了红黑树的实现现在我们一起来看一看如何使用红黑树封装出set与map~~~ 一、STL源码分析
我们一起来分析分析STL源码看一看库中是如何实现的 首先库里面stl_set与stl_map中
对于set来说key_type是keyvalue_type也是key也就是说set是一个rbTreeKey, Key的模型。
对于map来说key_type是key但是value_type是pairconst key, T也就是说map是一个rbTreeKey, pairKey, Value的模型。
我们再来看一下rb_tree的结构 rb_tree中前两个参数是key, value而__rb_tree_nodevalue里面的参数传的是value因此我们可以总结出这里map的结点中存储的是pairkey, value而set的结点中存储的是key。 那么到底为什么是这样的结构呢 我们将在下面的讲解中逐一解释 二、红黑树的构建
对于红黑树的构建J桑之前的文章有详细的讲解因此这里就直接给出代码啦还不清楚的观众老爷门可以点击下方的传送门
深入探索C红黑树原理与实现
当然我们之前红黑树是默认存储pair现在要同时满足map与set因此一些地方需要改变之后总结的时候会给出完整的更改后的代码下面讲解也会被提到。
#pragma once
#includeiostreamusing namespace std;enum Colour
{RED,BLACK
};templateclass K, class V
struct RBTreeNode
{pairK, V _kv;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;Colour _col;RBTreeNode(const pairK, V kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}
};templateclass K, class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:bool Insert(const pairK, V kv){// 树为空直接插入然后返回if (_root nullptr){_root new Node(kv);// 根节点必须是黑色_root-_col BLACK;return true;}Node* cur _root;Node* parent nullptr;while (cur){// 小于往左走if (kv.first cur-_kv.first){parent cur;cur cur-_left;}else if (kv.first cur-_kv.first) // 大于往右走{parent cur;cur cur-_right;}else{return false;}}cur new Node(kv);// 其他结点初始颜色为红色cur-_col RED;// 链接if (cur-_kv.first parent-_kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;// 如果我们parent是黑色不用处理就结束了// 情况一cur为红parent为红grandfather为黑uncle不确定// 用while循环是因为我们要不断的向上调整while (parent parent-_col RED){// 首先我们要找到grandfatherNode* grandfather parent-_parent;// 接下来通过grandfather找到uncle//如果parent是grandfather-_leftif (parent grandfather-_left){// 说明uncle在右边Node* uncle grandfather-_right;// uncle存在且为红if (uncle uncle-_col RED){// 满足上述情况开始调整颜色parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;// 继续向上调整cur grandfather;parent cur-_parent;// 但是走到这里有一个问题如果当前parent就是根// 并且parent是红色我们要把它变为黑色// 处理方式是出循环后暴力将_root-_col变为黑色}else // uncle不存在 或 uncle存在且为黑色{// 判断要怎样旋转// 右单旋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) // 如果parent是grandfather-_right{// 说明uncle在左边Node* uncle grandfather-_left;// uncle存在且为红if (uncle uncle-_col RED){// 满足上述情况开始调整颜色parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;// 继续向上调整cur grandfather;parent cur-_parent;}else // uncle不存在 或 uncle存在且为黑色{// 判断要怎样旋转// 左单旋if (cur parent-_right){// g// p// cRotateL(grandfather);// 调整颜色parent-_col BLACK;grandfather-_col RED;}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;Node* curleft cur-_left;// 重新链接parent-_right curleft;if (curleft) // 如果curleft存在{curleft-_parent parent;}cur-_left parent;Node* ppnode parent-_parent;parent-_parent cur;if (ppnode nullptr){_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 (ppnode nullptr){cur-_parent nullptr;_root cur;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}}// 检查是否构建正确bool CheckColour(Node* root, int blacknum, int benchmark){if (root nullptr){if (blacknum ! benchmark)return false;return true;}if (root-_col BLACK){blacknum;}if (root-_col RED root-_parent root-_parent-_col RED){cout root-_kv.first 出现连续红色节点 endl;return false;}return CheckColour(root-_left, blacknum, benchmark) CheckColour(root-_right, blacknum, benchmark);}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root nullptr)return true;if (root-_col ! BLACK){return false;}// 基准值int benchmark 0;Node* cur _root;while (cur){if (cur-_col BLACK)benchmark;cur cur-_left;}return CheckColour(root, 0, benchmark);}private:Node* _root nullptr;
};三、map与set整体框架的搭建与解析
代码
namespace jyf
{templateclass k, class vclass map{public:private:RBTreek, pairk, v _t;};
}namespace jyf
{templateclass kclass set{public:private:RBTreek, k _t;};
}解析
首先无论是map还是set都有两个模板参数第一个是key这个key是多存的它的作用体现在像find()这样的函数中我们后面在做解析。
这里先看第二个参数传给了RBTree的T而T就是结点中储存的东西也就是说你是set那么节点中就储存的是key, 你是map那么节点中就储存的是pairk, v。 四、如何取出进行比较
1. met与set的数据是不同的
我们要明白一个我问题met与set结点中存储的数据是不一样的因此如果节点中还存储的是pair就不对了因此我们结点之中存储的数据因该是T类型的数据如果是set就是key,如果是map就是pair。 2. 取出数据进行比较
1问题发现
再insert函数中我们之前的红黑树是这样实现的比如这个找到插入位置的逻辑 在这张图片里面我们之前使用pair但是现在对于map和set存储的数据不同因此需要用data来比较。
但是 对于map来说它的value是pair但是pair的比较逻辑能满足我们的需要吗 可以看到pair的比较逻辑是先比firstfirst一样就比second但是我们这里不需要比较secondkey_value的模型中只需要比较key不同因此我们需要一种方法重新定义我们的比较。
怎么重新比较呢 这里我们通过观察发现对于set来说它的data是key可以直接比较唯一有问题的是map因此我们采取的方式是仿函数。 2仿函数解决
我们可以多定义一个模板参数KeyOfT这个模板参数用来定义仿函数他的作用是取出Set或Map中的Key。
对于Set它的data直接就是key
struct SetKeyOfT
{const K operator()(const K key){return key;}
};对于Map它的data是一个pair我们需要pair的first也就是key
struct MapKeyOfT
{const K operator()(const pairK,V kv){return kv.first;}
};至此我们在取出数据的时候只要定义出一个对象重载operator()用()将data包起来就得到了我们想要的数据。
可以说这里set迁就了map~ 五、封装插入
完成了上述步骤我们就可以实现封装map与set的插入了~
对于set:
bool insert(const K key)
{return _t.Insert(key);
}对于map:
bool insert(const pairK,V kv)
{return _t.Insert(kv);
}插入结果 六、迭代器的实现
要实现迭代器就要先理解迭代器是怎么用的 下面是一个模板表示迭代器的使用
it s.begin();
while (it ! s.end())
{cout *it endl;it;
}为了实现这个过程我们需要重载很多东西。
我们先将框架搭出来
templateclass T
struct __TreeIterator
{typedef RBTreeNodeT Node;typedef __TreeIteratorT Self;Node* _node;__TreeIterator(Node* node):_node(node){}
};1. operator* 与operator-
RBTree中
T operator* ()
{return _node-_data;
}T* operator- ()
{return (_node-_data);
}2. operator!
bool operator! (const Self s)
{return _node ! s._node;
}3. operator
对于树的迭代器与- -就非常重要了这里有很多坑~
首先对于一个红黑树他走的是中序的排序图如下 那么it.begin()是谁呢 我们说中序是左-根-右也就是说begin应该是上图中的1。
其次如果我们进行操作迭代器会到那里去呢 这里分以下几种情况
如果右不为空
那么下一个访问的将是右树的最左 如果右为空
这里又分两种情况 cur是parent的左——下一个访问parent cur是parent的右——下一个访问没有被访问的祖先
通过观察这两种情况我们可以发现 也就是说当右为空的时候下一个访问的是孩子是父亲的左侧的那一个祖先。 代码总结
Self operator ()
{if (_node-_right ! nullptr){Node* curleft _node-_right;while (curleft-_left){curleft curleft-_left;}_node curleft;}else{// 找孩子是父亲左的那个祖先节点就是下一个要访问的节点Node* cur _node;Node* parent _node-_parent;while (parent){if (parent-_left cur){break;}else{cur parent;parent parent-_parent;}}_node parent;}return *this;
}4. operator- -
原理与是一样的只不过原本的顺序是中序即左-根-右- - 是反过来的因此是右-根-左
Self operator--(){if (_node-_left){Node* subRight _node-_left;while (subRight-_right){subRight subRight-_right;}_node subRight;}else{// 孩子是父亲的右的那个节点Node* cur _node;Node* parent cur-_parent;while (parent cur parent-_left){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;}5. 套用普通迭代器
RBTree中
经过前面的分析begin就是树最左边的结点end我们设置为nullptr。 typedef __TreeIteratorT iterator;
public:iterator begin(){Node* leftMin _root;while (leftMin leftMin-_left){leftMin leftMin-_left;}return iterator(leftMin);}iterator end(){return iterator(nullptr);}set与map中我们要封装这个方法
iterator begin(){return _t.begin();}iterator end(){return _t.end();}测试普通迭代器
jyf::mapint, int m;
m.insert(make_pair(1, 1));
m.insert(make_pair(3, 3));
m.insert(make_pair(2, 2));jyf::mapint, int::iterator mit m.begin();while (mit ! m.end())
{mit-first 1;mit-second 2;cout mit-first : mit-second endl;mit;
}
cout endl;for (const auto kv : m)
{cout kv.first : kv.second endl;
}
cout endl;jyf::setint s;
s.insert(5);
s.insert(2);
s.insert(2);
s.insert(12);
s.insert(22);
s.insert(332);
s.insert(7);auto it s.begin();
while (it ! s.end())
{// Ӧif (*it % 2 0){*it 10;}cout *it ;it;
}
cout endl;for (const auto e : s)
{cout e ;
}
cout endl;结果为 七、const迭代器
我们知道set是不允许修改的map的key不允许修改而value允许修改再通过观察库中的实现我们可以发现:
set实现不能修改的原因是——interator迭代器与const_iterator都是const迭代器。
而map实现key不能修改value可以修改的方法是在定义map的value的时候pairK, V修改为pairconst K, V
具体的逻辑我们下一次在进行讲解~ 八、查找
查找是通过key来查找的而不是通过value来查找的这也就解释了为什么最开始定义模板参数还要多定义一个key。
同样为了取出对应的值我们也需要仿函数来包上data。
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;
}总结
红黑树在 STL 的应用 set 与 map 的实现
set 节点存储 keyrbTreeKey, Key 模型。
map 节点存储 pairconst Key, TrbTreeKey, pairKey, Value 模型。
rbTree 的设计 节点使用 __rb_tree_nodevalue 的具体含义根据容器类型不同而不同。
