怎样建设传奇网站空间,泰兴网站建设公司,扁平化设计 科技感网站素材,门户网站 模板一、源码及框架分析
SGI-STL30版本源代码#xff0c;map和set的源代码在map/set/stl_map.h/stl_set.h/stl_tree.h等及个头文件中。 map和set的实现结构框架核心部分截取出来如下#xff1a;
// set
#ifndef __SGI_STL_INTERNAL_TREE_H
#include stl_tree.h
#endif
…一、源码及框架分析
SGI-STL30版本源代码map和set的源代码在map/set/stl_map.h/stl_set.h/stl_tree.h等及个头文件中。 map和set的实现结构框架核心部分截取出来如下
// set
#ifndef __SGI_STL_INTERNAL_TREE_H
#include stl_tree.h
#endif
#include stl_set.h
#include stl_multiset.h
// map
#ifndef __SGI_STL_INTERNAL_TREE_H
#include stl_tree.h
#endif
#include stl_map.h
#include stl_multimap.h// stl_set.h
template class Key, class Compare lessKey, class Alloc alloc
class set {
public:// typedefs:typedef Key key_type;typedef Key value_type;
private:typedef rb_treekey_type, value_type, identityvalue_type, key_compare, Alloc rep_type;rep_type t; // red-black tree representing set
};
// stl_map.h
template class Key, class T, class Compare lessKey, class Alloc alloc
class map {
public:// typedefs:typedef Key key_type;typedef T mapped_type;typedef pairconst Key, T value_type;
private:typedef rb_treekey_type, value_type, select1stvalue_type, key_compare, Alloc rep_type;rep_type t; // red-black tree representing map
};// stl_tree.h
struct __rb_tree_node_base
{typedef __rb_tree_color_type color_type;typedef __rb_tree_node_base* base_ptr;color_type color; base_ptr parent;base_ptr left;base_ptr right;
};
// stl_tree.h
template class Key, class Value, class KeyOfValue, class Compare, class Alloc alloc
class rb_tree {
protected:typedef void* void_pointer;typedef __rb_tree_node_base* base_ptr;typedef __rb_tree_nodeValue rb_tree_node;typedef rb_tree_node* link_type;typedef Key key_type;typedef Value value_type;
public:// insert⽤的是第⼆个模板参数做形参 pairiterator,bool insert_unique(const value_type x);// erase和find⽤第⼀个模板参数做形参 size_type erase(const key_type x);iterator find(const key_type x);
protected:size_type node_count; // keeps track of size of treelink_type header;
};
template class Value
struct __rb_tree_node : public __rb_tree_node_base
{typedef __rb_tree_nodeValue* link_type;Value value_field;}• 通过下图对框架的分析我们可以看到源码中rb_tree用了一个巧妙的泛型思想实现rb_tree是实现key的搜索场景还是key/value的搜索场景不是直接写死的而是由第二个模板参数Value决定_rb_tree_node中存储的数据类型。 • set实例化rb_tree时第二个模板参数给的是keymap实例化rb_tree时第二个模板参数给的是pairconst key , T这样一颗红黑树既可以实现key搜索场景的set也可以实现key/value搜索场景的map。 • 要注意⼀下源码里面模板参数是用T代表value而内部写的value_type不是我们我们日常key/value场景中说的value源码中的value_type反而是红黑树结点中存储的真实的数据的类型。 • rb_tree第二个模板参数Value已经控制了红黑树结点中存储的数据类型为什么还要传第一个模板参数Key呢尤其是set两个模板参数是⼀样的这是很多同学这时的一个疑问。要注意的是对于map和setfind/erase时的函数参数都是Key所以第一个模板参数是传给find/erase等函数做形参的类型的。对于set而言两个参数是一样的但是对于map而言就完全不一样了map insert的是pair对象但是find和ease的是Key对象。
二、模拟实现 set 和 map
2.1 实现出符合要求的红黑树
2.1.1 iterator 与 reverse_iterator
iterator实现思路分析 • iterator实现的大框架跟list的iterator思路是一致的用一个类型封装结点的指针再通过重载运算符实现迭代器像指针一样访问的行为。 • 这里的难点是operator和operator–的实现。之前使用部分我们分析了map和set的迭代器走的是中序遍历左子树-根结点-右子树那么begin()会返回中序第一个结点的iterator也就是最左节点的迭代器。 • 迭代器的核心逻辑就是不看全局只看局部只考虑当前中序局部要访问的下一个结点。迭代器时如果it指向的结点的右子树不为空代表当前结点已经访问完了要访问下一个结点是右子树的中序第一个一棵树中序第一个是最左结点所以直接找右子树的最左结点即可如果it指向的结点的右子树空代表当前结点已经访问完了且当前结点所在的子树也访问完了要访问的下一个结点在当前结点的祖先里面所以要沿着当前结点到根的祖先路径向上找。如果当前结点是父亲的左根据中序左子树-根结点-右子树那么下一个访问的结点就是当前结点的父亲如果当前结点是父亲的右根据中序左子树-根结点-右子树当前当前结点所在的子树访问完了当前结点所在父亲的子树也访问完了那么下一个访问的需要继续往根的祖先中去找直到找到孩子是父亲左的那个祖先就是中序要遍历的下一个结点。 • end()如何表示呢stl源码中红黑树增加了一个哨兵位头结点做为end()这哨兵位头结点和根互为父亲左指向最左结点右指向最右结点。 • 迭代器–的实现跟的思路完全类似逻辑正好反过来即可因为他访问顺序是右子树-根结点-左子树。 • set的iterator也不支持修改我们把set的第二个模板参数改成const K即可 RBTreeK, const K, SetKeyOfT _t; • map的iterator不支持修改key但是可以修改value我们把map的第二个模板参数pair的第一个参数改成const K即可 RBTreeK, pairconst K, V, MapKeyOfT _t; • 至于reverse_iterator的实现和iterator类似就不多赘述具体实现看下面的代码。
通过上面的叙述我们了解到整体需要从结点的定义开始改造即定义哨兵结点。
2.1.2 改造红黑树的代码
#pragma once#includeiostream
#includeassert.h
using namespace std;
//节点颜色
enum Colour
{RED,BLACK
};//红黑树的节点
//K是用来查找的T是用来插入的
//set中T是keymap中T是pairkey,value
templateclass T
struct RBTreeNode
{T _t;//dataRBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;Colour _col;RBTreeNode(const T t T(), Colour col RED):_t(t),_left(nullptr),_right(nullptr),_parent(nullptr),_col(col){}
};
//红黑树的迭代器
templateclass T, class Ref, class Ptr
struct RBTreeIterator
{typedef RBTreeNodeT Node;Node* _node;//要操作的节点RBTreeIterator(Node* node) :_node(node) {}typedef RBTreeIterator Self;//itSelf operator(){Node* cur _node;if (cur-_right){Node* LeftMost cur-_right;while (LeftMost-_left){LeftMost LeftMost-_left;}_node LeftMost;}else{Node* parent cur-_parent;while (parent-_right cur){cur parent;parent cur-_parent;}_node parent;}return *this;}//itSelf operator(int){Self temp(*this);*this;return temp;}//--itSelf operator--(){Node* cur _node;//end()时if (_node-_parent-_parent _node _node-_col RED){_node _node-_right;}else if (cur-_left){Node* RightMost cur-_left;while (RightMost-_right){RightMost RightMost-_right;}_node RightMost;}else{Node* parent cur-_parent;while (parent-_left cur){cur parent;parent cur-_parent;}_node parent;}return *this;}//it--Self operator--(int){Self temp(*this);--*this;return temp;}Ref operator*(){return _node-_t;}Ptr operator-(){return _node-_t;}bool operator!(const Self it){return _node ! it._node;}bool operator(const Self it){return _node it._node;}
};
//红黑树的反向迭代器
templateclass T, class Ref, class Ptr
struct RBTreeReverseIterator
{typedef RBTreeNodeT Node;Node* _node;//要操作的节点RBTreeReverseIterator(Node* node) :_node(node) {}typedef RBTreeReverseIterator Self;//itSelf operator--(){Node* cur _node;if (cur-_right){Node* LeftMost cur-_right;while (LeftMost-_left){LeftMost LeftMost-_left;}_node LeftMost;}else{Node* parent cur-_parent;while (parent-_right cur){cur parent;parent cur-_parent;}_node parent;}return *this;}//itSelf operator(int){Self temp(*this);*this;return temp;}//--itSelf operator(){Node* cur _node;//end()时if (_node-_parent-_parent _node _node-_col RED){_node _node-_right;}else if (cur-_left){Node* RightMost cur-_left;while (RightMost-_right){RightMost RightMost-_right;}_node RightMost;}else{Node* parent cur-_parent;while (parent-_left cur){cur parent;parent cur-_parent;}_node parent;}return *this;}//it--Self operator--(int){Self temp(*this);--*this;return temp;}Ref operator*(){return _node-_t;}Ptr operator-(){return _node-_t;}bool operator!(const Self it){return _node ! it._node;}bool operator(const Self it){return _node it._node;}
};//红黑树
templateclass K, class T, class KeyOfT
class RBTree
{typedef RBTreeNode T Node;void destory(Node* root){if (root nullptr)return;//必须后续销毁节点destory(root-_left);root-_left nullptr;destory(root-_right);root-_right nullptr;delete root;root nullptr;}
public:RBTree(){_header new Node(T());}//拷贝构造RBTree(const RBTree rbt){_header new Node(T());for (const auto e : rbt){insert(e);}}RBTree(initializer_listT il){_header new Node(T());for (const auto e : il)insert(e);}//赋值重载RBTree operator(const RBTree bst){//现代写法RBTree temp(bst);std::swap(_header, temp._header);return *this;}// 析构~RBTree(){destory(_header-_parent);delete _header;_header nullptr;}typedef RBTreeIteratorT, T, T* iterator;typedef RBTreeIteratorT, const T, const T* const_iterator;typedef RBTreeReverseIteratorT, T, T* reverse_iterator;typedef RBTreeReverseIteratorT, const T, const T* const_reverse_iterator;//迭代器iterator begin(){return iterator(_header-_left);}const_iterator begin() const{return const_iterator(_header-_left);}iterator end(){return iterator(_header);}const_iterator end() const{return const_iterator(_header);}//反向迭代器reverse_iterator rbegin(){return reverse_iterator(_header-_right);}const_reverse_iterator rbegin()const{return const_reverse_iterator(_header-_right);}reverse_iterator rend(){return reverse_iterator(_header);}const_reverse_iterator rend()const{return const_reverse_iterator(_header);}//此时需要注意key是set中的key是map中pairkey,value中的key// 因此我们需要取出想要的keyiterator find(const K key) const{Node* cur _header-_parent;//指向根节点while (cur){if (key KeyOfT()(cur-_t)){cur cur-_left;}else if (key KeyOfT()(cur-_t)){cur cur-_right;}else{return iterator(cur);}}return iterator(_header);}pairiterator, bool insert(const T t){if (_header-_parent nullptr){_header-_parent new Node(t);_header-_parent-_col BLACK;_header-_parent-_parent _header;return { iterator(_header-_parent),true };}//查找结点Node* parent _header;Node* cur _header-_parent;while (cur){if (KeyOfT()(t) KeyOfT()(cur-_t)){parent cur;cur cur-_left;}else if (KeyOfT()(t) KeyOfT()(cur-_t)){parent cur;cur cur-_right;}else{return { iterator(cur), false };}}//插入节点cur new Node(t);cur-_parent parent;if (KeyOfT()(t) KeyOfT()(parent-_t))parent-_left cur;elseparent-_right cur;//保存cur留待返回Node* ret cur;//调整颜色//情况一parent存在且为黑不需要调整//情况二parent存在且为红需要调整while (parent ! _header parent-_col RED){//确定 g 和 u 节点Node* grandfather parent-_parent;Node* uncle nullptr;if (parent grandfather-_left)uncle grandfather-_right;elseuncle grandfather-_left;//在情况二下又有如下情况//情况1unclude存在且为红if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;//继续向上调整cur grandfather;parent cur-_parent;}//情况2uncle不存在或uncle为黑else if (!uncle || uncle-_col BLACK){//parent 是 grandfather 的左孩子if (parent grandfather-_left){//cur 是 parent 的左孩子if (cur parent-_left){//旋转加变色RotateRight(grandfather);parent-_col BLACK;grandfather-_col RED;}//cur 是 parent 的右孩子else{//旋转加变色RotateLeftThenRight(grandfather);cur-_col BLACK;grandfather-_col RED;}}//parent 是 grandfather 的右孩子else{//cur 是 parent 的左孩子if (cur parent-_left){//旋转加变色RotateRightThenLeft(grandfather);cur-_col BLACK;grandfather-_col RED;}//cur 是 parent 的右孩子else{//旋转加变色RotateLeft(grandfather);parent-_col BLACK;grandfather-_col RED;}}break;//调整好能退出了}else{assert(false);//逻辑错误理论上不可能走到}}//保证根节点必须是黑色的_header-_parent-_col BLACK;_header-_left LeftMost();_header-_right RightMost();return { iterator(ret), true };}bool empty(){return _header-_parent nullptr;}size_t size(){size_t count 0;auto it begin();while (it ! end()){count;it;}return count;}void clear(){destory(_header-_parent);_header-_parent nullptr;}
private:Node* LeftMost(){Node* MostLeftChild _header-_parent;while (MostLeftChild-_left){MostLeftChild MostLeftChild-_left;}return MostLeftChild;}Node* RightMost(){Node* MostRightChild _header-_parent;while (MostRightChild-_right){MostRightChild MostRightChild-_right;}return MostRightChild;}void RotateLeft(Node* parent){//保存节点后面链接Node* parentparent parent-_parent;Node* sub parent-_right;Node* subleft sub-_left;//重新链接parent-_right subleft;if (subleft)subleft-_parent parent;sub-_left parent;parent-_parent sub;//和上面的节点链接if (parentparent _header){//说明parent原来是根节点_header-_parent sub;sub-_parent _header;}else{if (parentparent-_left parent){//原来是上面节点的左子树parentparent-_left sub;}else{parentparent-_right sub;}sub-_parent parentparent;}}void RotateRight(Node* parent){//保存节点后面链接Node* parentparent parent-_parent;Node* sub parent-_left;Node* subright sub-_right;//重新链接parent-_left subright;if (subright)subright-_parent parent;sub-_right parent;parent-_parent sub;//和上面的节点链接if (parentparent _header){//说明parent原来是根节点_header-_parent sub;sub-_parent _header;}else{if (parentparent-_left parent){//原来是上面节点的左子树parentparent-_left sub;}else{parentparent-_right sub;}sub-_parent parentparent;}}void RotateLeftThenRight(Node* parent){RotateLeft(parent-_left);RotateRight(parent);}void RotateRightThenLeft(Node* parent){RotateRight(parent-_right);RotateLeft(parent);}
private:Node* _header;
};2.2 复用红黑树实现 set
#pragma once#includeRBTree.htemplateclass K
class set
{typedef const K T;//用以插入struct KeyOfT{const K operator()(const T key){return key;}};typedef typename RBTreeK, T, KeyOfT::iterator iterator;typedef typename RBTreeK, T, KeyOfT::const_iterator const_iterator;typedef typename RBTreeK, T, KeyOfT::reverse_iterator reverse_iterator;typedef typename RBTreeK, T, KeyOfT::const_reverse_iterator const_reverse_iterator;
public:set() default;set(initializer_listT il){_rbt { il };}//迭代器iterator begin(){return _rbt.begin();}const_iterator begin()const{return _rbt.begin();}iterator end(){return _rbt.end();}const_iterator end() const{return _rbt.end();}//反向迭代器reverse_iterator rbegin(){return _rbt.rbegin();}const_reverse_iterator rbegin()const{return _rbt.rbegin();}reverse_iterator rend(){return _rbt.rend();}const_reverse_iterator rend() const{return _rbt.rend();}bool empty(){return _rbt.empty();}size_t size(){return _rbt.size();}void clear(){_rbt.clear();}iterator find(const K key)const{return _rbt.find(key);}pairiterator, bool insert(const T t){return _rbt.insert(t);}private:RBTreeK, T, KeyOfT _rbt;
};2.3 复用红黑树实现 map
#pragma once#includeRBTree.htemplateclass K, class V
class map
{typedef pairconst K, V T;struct KeyOfT{const K operator()(const T data){return data.first;}};typedef typename RBTreeK, T, KeyOfT::iterator iterator;typedef typename RBTreeK, T, KeyOfT::const_iterator const_iterator;typedef typename RBTreeK, T, KeyOfT::reverse_iterator reverse_iterator;typedef typename RBTreeK, T, KeyOfT::const_reverse_iterator const_reverse_iterator;
public:map() default;map(initializer_listT il){_rbt { il };}//迭代器iterator begin(){return _rbt.begin();}const_iterator begin()const{return _rbt.begin();}iterator end(){return _rbt.end();}const_iterator end() const{return _rbt.end();}//反向迭代器reverse_iterator rbegin(){return _rbt.rbegin();}const_reverse_iterator rbegin()const{return _rbt.rbegin();}reverse_iterator rend(){return _rbt.rend();}const_reverse_iterator rend() const{return _rbt.rend();}bool empty(){return _rbt.empty();}size_t size(){return _rbt.size();}void clear(){_rbt.clear();}iterator find(const K key)const{return _rbt.find(key);}pairiterator, bool insert(const pairconst K, V kv){return _rbt.insert(kv);}V operator[](const K key){pairiterator, bool ret insert({ key, V() });iterator it ret.first;return it-second;}
private:RBTree K, pairconst K, V, KeyOfT _rbt;//key 不能修改
};
文章转载自： http://www.morning.tlnbg.cn.gov.cn.tlnbg.cn http://www.morning.znrlg.cn.gov.cn.znrlg.cn http://www.morning.mllmm.cn.gov.cn.mllmm.cn http://www.morning.ngcsh.cn.gov.cn.ngcsh.cn http://www.morning.skfkx.cn.gov.cn.skfkx.cn http://www.morning.jrtjc.cn.gov.cn.jrtjc.cn http://www.morning.wbysj.cn.gov.cn.wbysj.cn http://www.morning.nlmm.cn.gov.cn.nlmm.cn http://www.morning.mgwpy.cn.gov.cn.mgwpy.cn http://www.morning.qphcq.cn.gov.cn.qphcq.cn http://www.morning.pttrs.cn.gov.cn.pttrs.cn http://www.morning.yjprj.cn.gov.cn.yjprj.cn http://www.morning.qxnns.cn.gov.cn.qxnns.cn http://www.morning.sffwz.cn.gov.cn.sffwz.cn http://www.morning.qyjqj.cn.gov.cn.qyjqj.cn http://www.morning.lhxrn.cn.gov.cn.lhxrn.cn http://www.morning.hcrxn.cn.gov.cn.hcrxn.cn http://www.morning.chtnr.cn.gov.cn.chtnr.cn http://www.morning.yskhj.cn.gov.cn.yskhj.cn http://www.morning.wjhnx.cn.gov.cn.wjhnx.cn http://www.morning.qzpkr.cn.gov.cn.qzpkr.cn http://www.morning.wmlby.cn.gov.cn.wmlby.cn http://www.morning.yfstt.cn.gov.cn.yfstt.cn http://www.morning.xwzsq.cn.gov.cn.xwzsq.cn http://www.morning.kklwz.cn.gov.cn.kklwz.cn http://www.morning.ffptd.cn.gov.cn.ffptd.cn http://www.morning.yckrm.cn.gov.cn.yckrm.cn http://www.morning.kpbgp.cn.gov.cn.kpbgp.cn http://www.morning.kxryg.cn.gov.cn.kxryg.cn http://www.morning.kgsws.cn.gov.cn.kgsws.cn http://www.morning.rkdnm.cn.gov.cn.rkdnm.cn http://www.morning.rlpmy.cn.gov.cn.rlpmy.cn http://www.morning.pbygt.cn.gov.cn.pbygt.cn http://www.morning.pxrfm.cn.gov.cn.pxrfm.cn http://www.morning.rlkgc.cn.gov.cn.rlkgc.cn http://www.morning.bsqkt.cn.gov.cn.bsqkt.cn http://www.morning.neletea.com.gov.cn.neletea.com http://www.morning.jcnmy.cn.gov.cn.jcnmy.cn http://www.morning.xbzfz.cn.gov.cn.xbzfz.cn http://www.morning.fstdf.cn.gov.cn.fstdf.cn http://www.morning.rjmd.cn.gov.cn.rjmd.cn http://www.morning.fwqgy.cn.gov.cn.fwqgy.cn http://www.morning.lnrr.cn.gov.cn.lnrr.cn http://www.morning.rxfjg.cn.gov.cn.rxfjg.cn http://www.morning.znsyn.cn.gov.cn.znsyn.cn http://www.morning.qztdz.cn.gov.cn.qztdz.cn http://www.morning.tsflw.cn.gov.cn.tsflw.cn http://www.morning.tkchg.cn.gov.cn.tkchg.cn http://www.morning.rsjng.cn.gov.cn.rsjng.cn http://www.morning.zqwp.cn.gov.cn.zqwp.cn http://www.morning.sgpnz.cn.gov.cn.sgpnz.cn http://www.morning.rcrfz.cn.gov.cn.rcrfz.cn http://www.morning.tqrjj.cn.gov.cn.tqrjj.cn http://www.morning.rcqyk.cn.gov.cn.rcqyk.cn http://www.morning.beijingzy.com.cn.gov.cn.beijingzy.com.cn http://www.morning.nj-ruike.cn.gov.cn.nj-ruike.cn http://www.morning.jzyfy.cn.gov.cn.jzyfy.cn http://www.morning.xgcwm.cn.gov.cn.xgcwm.cn http://www.morning.gwtbn.cn.gov.cn.gwtbn.cn http://www.morning.rklgm.cn.gov.cn.rklgm.cn http://www.morning.wsyst.cn.gov.cn.wsyst.cn http://www.morning.qnzld.cn.gov.cn.qnzld.cn http://www.morning.rymb.cn.gov.cn.rymb.cn http://www.morning.mjqms.cn.gov.cn.mjqms.cn http://www.morning.ghrlx.cn.gov.cn.ghrlx.cn http://www.morning.pmbcr.cn.gov.cn.pmbcr.cn http://www.morning.gyfhk.cn.gov.cn.gyfhk.cn http://www.morning.ltzkk.cn.gov.cn.ltzkk.cn http://www.morning.mcjp.cn.gov.cn.mcjp.cn http://www.morning.qgjp.cn.gov.cn.qgjp.cn http://www.morning.ghkgl.cn.gov.cn.ghkgl.cn http://www.morning.gktds.cn.gov.cn.gktds.cn http://www.morning.hslgq.cn.gov.cn.hslgq.cn http://www.morning.wjhdn.cn.gov.cn.wjhdn.cn http://www.morning.skmzm.cn.gov.cn.skmzm.cn http://www.morning.bpmnc.cn.gov.cn.bpmnc.cn http://www.morning.c7629.cn.gov.cn.c7629.cn http://www.morning.xsklp.cn.gov.cn.xsklp.cn http://www.morning.ylkkh.cn.gov.cn.ylkkh.cn http://www.morning.pzbjy.cn.gov.cn.pzbjy.cn
