请简述网站建设的方法,电商网站开发的主流技术,百度框架户开户渠道代理,白名单 网站map和set的封装一、介绍二、stl源码剖析三、仿函数获取数值四、红黑树的迭代器五、map的[]5.1 普通迭代器转const迭代器六、set源码七、map源码八、红黑树源码一、介绍
首先要知道map和set的底层都是用红黑树实现的 【数据结构】红黑树 set只需要一个key#xff0c;但是map既…
map和set的封装一、介绍二、stl源码剖析三、仿函数获取数值四、红黑树的迭代器五、map的[]5.1 普通迭代器转const迭代器六、set源码七、map源码八、红黑树源码一、介绍
首先要知道map和set的底层都是用红黑树实现的 【数据结构】红黑树 set只需要一个key但是map既有key也有val。 那么我们怎么同时兼容呢
二、stl源码剖析 从这张图可以看出红黑树的节点里面存的类型是由Value决定的跟Key无关。
所以我们实现的时候就可以给RBTree添加一个模板参数
templateclass K, class T
class RBTreeT模板参数我们既可以传K也可以传pairk, V map
template class K
class set
{
private:RBTreeK,K _t;
};set
template class K, class V
class map
{
private:RBTreeK, pairconst K,V _t;
};既然通过第二个参数就能确定节点的类型那么第一个参数有什么用呢? 当我们查找的时候如果是map第二个参数就是pair类型不能使用所以得加上第一个参数方便查找。 参照stl的方法定义节点
template class T
struct RBTreeNode
{RBTreeNode(const T data): _data(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}T _data;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;Colour _col;
};三、仿函数获取数值
我们知道红黑树是搜索树插入的时候需要比较大小而我们插入的有可能是K也有可能是pairK, V导致我们无法直接比较。
而stl的做法就是利用仿函数获取我们需要进行比较的元素。 set
template class K
class set
{struct SetKeyOfT{const K operator()(const K k){return k;}};
public:
private:RBTreeK, K, SetKeyOfT _t;
};map
template class K, class V
class map
{struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};
public:
private:RBTreeK, pairK, V, , MapKeyOfT _t;
};进行大小比较
KeyOfT kot;// 仿函数比较
Node* parent nullptr;
Node* cur _root;
while (cur)
{if (kot(cur-_data) kot(data)){parent cur;cur cur-_left;}else if (kot(cur-_data) kot(data)){parent cur;cur cur-_right;}else return false;
}四、红黑树的迭代器
template class T, class Ref, class Ptr
struct RBTIterator
{typedef RBTreeNodeT Node;typedef RBTIteratorT, Ref, Ptr self;RBTIterator(Node* node): _node(node){}Node* _node;
};*解引用操作返回对应结点数据的引用:
Ref operator*()
{return _node-_data;
}-访问成员操作符返回节点数据的地址
Ptr operator-()
{return _node-_data;
}!、 比较迭代器是否指向同一节点
bool operator!(const self it)
{return _node ! it._node;
}bool operator(const self it)
{return _node it._node;
}begin() 和 end() begin()返回的是最左节点中序遍历的第一个节点 end()迭代器的end()一般是返回最后一个节点的下一个位置这里设置为nullptr。
typedef RBTIteratorT, T, T* iterator;
typedef RBTIteratorT, const T, const T* const_iterator;
iterator begin()
{Node* cur _root;while (cur cur-_left){cur cur-_left;}return iterator(cur);
}iterator end()
{return iterator(nullptr);
}map里面的begin()与end()
typedef typename RBTreeK, pairconst K, V, MapKeyOfT ::iterator iterator;
iterator begin()
{return _t.begin();
}iterator end()
{return _t.end();
}这里注意因为编译的时候编译器不知道RBTreeK, pairconst K, V, MapKeyOfT ::iterator这是个类型还是静态成员变量会编译出错加上typename就是告诉编译器这里是一个类型。
set的begin()和end()
typedef typename RBTreeK, K, SetKeyOfT ::iterator iterator;
iterator begin()
{return _t.begin();
}iterator end()
{return _t.end();
}这里重要的是迭代器的和-- 寻找中序遍历的下一个节点 1️⃣ 如果右子树不为空就是找右子树的最左节点。 1️⃣ 如果右子树为空就是找祖先孩子是父亲的左的那个祖先
self operator()
{if (_node-_right){Node* min _node-_right;while (min-_left){min min-_left;}_node min;}else{Node* cur _node;Node* parent cur-_parent;while (parent parent-_right cur){cur parent;parent parent-_parent;}_node parent;}return *this;
}-- 跟刚好是反过来 1️⃣ 如果左子树不为空就是找左子树的最右节点。 1️⃣ 如果左子树为空就是找祖先孩子是父亲的右的那个祖先
self operator--()
{if (_node-_left){Node* max _node-_left;while (max max-_right){max max-_right;}_node max;}else{Node* cur _node;Node* parent cur-_parent;while (parent parent-_left cur){cur parent;parent parent-_parent;}_node parent;}return *this;
}这里还有一个重要的问题 如果这么写那么set的值也可以被修改。那么如何保证set不能被修改呢 可以直接把普通迭代器和const迭代器都变成const_iterator。
此时这里会出现问题
iterator begin()
{return _t.begin();
}iterator end()
{return _t.end();
}这里_t是普通对象会调用普通的迭代器类型不同无法返回。
我们只需要在函数后面加上const就可以权限缩小变成const对象。
iterator begin() const
{return _t.begin();
}iterator end() const
{return _t.end();
}在红黑树中也要加入对应的const版本begin()和end()
const_iterator begin() const
{Node* cur _root;while (cur cur-_left){cur cur-_left;}return const_iterator(cur);
}const_iterator end() const
{return const_iterator(nullptr);
}五、map的[]
当我们想使用map来统计次数的时候就需要重载[]。 如果想要支持[]那么insert的返回值就得设置成pairiterator, bool。 如果在bool就是falseiterator返回当前节点。
return make_pair(iterator(cur), false);不在就插入。
return make_pair(iterator(newnode), true);map
V operator[](const K key)
{pairiterator, bool ret insert(make_pair(key, V()));return ret.first-second;
}这里要注意set
pairiterator, bool insert(const K k)
{return _t.insert(k);
}这里的iterator其实是const_iterator所以导致类型不同。
5.1 普通迭代器转const迭代器
正常情况下普通迭代器不能转化为const迭代器。 为了解决这种情况我们在迭代器内添加一个拷贝构造即可。
1️⃣ 当传进来的是普通迭代器的时候iterator是普通迭代器这个函数相当于拷贝构造 2️⃣ 当传进来的是const迭代器的时候iterator依然是普通迭代器此时该函数就相当于构造函数普通迭代构造const迭代器。
其实普通迭代器和const的区别就在operator*和operator-
而set的插入不需要修改
pairiterator, bool insert(const K k)
{return _t.insert(k);
}return的时候会调用拷贝构造函数也就是构造函数把普通迭代器转化为const迭代器。
六、set源码
#pragma once
#include RBTree.hnamespace yyh
{template class Kclass set{struct SetKeyOfT{const K operator()(const K k){return k;}};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();}pairiterator, bool insert(const K k){return _t.insert(k);}private:RBTreeK, K, SetKeyOfT _t;};
}七、map源码
#pragma once
#include RBTree.hnamespace yyh
{template class K, class Vclass 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 ::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();}pairiterator, bool insert(const const pairK, V kv){return _t.insert(kv);}V operator[](const K key){pairiterator, bool ret insert(make_pair(key, V()));return ret.first-second;}private:RBTreeK, pairconst K, V, MapKeyOfT _t;};
}
八、红黑树源码
#pragma once
#include iostream
#include cstdlib
#include cassert
#include stringusing namespace std;enum Colour
{RED,BLACK,
};template class T
struct RBTreeNode
{RBTreeNode(const T data): _data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}T _data;RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;Colour _col;
};template class T, class Ref, class Ptr
struct RBTIterator
{typedef RBTreeNodeT Node;typedef RBTIteratorT, Ref, Ptr self;typedef RBTIteratorT, T, T* iterator;RBTIterator(const iterator s): _node(s._node){}RBTIterator(Node* node): _node(node){}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator!(const self it){return _node ! it._node;}bool operator(const self it){return _node it._node;}self operator(){if (_node-_right){Node* min _node-_right;while (min-_left){min min-_left;}_node min;}else{Node* cur _node;Node* parent cur-_parent;while (parent parent-_right cur){cur parent;parent parent-_parent;}_node parent;}return *this;}self operator--(){if (_node-_left){Node* max _node-_left;while (max max-_right){max max-_right;}_node max;}else{Node* cur _node;Node* parent cur-_parent;while (parent parent-_left cur){cur parent;parent parent-_parent;}_node parent;}return *this;}Node* _node;
};template class K, class T, class KeyOfT
class RBTree
{
public:typedef RBTreeNodeT Node;typedef RBTIteratorT, T, T* iterator;typedef RBTIteratorT, const T, const T* const_iterator;iterator begin(){Node* cur _root;while (cur cur-_left){cur cur-_left;}return iterator(cur);}iterator end(){return iterator(nullptr);}const_iterator begin() const{Node* cur _root;while (cur cur-_left){cur cur-_left;}return const_iterator(cur);}const_iterator end() const{return const_iterator(nullptr);}pairiterator, bool insert(const T data){if (_root nullptr){_root new Node(data);_root-_col BLACK;return make_pair(iterator(_root), true);}KeyOfT kot;// 仿函数比较Node* parent nullptr;Node* cur _root;while (cur){if (kot(cur-_data) kot(data)){parent cur;cur cur-_left;}else if (kot(cur-_data) kot(data)){parent cur;cur cur-_right;}else return make_pair(iterator(cur), false);}cur new Node(data);Node* newnode cur;if (kot(data) kot(parent-_data)){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;while (parent parent-_col RED){// 找g 与 uNode* g parent-_parent;if (parent g-_left){Node* u g-_right;// 情况一 u存在且为红if (u u-_col RED){parent-_col u-_col BLACK;g-_col RED;// 继续往上处理cur g;parent cur-_parent;}else // 情况二或情况三{if (cur parent-_left)// 情况二{// g// p// cRotateR(g);parent-_col BLACK;g-_col RED;}else// 情况三{// g// p// cRotateL(parent);RotateR(g);// c// p gcur-_col BLACK;g-_col RED;}break;}}else{Node* u g-_left;// 情况一if (u u-_col RED){u-_col parent-_col BLACK;g-_col RED;cur g;parent cur-_parent;}else{// 情况二// g// p// cif (cur parent-_right){RotateL(g);parent-_col BLACK;g-_col RED;}else// 情况三{// g// p// cRotateR(parent);RotateL(g);cur-_col BLACK;g-_col RED;}break;}}}// 上面有可能把_root的颜色变为红_root-_col BLACK;return make_pair(iterator(newnode), true);}void RotateL(Node* parent){Node* top parent-_parent;Node* right parent-_right;parent-_right right-_left;if (right-_left) right-_left-_parent parent;right-_left parent;parent-_parent right;if (top)// 子树{if (parent top-_left) top-_left right;else top-_right right;right-_parent top;}else// 完整的树{_root right;_root-_parent nullptr;}}void RotateR(Node* parent){Node* top parent-_parent;Node* left parent-_left;Node* leftR left-_right;parent-_left leftR;if (leftR) leftR-_parent parent;left-_right parent;parent-_parent left;if (top){if (parent top-_left) top-_left left;else top-_right left;left-_parent top;}else{_root left;_root-_parent nullptr;}}void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first root-_kv.second endl;_Inorder(root-_right);}void Inorder(){_Inorder(_root);}bool _IsBalance(Node* root, int i, int flag){if (root nullptr){if (i ! flag){cout errno: 左右子树黑色节点数目不同 endl;return false;}return true;}// 红节点时判断父亲if (root-_col RED){if (root-_parent-_col RED){cout errno: 红-红 endl;return false;}}if (root-_col BLACK){i;}return _IsBalance(root-_left, i, flag) _IsBalance(root-_right, i, flag);}bool IsBalance(){if (_root nullptr){return true;}if (_root-_col ! BLACK){return false;}// 找标准值Node* cur _root;int flag 0;while (cur){if (cur-_col BLACK){flag;}cur cur-_left;}int i 0;return _IsBalance(_root, i, flag);}private:Node* _root nullptr;
};
