网站备案 新增接入,2017国外优秀网站模版,网上廊坊,地推团队一、封装思路
在 STL 中 map set 的底层就是封装了一棵红黑树。
其中连接红黑树和容器的是迭代器#xff0c;map set 暴露出的接口都不是自己写的#xff0c;而是红黑树写的#xff0c;外部接口封装红黑树接口。
所以写出红黑树为 map set 写的接口#xff0c;再在上层的…一、封装思路
在 STL 中 map set 的底层就是封装了一棵红黑树。
其中连接红黑树和容器的是迭代器map set 暴露出的接口都不是自己写的而是红黑树写的外部接口封装红黑树接口。
所以写出红黑树为 map set 写的接口再在上层的 map set 类中包装一下即可。
之前的红黑树就是单纯的在树上插入节点为了实现 map set 就需要红黑树再实现迭代器。
二、红黑树细节实现
1、迭代器
本质就是封装了一个节点用于遍历红黑树找到目标值。
1整体设计
与链表迭代器一样需要迭代器重载解引用和箭头所以模板依旧设计成
templateclass T, class Ref, class Ptr来适应 const 迭代器的复用。
2重载解引用
// 解引用迭代器是取数据
Ref operator*()
{return _node-_data;
}
3重载箭头
// 取数据的地址
Ptr operator-()
{return (_node-_data);
}
4重载不等于
bool operator!(const Self it)
{return _node ! it._node;
}
5后置
// 1.如果右子树存在访问右子树的最左节点
// 2.如果右子树不存在如果我是父亲的左那就访问父亲
// 如果我是父亲的右表示父亲也完了向上判断直到是左孩子
Self operator()
{if (_node-_right){Node* cur _node-_right;while (cur-_left)cur cur-_left;_node cur;}else{Node* cur _node;while (cur-_parent cur cur-_parent-_right)cur cur-_parent;_node cur-_parent;}return *this;
}
6后置--
// 1.如果左子树存在返回左子树的最右节点
// 2.如果左子树不存在如果是父亲的右孩子返回根
// 如果是父亲的左孩子向上找直到是右孩子
Self operator--()
{Node* cur _node;if (_node-_left){while (cur-_right)cur cur-_right;_node cur;}else{while (cur cur cur-_parent-_left)cur cur-_parent;_node cur-_parent;}return *this;
}
2、红黑树
到这里迭代器已经实现完毕要把裸的迭代器实现出不同的形式花样就是在红黑树这一层实现的。
1整体设计
从这里开始就要考虑如何把容器与红黑树相关联。
难点一 map 是 kv 模型set 是 key 模型类型都不一样怎么防止在一份红黑树代码中参数的冲突
库里面的解决办法是templateclass K, class T
这里的 T 是存放的数据类型即 map 是 pairK, Vset 是 K这样至少能传入正确的参数了。
但是红黑树主要功能插入删除的比较参数是 key所以直接传入的参数 T 用于比较map 的 pairK, V 比较逻辑是 K 大的就返回K 不大就 V 大的返回显然不符合比较逻辑是不行的我们需要都是比较 K所以还需要一个内部类提取 map set 的 key 值。
所以最终的红黑树模板参数如下
templateclass K, class T, class KeyOfTK 是 key 的类型T 是容器存储的数据类型KeyOfT 是分别在 map 和 set 中实现的内部类分别提取其中的 key 用于插入删除函数的比较。
难点二
迭代器分为 const 迭代器和非 const 迭代器所以在红黑树中也要封装。
不用写两份迭代器代码之前迭代器的模板参数就起作用了其实 const 和非 const 的区别就是指向的内容不能修改就是解引用和箭头的重载返回值不能被修改利用模板实例化就能解决问题
// 红黑树中定义两个迭代器模板参数不同即可
typedef __RBTreeIteratorT, T, T* Iterator;
typedef __RBTreeIteratorT, const T, const T* ConstIterator;
2构造析构
由于已经要和容器接轨了所以要考虑深浅拷贝问题这里封装了常见的默认成员函数
RBTree() default; // 由于已经写了拷贝构造强制生成默认构造// 私有的概念只针对于类外类内可以访问其他对象的私有成员
RBTree(const RBTreeK, T, KeyOfT tree)
{_root Copy(tree._root);
}RBTreeK, T, KeyOfT operator(RBTreeK, T, KeyOfT tree)
{swap(_root, tree._root);
}~RBTree()
{Destroy(_root);_root nullptr;
}
3迭代器封装
在迭代器类中已经处理了迭代器的使用逻辑在红黑树这一层就是封装容器的迭代器常用功能
Iterator begin()
{Node* leftMin _root;while (leftMin leftMin-_left)leftMin leftMin-_left;return leftMin;
}Iterator end()
{return Iterator(nullptr);
}ConstIterator begin() const
{Node* leftMin _root;while (leftMin leftMin-_left)leftMin leftMin-_left;return leftMin;
}ConstIterator end() const
{return ConstIterator(nullptr);
}
注意 const 迭代器函数后面需要加 const 构成函数重载。
4insert 改造
和库里面保持一致插入函数返回插入元素的迭代器和是否插入成功的 pair
为了比较的正确性要利用内部类 KeyOfT 来取出数据的 key 进行比较
pairIterator, bool insert(const T data)
{if (_root nullptr){_root new Node(data);_root-_col BLACK;return {_root, true};}Node* cur _root;Node* parent cur;KeyOfT kot;// 1.像搜索二叉树一样插入节点curwhile (cur){if (kot(cur-_data) kot(data)){parent cur;cur cur-_left;}else if (kot(cur-_data) kot(data)){parent cur;cur cur-_right;}elsereturn {cur, false};}cur new Node(data);Node* newnode cur;if (kot(parent-_data) kot(data))parent-_right cur;elseparent-_left cur;cur-_parent parent;// 新插入是红色如果父亲是黑色就没事while (parent parent-_col RED){Node* g parent-_parent;Node* uncle parent g-_left ? g-_right : g-_left;// 情况一叔叔存在且为红u p 变黑g变红向上if (uncle uncle-_col RED){uncle-_col parent-_col BLACK;g-_col RED;cur g;parent cur-_parent;}// 情况二叔叔存在且为黑或叔叔不存在else{// u parent cur 的位置决定的是左右单旋双旋// gB pB// pR u - cR gR// cR uif (cur parent-_left parent g-_left){RotateR(g);parent-_col BLACK;g-_col RED;}// gB gB cB// pR u - cR u - pR gR// cR pR uelse if (cur parent-_right parent g-_left){RotateL(parent);RotateR(g);cur-_col BLACK;g-_col RED;}// gB pB// u pR - gR cR// cR u else if (cur parent-_right parent g-_right){RotateL(g);g-_col RED;parent-_col BLACK;}// gB gB cB// u pR - u cR - gR pR// cR pR u else if (cur parent-_left parent g-_right){RotateR(parent);RotateL(g);cur-_col BLACK;g-_col RED;}elseassert(false);break;}}_root-_col BLACK;return {newnode, true};
}
三、容器细节实现
首先容器的实现共性是 map set 上层确确实实只传入 K, V 和 K是底层红黑树为了适应容器底层红黑树的实例化是 K, pairK, V, KeyOfT 和 K, K, KeyOfT
其次两者都要实现各自的 KeyOfT 内部类来告诉底层红黑树要怎么取到 key 值。
最后容器封装底层红黑树写好的迭代器代码交给外部使用。
1、set 实现
templateclass K
class set
{struct SetKeyOfT{const K operator()(const K key){return key;}};
public:typedef typename RBTreeK, const K, SetKeyOfT::Iterator iterator;typedef typename RBTreeK, const K, SetKeyOfT::ConstIterator 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();}iterator find(const K key){return _t.find(key);}pairiterator, bool insert(const K key){return _t.insert(key);}
private:RBTreeK, const K, SetKeyOfT _t;
};
2、map 实现
templateclass K, class V
class map
{struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};
public:typedef typename RBTreeK, pairconst K, V, MapKeyOfT::Iterator iterator;typedef typename RBTreeK, pairconst K, V, MapKeyOfT::ConstIterator 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();}iterator find(const K key){return _t.find(key);}pairiterator, bool insert(const pairK, V kv){return _t.insert(kv);}V operator[](const K key){pairiterator, bool ret _t.insert({ key, V() });return ret.first-second;}
private:RBTreeK, pairconst K, V, MapKeyOfT _t;
};
值得一提的是 map 还要重载 []其实现逻辑已经在博客map和set-CSDN博客解释过。
