如何制作一个网页网站,怎样运营网站,电商app开发多少钱,wordpress无法保存pages好了#xff0c;上次我们了解完了AVL平衡树和红黑树之后#xff0c;我们就可以去了解关于map与set的底层实现原理了。
全局观STL的操作#xff1a; 我们先来看看STL中是如何利用红黑树进行对map与set的实现的#xff1f; 从上面我们可以看到#xff1a; 为了实现一颗红黑…好了上次我们了解完了AVL平衡树和红黑树之后我们就可以去了解关于map与set的底层实现原理了。
全局观STL的操作 我们先来看看STL中是如何利用红黑树进行对map与set的实现的 从上面我们可以看到 为了实现一颗红黑树即可map又可set即即可key结构也可K,V结构这取决于 第二个模板参数你传什么能不能只传Value不传Key传第二个模板参数不传第一个模板参数 不能因为当find接口时对于set没问题set的value就是Key但对于map不能。 所以为了统一适配要传两个模板参数。但实际上set是一个模板参数map是两个模板参数。 psKey与pair中的Key是同一类型 set的模拟实现set是一个模板参数 typedef Key key_type; typedef Key value_type; 那么有人又会想它会不会存在树被修改的问题 答案不存在的因为你并不会动这棵树你只是动map与set而已接触不了树的那层。 看上面的图K是为了让find接口更加好搞T是为了决定树的结点里面存什么。 好了上面了解库的大概实现的方式后现在我们来实现一下
自己模拟 ps这里我们会采用set与map两者之间的对比差异结合来实现即同一部分的放在一起并不会像之前那样set与map分开来实现。 红黑树创建结点和颜色管理 红黑树部分跟上一篇的差不多只不过这里改了_kv类型改了一下 我们上一篇的是以pairK,V _kv,而现在改成了T _data 这里可以认为在红黑树这一层它走了一个泛型以前实现红黑树都是确定的是pairK,V类型而现在是不确定的而是通过一个模板来接受它的类型。 这里的本意就是想要通过模板来使红黑树实例化出来两份一份是K,K,一份是K,pairK,V enum Color
{BLACK,RED
};templateclass T
struct RBTreeNode
{RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;T _data;Color _col;RBTreeNode(const T data):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){ }};
构建其成员变量
ps有些模板参数后面会讲可暂时先不用管。
红黑树部分
templateclass K,class T,class KeyOFT
class RBTree
{typedef RBTreeNodeT Node;public:
private:Node* _root nullptr;
}; set部分
namespace bai
{templateclass Kclass My_set{private:RBTreeK, K, SetKeyOFT _t;};
}
map部分
namespace bai
{templateclass K, class Vclass My_map{private:RBTreeK, pairconst K, V, MapKeyOFT _t;};
}
插入部分 1.这里如果按照上一篇的方式之间比较的话它就会行不通为什么呢 因为insert部分的比较通过上面我们知道对于set可以直接比较它的结构本质上K,K第二个模板是K而map的话它的结构是K,pairK,V,第二个模板参数是pair类型它并不可以像我们之前那样直接比较。可能有人会问那为什么不可以直接用K模板比较注意我们这里比较的是值这个K是个类型而这比较需要拿的是对象对象不确定是K还是pair所以不可以。 那么我们该怎么去解决这个问题呢这里就使用到了仿函数了。 之前我们说过仿函数是可以做到像函数一样的。 这里我们可以直接在各自那里实现一个仿函数。通过模板还传进去树的结构那里。 使用仿函数比较
set部分 struct SetKeyOFT{const K operator()(const K key){return key;}};bool insert(const K key){return _t.Insert(key);}
map部分 struct MapKeyOFT{const K operator()(const pairK, V kv){return kv.first;}};//后面我们再实现V operator[](const K key);bool insert(const pairK, V kv){return _t.Insert(kv);}完了之后就可以直接利用仿函数的使用方法通过仿函数比较insert部分里面的比较内容了。
由于代码太多了这里只展现出部分的展示如何利用上仿函数就行其余的代码跟上一篇的红黑树插入部分已经有了。
bool Insert(const T data)
{……………………………………………………KeyOfT kot;while (cur){if (kot(cur-_data) kot(data)){……………………}else if (kot(cur-_data) kot(data)){……………………}
………………
………………
} 说明为什么在红黑树中不通过KeyOfT实现比较 这样设计是为了保持KeyOfT的纯粹性。如果让KeyOfT负责比较就会失去其核心价值。我们要思考的是KeyOfT存在的真正意义是什么是为了让树结构本身更清晰。 我们的做法是使用者只需关注比较逻辑无需理会KeyOfT的具体实现。因此将两者分离只需传入比较接口即可实现功能。 迭代器部分
红黑树部分
迭代器的构造加上构造拷贝构造
templateclass T,class Ptr,class Ref
struct TreeIterator
{typedef RBTreeNodeT Node;typedef TreeIteratorT,Ptr,Ref Self;typedef TreeIteratorT, T*, T Iterator;Node* _node;TreeIterator(Node*node):_node(node){ }TreeIterator(const Iteratorit):_node(it._node){ }};
operator*
Ref operator*()
{return _node-_data;
}operator- Ptr operator-(){return _node-_data;}
operator! bool operator!(const Selfs){return _node ! s._node;}
operator bool operator(const Self s) const{return _node s._node;}
operator 讲解 1.首先我们来看一下上面的图来使我们更加清楚了解它是如何进行的 2.我们先来看一下它的总思路结合着上图一起看 1右不为空访问右树的最左结点即最小结点。 2右为空下一个要访问的孩子是父亲左的那个祖先。 Self operator(){//右树不为空找右树的最左结点即最小结点if (_node-_right){Node* subleft _node-_right;while (subleft-_left){subleft subleft-_left;}_node subleft;}//右树为空else{Node* cur _node;Node* parent cur-_parent;//找孩子是父亲左的那个祖先节点就是下一个要访问的节点while (parent curparent-_right){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;} operator-- 1.减减的思路和加加的思路相反 1左不为空访问左树的最右结点即最大结点。 2左为空下一个要访问的孩子是父亲右的那个祖先。 Self operator--(){if (_node-_left){Node* subright _node-_right;while (subright-_right){subright subright-_right;}_node subright;}else{Node* cur _node;Node* parent cur-_parent;while (parent curparent-_left){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;}
好了迭代器接口的类已经写完了现在我们利用上写的迭代器函数进行对begin(),end()等实现上去。
begin()和end函数 首先我们先来看一下库里面是如何进行实现的 库那利用了一个哨兵节点。 除了它的开销在旋转操作中为了维护父节点而付出了一定的代价。而且当在最左边或最右边插入或删除节点时也需要进行相应的维护和修改 在这里我们就不像它那样实现了复杂难 1.我们先对迭代器进行封装还是用上我们的模板 2.begin()函数的解释因为底层实现是红黑树即平衡二叉搜索树所以我们开始的结点中序遍历是左子树最左的那个值所以要进行查找遍历到左数最小的值最后返回。 3.end函数的解释直接返回迭代器为nullptr时。为什么呢返回nullptr构造的迭代器当遍历完红黑树时迭代器到达这个位置就说明遍历完了有效的元素和STL容器的迭代器使用习惯一致方便搭配基于范围for循环等遍历方式for(auto itrbtree.begin();it!end();it). 4.下面还有就是实现了const迭代器。 templateclass K,class T,class KeyOFT
class RBTree
{typedef RBTreeNodeT Node;public:typedef TreeIteratorT,T*,T iterator;iterator begin(){Node* LeftMin _root;while (LeftMin LeftMin-_left){LeftMin LeftMin-_left;}return iterator(LeftMin);}iterator end(){return iterator(nullptr);}const_iterator begin()const{Node* LeftMin _root;while (LeftMin LeftMin-_left){LeftMin LeftMin-_left;}return const_iterator(LeftMin);}const_iterator end()const {return const_iterator(nullptr);}
private:Node* _root nullptr;
};
好了红黑树里的迭代器封装我们就基本实现完成了那么现在就开始对set与map进行对迭代器模板的使用。
set迭代器 同样我们来进行实现两个迭代器分别是普通迭代器和const迭代器。 但是由上面一开始的分析我们也知道set中是不可被修改的否则就不是搜索树了。 所以普通迭代器底层对红黑树的迭代器封装时也是使用了const迭代器进行封装的从而做到不可修改。 1.注意为什么iterator begin()后面不加const不会通过编译会报错 因为不加const的话那么_t就是普通迭代器的_t普通迭代器的t就只能调用普通的begin,普通的begin()end(),返回的就是普通的iterator,普通的iterator能不能跟这个匹配不能。 那么我们只提供const版本的迭代器有没有价值呢 答案是有点反正它是不能被修改的const对象可以调用const平移普通对象也是可以调用const的缩小。因为我们说过对象可以平移或者缩小但是不可以扩大。 比如我们使用时bai::setint::iterator it_t.begin(); iterator可以转化为const_itrerator那要单独写一个构造进行转化但是typedef里的iterator还是要写的因为像我们平常的话更多习惯用的还是iterator而不是const_iterator对吧。 2.注意补充一点类模板没有实例化编译器不会去找。 内嵌类型内部类typedef 要加typename相当于给编译器吃一颗定心丸告知编译器它是合法的。具体的可以去看一下关于进阶模板的文章 //有些代码已经省略
namespace bai
{templateclass Kclass My_set{public:typedef typename RBTreeK,K,SetKeyOFT::const_iterator iterator;typedef typename RBTreeK, K, SetKeyOFT::const_iterator const_iterator;iterator begin()const{return _t.begin();}iterator end()const{return _t.end();}private:RBTreeK, K, SetKeyOFT _t;};
}
map迭代器 1.我们的map可以修改即不可以修改K可以修改Value那么我们能不能继续像刚才set那样底层都是const_iterator来保证K不变。 答不可以因为set只有一个让K不可被修改若map也用的话它不仅仅K不可改连V也不可修改了。 那么我们该怎么去做到不改变K但是改变V呢 我们可以在pair内部进行操作即在pairconst K,V,这样的话pair可以被修改但是K不可以修改了达成我们的目的 其他的做法跟我们set的差不多 namespace bai
{templateclass K, class Vclass My_map{public:typedef typename RBTreeK, pairconst K,V, MapKeyOFT::iterator iterator;typedef typename RBTreeK, pairconst K, V, MapKeyOFT::const_iterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}const_iterator begin()const{return _t.begin();}const_iterator end()const{return _t.end();}private:RBTreeK, pairconst K, V, MapKeyOFT _t;};
}
随之我们的迭代器部分的完善我们的insert部分也要进一步改善的
完善insert部分
insert部分返回值要改成pairiterator,bool
红黑树部分 讲解 1.为什么要用newnode保存一下cur呢不能直接用cur 答因为红黑树插入的过程中会有变色cur的grandfathercur可能往上走不一定是新插入的结点所以要保存一下新节点 pairiterator, bool insert(const T data){KeyOFT kot;if (_root nullptr){_root new Node(data);_root-_col BLACK;return make_pair(iterator(_root),true);}Node* cur _root;Node* parent nullptr;//Node* newnode cur;while (cur){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 make_pair(iterator(cur), false);}}cur new Node(data);//写错1Node* newnode cur;cur-_col RED;if (kot(parent-_data) kot(data)){parent-_rightcur;}else{parent-_leftcur;}cur-_parent parent;while (parent parent-_col RED){Node* grandfather parent-_parent;if (parent grandfather-_left){Node* uncle grandfather-_right;if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续向上更新cur grandfather;parent cur-_parent;}else//不存在 或者uncle为黑 旋转变色{if (cur parent-_left){// g// p//cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED; }else //curparnet-right{// g// p// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;//parent-_col BLACK;grandfather-_col RED;}break;} }else //(parent grandfather-_right){Node* uncle grandfather-_left;//Node* uncle grandfather-_right;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;//继续向上更新cur grandfather;parent cur-_parent;}else //(uncle不存在时)旋转变色{// g // p// c if (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}// g // p// celse{RotateR(parent);RotateL(grandfather);cur-_col BLACK;//parent-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return make_pair(iterator(newnode),true);}
你把树里的改了那么set与map的也要跟着改。但是这时候就会set的insert出现问题
现在我们来看一下改变的代码
set部分
pairiterator, bool insert(const K key)
{return _t.insert(key);
} set没有pair而pair又是全局的。 会出现迭代器问题 返回值的pairiterator,bool是RBTree::const_iterator 而你return的 _t.Insert(key)是pairRBTree::iterator,bool 那么我们在insert() const 行不行 不能_t是constInsert也是const,那么必须去调用const insert,那就不能够修改树的结构了所以不能 再来回顾make_pair会根据它的类型自己去推在类里面直接用iterator,本质也是const_iterator. 这里的做法是 拿一个普通迭代器去构造const迭代器 按理说迭代器不需要写拷贝构造因为编译器默认写浅拷贝。 templateclass T,class Ptr,class Ref
struct TreeIterator
{typedef RBTreeNodeT Node;typedef TreeIteratorT,Ptr,Ref Self;typedef TreeIteratorT, T*, T Iterator;Node* _node;TreeIterator(Node*node):_node(node){ }TreeIterator(const Iteratorit):_node(it._node){ }
} 但这个函数也不完全是拷贝构造因为它的返回值不是Self 。 Self与Iterator的区别Self就是这个迭代器但Iterator就不一定了。 可能听到这里有点疑惑别急让我们再来捋捋思路 _t.insert是一个普通树的对象 pairtypename RBTreeK,K,SetkeyofT::iterator,bool rett.insert() 返回的是一个普通的迭代器而set这层的iterator是const迭代器传不过去所以我们的做法是 单独用一个pair对象普通树的迭代器的对象去接受接受了以后再用这个东西去构造传参first传的是普通迭代器 那么普通迭代器为什么可以初始化const迭代器 因为const迭代器中支持了一个构造这两个pair是同一个类模板并不是同类型的。 当这个类被实例化成const迭代器时这个函数是一个构造支持普通迭代器构造const迭代器为什么 1.因为我实例化出const迭代器我自己就是const迭代器但是这个参数是iterator特点是不管你是普通迭代器还是const迭代器都是普通迭代器因为这参数传的是 typedef TreeIteratorT, T*, T Iterator; 并不受RefPtr影响。 2.当这个类被实例化成普通迭代器这个函数就是一个拷贝构造普通构造普通。 map部分 pairiterator,bool insert(const pairK, V kv){return _t.insert(kv);} 也是跟上面的一样理解。 map的operator[]部分 V operator[](const K key){pairiterator, bool ret insert(make_pair(key, V()));return ret.first-second;} 1.这是一个关联式容器 - make_pair(key, V()) 创建一个 pair 对象 first 是传入的 key second 是默认构造的 V 类型对象如果 V 是自定义类型需有默认构造函数 。 - insert(make_pair(key, V())) 调用下方自定义的 insert 函数尝试插入pair 。 insert 函数返回一个 pair 其中 first 是指向插入位置或已存在元素位置 的迭代器 second 是 bool 类型 true 表示插入成功之前无该 key false 表示已存在未插入新元素 。 - return ret.first-second 不管插入是否成功通过迭代器 ret.first 访问 pair 的 second 即对应 key 的 value 并返回其引用 大整体部分就这样了。
好的本次分享就到处结束了希望我们一起进步
最后到了本次鸡汤环节 下面图片与大家共勉
