旅游电子商务网站建设规划书,免费网站服务器安全,网站建设中合作加盟的作用,公众号怎么制作红包封面在接触了诸如二叉搜索树、AVL树、红黑树的树形结构之后#xff0c;我们对树的结构有了大致的了解#xff0c;现在引入真正的关联式容器。 首先#xff0c;先明确了关联式容器的概念。我们之前所接触到的如vector、list等容器#xff0c;我们知道他们实际上都是线性的数据结… 在接触了诸如二叉搜索树、AVL树、红黑树的树形结构之后我们对树的结构有了大致的了解现在引入真正的关联式容器。 首先先明确了关联式容器的概念。我们之前所接触到的如vector、list等容器我们知道他们实际上都是线性的数据结构因此也称之为序列式容器。而关联式容器也是存储数据用只是其特别的key,value键值对的元素结构使得在数据检索方面的效率得到了很大的提升。 STL中提供的关联式容器可以分为两类树形结构和哈希结构。哈希结构我们会在后文再叙述。树形结构中关联式容器主要有set、map、multiset、multimap四种其底层都是红黑树。
4. set与multiset的用法
4.1 set的特征 set实际上就是我们之前介绍的K模型下面给出一些set特征的汇总
①容器中存储的元素只有一个值这个值既是其value又是标识它的key不允许重复元素
②set的元素只允许插入或删除操作不允许修改元素类型是const
③set的底层是红黑树所以其底层实际存放的是value,value的键值对但在插入删除时只需要给出value即可。其查找元素时间复杂度是logN。
4.2 set的接口
4.2.1 set的模板参数 模板参数中包含
key——set中存放的数据类型
Compare——比较逻辑的仿函数缺省值是less小于比较形成左树小右树大的结构。
4.2.2 set构造函数 1默认构造
2迭代区间(first,last)构造
3拷贝构造。
4.2.3 set迭代器 iterator begin()——返回set中起始位置元素的迭代器 iterator end()——返回set中最后一个元素后面的迭代器 const_iterator cbegin() const ——返回set中起始位置元素的const迭代器 const_iterator cend() const ——返回set中最后一个元素后面的const迭代器 reverse_iterator rbegin() ——返回set第一个元素的反向迭代器即end reverse_iterator rend() ——返回set最后一个元素下一个位置的反向迭代器 即begin const_reverse_iterator crbegin() const ——返回set第一个元素的反向const迭代器即cend const_reverse_iterator crend() const ——返回set最后一个元素下一个位置的反向const迭代器即cbegin 4.2.4 set的其他函数 ①empty 检测set是否为空空返回true否则返回true。 ②size 返回set中有效元素的个数。 ③insert (1)单元素在set中插入元素val实际插入的是val, val构成的键值对如果插入成功返回该元素在set中的位置true如果插入失败说明val在set中已经存在返回val在set中的位置false。 (2)范围插入。 ④erase (1)删除set中position位置上的元素。 (2)删除set中值为val的元素返回删除的元素的个数。 (3)删除set中[first, last)区间中的元素。 ⑤swap 交换两个set。 ⑥clear 将set中的元素清空。 ⑦find 返回set中值为val的元素的位置。 ⑧count 返回set中值为val的元素的个数。 4.3 multiset multiset的接口使用方法和set完全一致其唯一不同就是允许存储重复元素。
5. map的用法
5.1 map的特征 map和set有一定的相似性运用到的是KV模型下面是mapt特征的汇总
①容器中存储的元素有两个值一个是标识它的key一个是表示其值的value。不允许出现相同key的元素而不同key允许value相同。
②map的元素key不可以被修改但是其对应的value允许修改可通过[]操作符进行新增或修改操作。
③map的底层是红黑树其底层存放的是key,value的键值对。查找元素时间复杂度是logN。
5.2 map的接口
5.2.1 map的模板参数 模板参数中包含
key——map中存放的键值对的key的类型
T——map中存放的键值对的value的类型
Compare——比较逻辑的仿函数缺省值是less小于比较形成左树小右树大的结构。
5.2.2 map构造函数 1默认构造
2迭代区间(first,last)构造
3拷贝构造。
5.2.3 map迭代器 iterator begin()——返回set中起始位置元素的迭代器 iterator end()——返回set中最后一个元素后面的迭代器 const_iterator cbegin() const ——返回set中起始位置元素的const迭代器 const_iterator cend() const ——返回set中最后一个元素后面的const迭代器 reverse_iterator rbegin() ——返回set第一个元素的反向迭代器即end reverse_iterator rend() ——返回set最后一个元素下一个位置的反向迭代器 即begin const_reverse_iterator crbegin() const ——返回set第一个元素的反向const迭代器即cend const_reverse_iterator crend() const ——返回set最后一个元素下一个位置的反向const迭代器即cbegin 5.2.4 map的其他函数 ①empty 检测map是否为空空返回true否则返回true。 ②size 返回map中有效元素的个数。 ③insert (1)单元素在map中插入键值对元素val如果插入成功返回该元素在map中的位置true如果插入失败说明在map中已经存在返回val在map中的位置false。 (2)范围插入。 ④erase (1)删除map中position位置上的元素。 (2)删除map中key为k的元素返回删除的元素的个数。 (3)删除map中[first, last)区间中的元素。 ⑤swap 交换两个map。 ⑥clear 将map中的元素清空。 ⑦find 返回map中key为k的元素的位置。 ⑧count 返回map中key为k的元素的个数。 ⑨[]操作符 []操作符通过给定的key值找到其对应的value值返回的是value值即键值对第二个成员的引用因此[]既可以用于访问key对应的value也可以用于修改对应的value值。 5.3 multimap multimap的接口使用方法和map完全一致其唯一不同也是允许存储重复元素。
6.set和map的模拟实现
6.1 红黑树的接口改造 因为set和map的底层都是红黑树所以我们首先需要对之前写过的红黑树进行改造。
6.1.1 红黑树的结点 红黑树结点为了同时适用于set和map因此模板参数使用一个T来表示。当set使用时T就是一个规定的类型当map使用时T就是一个pair类型的键值对。 enum color {RED,BLACK};//红黑树的结点//由于不确定所适配的是什么容器set是Kmap是KV因此使用一个模板参数T进行代替templateclass Tstruct RBTreeNode {T _val;RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;color _color;RBTreeNode(T val):_val(val), _left(nullptr), _right(nullptr), _parent(nullptr), _color(RED){}};
6.1.2 红黑树的迭代器 因为set和map均需要使用迭代器因此红黑树也需要实现它的迭代器。我们首先给出其框架代码然后再逐一补全。 迭代器封装的是红黑树的结点除此之外为了满足自减操作的需要需要额外需要一个说明树的根节点的成员在库中使用了带头结点的树来满足这个需求。迭代器的模板为了满足const的需求依旧是经典的三个。 //对于红黑树我们需要为它写一个迭代器类型templateclass T, class Ptr, class Refclass RBTreeIterator {private:typedef RBTreeNodeT Node;Node* _node;Node* _root;typedef RBTreeIteratorT, Ptr, Ref self;public:RBTreeIterator(Node* node, Node* root):_node(node), _root(root){}};
6.1.2.1 前置 一般遍历红黑树的策略都是中序遍历因为这样得到的是一个递增或递减的序列具有实际意义。所以我们就要通过能够仅凭一个指定的点找到其在红黑树中序遍历的下一个结点。 中序遍历顺序是左→中→右因此拿到一个节点其突破点就在于有无右树。
①若其具有右树则说明此时迭代器当前处于“中”接下来就该中序访问右子树即下一个结点是右子树的最左节点。
②若其没有右子树则说明当前右子树遍历完了现在就需要确定是哪棵树的右子树遍历完了于是可以一直向父结点回溯寻找。如果是右孩子就说明它的右子树也遍历完了所以继续向上找父结点当发现是父结点的左孩子就说明它的左子树遍历完了那么此时下一个节点即为这个父结点也有可能父结点为空了说明整棵树遍历完成返回空指针作为遍历的end。 self operator(){//采取中序遍历左根右的策略那么对于而言找到下一位置是谁即可//分情况讨论//基本思路就是看当前子树是否遍历完成有右树就代表没有完成需要继续处理右树。如果完成就向上找自己属于哪一棵左子树从而继续遍历根节点和右树//①如果发现当前结点有右孩子那么说明下一个结点是右子树的最左孩子if (_node-_right){Node* cur _node-_right;while (cur-_left){cur cur-_left;}_node cur;}else{Node* cur _node;Node* parent _node-_parent;//②如果发现当前结点是父结点的左孩子那么下一个结点就是应该是该结点的父亲//③如果发现当前结点没有右子树那么说明下个结点就是向上找直到找到是左孩子的父结点while (parent cur parent-_right){cur parent;parent parent-_parent;}_node parent;}return *this;}
6.1.2.2 前置-- --即为的逆序逻辑十分相似。首先因为end是由空指针替代所以没有任何树的信息于是才引入了一个成员记录树的根节点以便在第一次--操作时可以通过一直找右的方法找到第一个遍历的结点。 在之后类似的只需判断有无左孩子。有则说明下一个节点就是左子树的最右结点没有则向上回溯直到找到是谁的右孩子。 self operator--(){//相当于操作的逆序也就成了右根左的遍历顺序了//基本思路看当前子树是否遍历完成有左树就代表没有完成需要继续处理左树。如果完成就向上找自己属于哪一棵右子树从而继续遍历根节点和左树//对于--操作而言起点可以是end()即一个空指针当从空指针开始--时需要找到中序遍历的最后一个节点即最右节点,因此需要知道根节点所以迭代器需要新增一个root成员//但在实际的std库中红黑树具有一个头结点所以迭代器不会走到空也就不需要这个root成员了if (_node nullptr){Node* cur _root;while (cur-_right){cur cur-_right;}_node cur;}//①如果发现当前结点有左孩子那么说明下一个结点是左子树的最右孩子else if (_node-_left){Node* cur _node-left;while (cur-_right){cur cur-_right;}_node cur;}else{Node* cur _node;Node* parent _node-_parent;//②如果发现当前结点是父结点的右孩子那么下一个结点就是应该是该结点的父亲//③如果发现当前结点没有左子树那么说明下个结点就是向上找直到找到是右孩子的父结点while (parent cur parent-_left){cur parent;parent parent-_parent;}_node parent;}return *this;}
6.1.2.3 其他函数 其他函数包括解引用、判断相等等函数。 Ref operator*(){return _node-_val;}Ptr operator-(){return (_node-_val);}bool operator(const self it){return it._node _node;}bool operator!(const self it){return it._node ! _node;}
6.1.3 红黑树
6.1.3.1 模板参数与默认成员函数 为了同时兼容set和map红黑树参数模板缩减至三个。、
K——key的类型
T——value的类型或者说是应该存储的元素的类型。对于set而言T与K是相同的对于map而言T就是pairkeyvalue
KeyOfT——取得key值的仿函数。因为set的key可以直接取得而map的key需要访问pair的first成员得到因此给出仿函数来解决这个问题。 templateclass K, class T, class KeyOfT//模板参数// K——key的类型// T——value的类型对于set而言T与K是相同的对于map而言T就是pairkeyvalue// KeyOfT——取得key值的仿函数class RBTree {typedef RBTreeNodeT RBNode;public://无参构造RBTree():_root(nullptr){}//拷贝构造RBTree(const RBTree rb){_root copy(rb._root);}private:RBNode* copy(RBNode* root){if (root nullptr) return nullptr;RBNode* newnode new RBNode(root-_val);newnode-_left copy(root-_left);newnode-_right copy(root-_right);return newnode;}public://析构函数~RBTree(){destroy(_root);_root nullptr;}private:void destroy(RBNode* root){if (root nullptr) return;destroy(root-_left);destroy(root-_right);delete root;}public://赋值重载操作符RBTree operator(const RBTree rb){swap(_root, rb-_root);return *this;}private:RBNode* _root;};
6.1.3.2 迭代器 实现了const和非const两种迭代器。begin函数即为开始点找到最左结点即可end函数则是空指针构造迭代器。 //迭代器public:typedef RBTreeIteratorT, T*, T iterator;typedef RBTreeIteratorT, const T*, const T constiterator;iterator begin(){RBNode* cur _root;while (cur cur-_left){cur cur-_left;}return iterator(cur, _root);}iterator end(){return iterator(nullptr, _root);}constiterator cbegin(){RBNode* cur _root;while (cur cur-_left){cur cur-_left;}return constiterator(cur, _root);}constiterator cend(){return { nullptr,_root };}6.1.2.3 其他函数 注意修改insert和find返回值。insert返回迭代器和bool的pair使用make_pair来构造。find返回迭代器。
//插入//在标准库中insert返回的实际上是pairiterator,bool,可以通过库函数make_pair(T1 x,T2 y)来创建pairpairiterator, bool insert(const T data){//第一个结点特殊处理if (_root nullptr){_root new RBNode(data);_root-_color BLACK;return make_pair(iterator(_root, _root), true);}RBNode* cur _root;RBNode* parent nullptr;//对于set和map它们取出key值的方法是不同的//set的key和value相同就是传入的参数data因此直接使用data既可以拿到key值//而map的key值不同它传入的data是一个结构体pair需要通过pair.first的形式来拿到key值//可见面对这样同种目的但操作不同的情况就需要通过仿函数来解决了////以红黑树为底层的容器需要提供对应的仿函数来完成取得key值的功能而在红黑树中只需要使用即可KeyOfT Getkey;while (cur){if (Getkey(cur-_val) Getkey(data)){parent cur;cur cur-_left;}else if (Getkey(cur-_val) Getkey(data)){parent cur;cur cur-_right;}else{return make_pair(iterator(cur,_root),false);}}cur new RBNode(data);if (Getkey(parent-_val) Getkey(data)){parent-_left cur;cur-_parent parent;}else{parent-_right cur;cur-_parent parent;}RBNode* ret cur;//调整红黑树颜色//红黑树规则// ①根结点颜色一定是黑色// ②不能出现连续的红结点即红结点的孩子一定是黑色// ③各条路径根结点-叶子结点上的黑色节点数目相同// ④叶子结点此处认为是空结点颜色为黑色//在这样的规则限制下不难发现红黑树最长路径一定小于最短路径的二倍这个特征//当违反了红黑树规则才需要调整红黑树颜色//插入新的结点时选择插入红色节点可能违反不能有连续的红色节点的规则选择插入黑色节点则必然会违反黑色节点数目相同的规则//因此两害相权取其轻选择插入红色节点因此我们主要处理的就是连续红结点的问题//于是连续的两个节点cur和p都是红色的而u作为p的兄弟节点决定了调整方式而在调整中受影响的则是p和u的父结点gwhile (parent parent-_color RED){//根据形式的不同一般分为三类处理//在解决连续红色的问题时也要兼顾到褐色节点数目相同这一规则RBNode* grandparent parent-_parent;RBNode* uncle parent grandparent-_left ? grandparent-_right : grandparent-_left;//①u为红色p、u均为红//p、u同时变为黑色g变为红色因为g是红色因此需要继续向上检查if (uncle uncle-_color RED){parent-_color uncle-_color BLACK;grandparent-_color RED;parent grandparent-_parent;cur grandparent;}//②u为黑色或不存在而g、p和cur是顺位左左或右右//此时单纯的变色会使得p子树和u子树路径黑色节点数目不同因为在修改p为黑u本就为黑u相较p黑色节点少一个//为了可以顺利变色我们首先要旋转红色的p成为了子树的根黑色的g成为了u这棵树的父结点此时可以证明只需要p变为黑g变为红即可//旋转操作就是AVL树中的左右单旋//③u为黑色或不存在而g、p和cur是逆位左右或右左//此时只需要将p结点左旋或右旋一次即可形成如②的情况因此这种情况使用双旋即可else{if (parent grandparent-_left){//左左顺位——右旋p变黑g变红if (cur parent-_left){RotateR(grandparent);}//左右逆位——左右双旋p变黑g变红else{RotateLR(grandparent);}}else{//右右顺位——左旋p变黑g变红if (cur parent-_right){RotateL(grandparent);}//右左逆位——右左双旋p变黑g变红else{RotateRL(grandparent);}}//由于②③结果的子树根结点都是黑色因此不会影响上一层无需向上检查break;}}//根结点有可能变色需要修改_root-_color BLACK;return make_pair(iterator(ret, _root), true);}iterator find(const K key){RBNode* cur _root;KeyOfT Getkey;while (cur){if (key Getkey(cur-_val)){cur cur-_right;}else if (key Getkey(cur-_val)){cur cur-_left;}else{return iterator(cur, _root);}}return iterator(nullptr, _root);}private:void RotateL(RBNode* grandparent){RBNode* subR grandparent-_right;RBNode* subRL subR-_left;//结点链接三组subR和grandparent、grandparent和sunRL、grandparent-_parent和subRsubR-_left grandparent;grandparent-_right subRL;if (grandparent-_parent nullptr){_root subR;}else if (grandparent-_parent-_left grandparent){grandparent-_parent-_left subR;}else{grandparent-_parent-_right subR;}subR-_parent grandparent-_parent;grandparent-_parent subR;if (subRL) //右左子树为空树subRL-_parent grandparent;//修改颜色p变黑g变红subR-_color BLACK;grandparent-_color RED;}void RotateR(RBNode* grandparent){RBNode* subL grandparent-_left;RBNode* subLR subL-_right;//结点链接三组subL和grandparent、grandparent和sunLR、grandparent-_parent和subLsubL-_right grandparent;grandparent-_left subLR;if (grandparent-_parent nullptr){_root subL;}else if (grandparent-_parent-_left grandparent){grandparent-_parent-_left subL;}else{grandparent-_parent-_right subL;}subL-_parent grandparent-_parent;grandparent-_parent subL;if (subLR) //左右子树为空树subLR-_parent grandparent;//修改颜色p变黑g变红subL-_color BLACK;grandparent-_color RED;}//左右双旋void RotateLR(RBNode* grandparent){RBNode* subL grandparent-_left;RBNode* subLR grandparent-_left-_right;//只需要旋转颜色最后指定RotateL(subL);RotateR(grandparent);//修改颜色cur变黑g变红subLR-_color BLACK;grandparent-_color RED;}//右左双旋void RotateRL(RBNode* grandparent){RBNode* subR grandparent-_right;RBNode* subRL grandparent-_right-_left;//只需要旋转颜色最后指定RotateR(subR);RotateL(grandparent);//修改颜色cur变黑g变红subRL-_color BLACK;grandparent-_color RED;}
6.2 set的封装 封装set只需要调用对应红黑树的接口就好。 注意两处①提供红黑树使用的仿函数set的key和value相同传入key返回key即可。②typedef迭代器时由于定义的是模板类的中的类型因为模板没有实例化所以编译器不知道iterator是什么需要给出关键字typename说明这是一个类型名。 template class Kclass set {//取出Key的仿函数struct Set_KeyOfT{//传入一个value是T类型要求返回value的key//set的value和key相同const K operator()(const K key){return key;}};public://由于是对模板类中的类型进行重命名模板类没有实例化编译器并不知道iterator是什么因此需要加上typename来告诉编译器这是一个类型名typedef typename RBTree::RBTreeK, K, Set_KeyOfT::iterator iterator;typedef typename RBTree::RBTreeK, K, Set_KeyOfT::constiterator constiterator;iterator begin(){return _tree.begin();}iterator end(){return _tree.end();}constiterator cbegin(){return _tree.cbegin();}constiterator cend(){return _tree.cend();}pairiterator,bool insert(const K key){return _tree.insert(key);}iterator find(const K key){return _tree.find(key);}private:RBTree::RBTreeK, K, Set_KeyOfT _tree;};
6.3 map的封装 同样的封装map也只需要调用对应红黑树的接口就好。 注意三处①提供红黑树使用的仿函数传入value值即一个pair返回pair的first成员就是key。②typedef迭代器需要给出关键字typename。③注意[]函数的实现。 template class K, class Vclass map {//取出Key的仿函数struct Map_KeyOfT{//传入一个value是T类型要求返回value的key//map的value是一个pairkey是pair的firstconst K operator()(const pairK, V kv){return kv.first;}};public://由于是对模板类中的类型进行重命名模板类没有实例化编译器并不知道iterator是什么因此需要加上typename来告诉编译器这是一个类型名typedef typename RBTree::RBTreeK, pairconst K, V, Map_KeyOfT::iterator iterator;typedef typename RBTree::RBTreeK, pairconst K, V, Map_KeyOfT::constiterator constiterator;iterator begin(){return _tree.begin();}iterator end(){return _tree.end();}constiterator cbegin(){return _tree.cbegin();}constiterator cend(){return _tree.cend();}pairiterator, bool insert(const pairK,V kv){return _tree.insert(kv);}iterator find(const K key){return _tree.find(key);}V operator[](const K key){return find(key)-second;}private:RBTree::RBTreeK, pairconst K, V, Map_KeyOfT _tree;};
