查看网站开发,做网站还要维护吗,做网站需要哪些栏目,html5 网站源码模拟实现map和set
map和set是红黑树的两种不同封装形式#xff0c;底层使用同一颗泛型结构的红黑树#xff0c;只是存储类型不同。set是红黑树的K模型#xff0c;存储key#xff1b;map是红黑树的KV模型#xff0c;存储pairkey,value。
下面的代码和讲解着重体现…模拟实现map和set
map和set是红黑树的两种不同封装形式底层使用同一颗泛型结构的红黑树只是存储类型不同。set是红黑树的K模型存储keymap是红黑树的KV模型存储pairkey,value。
下面的代码和讲解着重体现红黑树的底层实现和map\set上层封装的衔接。红黑树的具体结构基本操作实现原理等内容请阅读下面几篇文章
【高阶数据结构】二叉搜索树 {概念实现核心结构增删查默认成员函数应用K模型和KV模型性能分析相关练习}【STL】map和set的介绍和使用 {关联式容器键值对map和setmultimap和multisetOJ练习}【高阶数据结构】AVL树 {概念及实现节点的定义插入并调整平衡因子旋转操作左单旋右单旋左右双旋右左双旋AVL树的验证及性能分析}【高阶数据结构】红黑树 {概念及性质红黑树节点的定义红黑树插入操作详细解释红黑树的验证} 一、核心结构 问题一map和set底层使用同一颗泛型结构的红黑树如何处理map(pairkey,value)和set(key)存储值不同的问题 解决方案泛型底层红黑树的存储类型通过不同的实例化参数实现出map和set。 问题二在进行查找、插入、删除操作时要对key值进行比较。在同一模版中如何区别比较map和set中的key值 解决方案通过传入仿函数KofT(KeyofTree)解决。如果是setKofT对象返回data的值如果是mapKofT对象返回data.first的值 注意pair中重载了关系运算符但first和second都参与运算不符合要求。要求只比较pair.first (key)。
1.1 RBTreeNode RBTree
// RBTree.hpp
enum Color{RED,BLACK
};template class T
struct RBTreeNode{RBTreeNodeT *_left;RBTreeNodeT *_right;RBTreeNodeT *_parent;T _data; //泛型底层红黑树的存储类型通过不同的实例化参数实现出map和set。Color _color;RBTreeNode(const T data T(), Color color RED):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_color(color){}
};//
// K: key的类型
// T: 如果是map则为pairK, V; 如果是set则为K
// KofT: 通过T类型的data来获取key的一个仿函数类
template class K, class T, class KofT
class RBTree{typedef RBTreeNodeT Node; //第二个模版参数T决定红黑树的存储类型Node *_root nullptr;//......
};1.2 set map封装
// Set.hpp
namespace zty{template class Kclass set{struct SetKofT{ //用于取出data中的keyconst K operator()(const K k){return k; } };typedef RBTreeK, K, SetKofT RBT; //set是K模型的红黑树只存储key值RBT _rbt;//......};
}//
// Map.hpp
namespace zty{template class K, class Vclass map{struct MapKofT{ //用于取出data中的keyconst K operator()(const pairK,V kv){return kv.first;}};typedef RBTreeK, pairK,V, MapKofT RBT; //map是KV模型的红黑树存储pairK,V键值对RBT _rbt;//......};
}二、插入和查找
2.1 RBTree::insert
// RBTree.hpp
template class K, class T, class KofT
pairtypename RBTreeK,T,KofT::iterator, bool RBTreeK,T,KofT::Insert(const T data)
{KofT kot; //创建KofT对象用于取出data中的keyif(_root nullptr){_root new Node(data, BLACK);return make_pair(iterator(_root), true); //返回pairiterator, bool方便实现operator[]。}Node *cur _root;Node *parent nullptr;while(cur ! nullptr){if(kot(data) kot(cur-_data)) //不管是map还是set都能正确的取出key进行比较。{parent cur;cur cur-_right;}else if(kot(data) kot(cur-_data)){parent cur;cur cur-_left;}else{return make_pair(iterator(cur), false);}}cur new Node(data,RED);Node *newnode cur; //在调整红黑树的过程中cur的指向会改变所以要提前记录新节点的指针。if(kot(data) kot(parent-_data)){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;//上一次循环中grandparent 为根节点此次循环parent nullptrwhile(parent ! nullptr parent-_color RED) {//......具体内容请参考红黑树章节内容} //end of whileif(cur _root)cur-_color BLACK;return make_pair(iterator(newnode), true); //返回pairiterator, bool方便实现operator[]。
}2.2 RBTree::find
//RBTree.hpp
template class K, class T, class KofT
typename RBTreeK,T,KofT::iterator RBTreeK,T,KofT::Find(const K k){KofT kot;if(_root nullptr){return end();}Node *cur _root; while(cur ! nullptr){if(k kot(cur-_data)){cur cur-_right;}else if(k kot(cur-_data)){cur cur-_left;}else{return cur;}}return end();
}2.3 set map封装
//Set.hpp
namespace zty{template class Kclass set{//......bool Insert(const K k){return _rbt.Insert(k).second;}iterator Find(const K k){return _rbt.Find(k);}};
}//
// Map.hpp
namespace zty{template class K, class Vclass map{//......pairiterator, bool Insert(const pairK,V kv){return _rbt.Insert(kv);}V operator[](const K k){ //Insert返回pairiterator, bool方便实现operator[]。pairiterator, bool ret Insert(make_pair(k, V()));return ret.first-second;}iterator Find(const K k){return _rbt.Find(k);}};
}三、迭代器
问题三map和set红黑树的迭代器如何实现 红黑树的迭代器底层封装一个指向节点的指针基本操作请参照list迭代器的实现。 红黑树迭代器的实现难点在于和–操作。 通过二叉树的中序遍历规则得出中序左子树根右子树 begin是中序遍历的第一个节点即二叉树的最左最小节点。 end是中序遍历最后一个节点的下一个位置左闭右开这里我们设为nullptr。 操作中序左子树根右子树 如果当前节点的右子树不为空就是找右子树中序的第一个节点最左节点。 如果当前节点的右子树为空就是找孩子不是右节点的那个祖先。 提示右子树为空或孩子是右节点说明这棵子树已经遍历访问完了。 –操作和相反右子树根左子树 如果当前节点的左子树不为空–就是找左子树的最右节点。 如果当前节点的左子树为空–就是找孩子不是左节点的那个祖先。 提示左子树为空或孩子是左节点说明这棵子树已经遍历访问完了。
3.1 RBT_iterator
// RBTree.hpp
templateclass T, class Ref, class Ptr
class RBT_iterator{typedef RBT_iteratorT, Ref, Ptr iterator;typedef RBTreeNodeT Node;Node *_pnode; //红黑树的迭代器底层封装一个指向节点的指针
public://基本操作请参照list迭代器的实现不做过多解释RBT_iterator(Node *pnode nullptr):_pnode(pnode){}Ref operator*() const{ return _pnode-_data;}Ptr operator-() const{return _pnode-_data;}bool operator(const iterator it) const{return _pnode it._pnode;}bool operator!(const iterator it) const{return _pnode ! it._pnode;}//红黑树的迭代器的实现难点在于和--操作iterator operator(){if(_pnode-_right ! nullptr) //如果当前节点的右子树不为空就是找右子树中序的第一个节点最左节点。{Node *left _pnode-_right;while(left-_left ! nullptr){left left-_left;}_pnode left;}else{ //如果当前节点的右子树为空就是找孩子不是右节点的那个祖先。Node *parent _pnode-_parent;Node *cur _pnode;while(parent ! nullptr cur parent-_right) //parent nullptr表示遍历到尾{parent parent-_parent;cur cur-_parent;}_pnode parent;}return *this;}iterator operator--(){if(_pnode-_left ! nullptr) //如果当前节点的左子树不为空--就是找左子树的最右节点。{Node *right _pnode-_left;while(right-_right ! nullptr){right right-_right;}_pnode right;}else{ //如果当前节点的左子树为空--就是找孩子不是左节点的那个祖先。Node *parent _pnode-_parent;Node *cur _pnode;while(parent ! nullptr cur parent-_left) //parent nullptr表示遍历到头{parent parent-_parent;cur cur-_parent;}_pnode parent;}return *this;}
};//template class K, class T, class KofT
class RBTree{
//......
public:typedef RBT_iteratorT, T, T* iterator; //普通迭代器typedef RBT_iteratorT, const T, const T* const_iterator; //const迭代器iterator begin(){ //begin是中序遍历的第一个节点即二叉树的最左最小节点。Node *left _root;while(left ! nullptr left-_left ! nullptr){left left-_left;}return iterator(left);}iterator end(){return iterator(nullptr); //end是中序遍历最后一个节点的下一个位置左闭右开这里我们设为nullptr。}
};3.2 set map封装
// Set.hpp
namespace zty{template class Kclass set{//......typedef RBTreeK, K, SetKofT RBT; public:typedef typename RBT::iterator iterator; //set的迭代器类型typedef typename RBT::const_iterator const_iterator; //const迭代器iterator begin(){return _rbt.begin();}iterator end(){return _rbt.end();}};
}//
// Map.hpp
namespace zty{template class K, class V//......typedef RBTreeK, pairK,V, MapKofT RBT;public:typedef typename RBT::iterator iterator; //map的迭代器类型typedef typename RBT::const_iterator const_iterator; //const迭代器iterator begin(){return _rbt.begin();}iterator end(){return _rbt.end();}};
}
