C++——关联式容器（4）：set和map

        在接触了诸如二叉搜索树、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迭代器

        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迭代器

        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是K，map是KV），因此使用一个模板参数T进行代替template<class T>struct RBTreeNode {T _val;RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;color _color;RBTreeNode(T val):_val(val), _left(nullptr), _right(nullptr), _parent(nullptr), _color(RED){}};

6.1.2  红黑树的迭代器

        因为set和map均需要使用迭代器，因此红黑树也需要实现它的迭代器。我们首先给出其框架代码，然后再逐一补全。

        迭代器封装的是红黑树的结点，除此之外，为了满足自减操作的需要，需要额外需要一个说明树的根节点的成员（在库中使用了带头结点的树来满足这个需求）。迭代器的模板为了满足const的需求，依旧是经典的三个。

	//对于红黑树，我们需要为它写一个迭代器类型template<class T, class Ptr, class Ref>class RBTreeIterator {private:typedef RBTreeNode<T> Node;Node* _node;Node* _root;typedef RBTreeIterator<T, 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就是pair<key，value>；

KeyOfT——取得key值的仿函数。因为set的key可以直接取得，而map的key需要访问pair的first成员得到，因此给出仿函数来解决这个问题。

	template<class K, class T, class KeyOfT>//模板参数：// K——key的类型// T——value的类型，对于set而言T与K是相同的，对于map而言T就是pair<key，value>// KeyOfT——取得key值的仿函数class RBTree {typedef RBTreeNode<T> 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 RBTreeIterator<T, T*, T&> iterator;typedef RBTreeIterator<T, 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返回的实际上是pair<iterator,bool>,可以通过库函数make_pair(T1 x,T2 y)来创建pairpair<iterator, 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 K>class 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::RBTree<K, K, Set_KeyOfT>::iterator iterator;typedef typename RBTree::RBTree<K, 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();}pair<iterator,bool> insert(const K& key){return _tree.insert(key);}iterator find(const K& key){return _tree.find(key);}private:RBTree::RBTree<K, K, Set_KeyOfT> _tree;};

6.3 map的封装

        同样的，封装map也只需要调用对应红黑树的接口就好。

        注意三处：①提供红黑树使用的仿函数：传入value值，即一个pair，返回pair的first成员就是key。②typedef迭代器需要给出关键字typename。③注意[]函数的实现。

	template <class K, class V>class map {//取出Key的仿函数struct Map_KeyOfT{//传入一个value，是T类型，要求返回value的key//map的value是一个pair，key是pair的firstconst K& operator()(const pair<K, V>& kv){return kv.first;}};public://由于是对模板类中的类型进行重命名，模板类没有实例化，编译器并不知道iterator是什么，因此需要加上typename来告诉编译器这是一个类型名typedef typename RBTree::RBTree<K, pair<const K, V>, Map_KeyOfT>::iterator iterator;typedef typename RBTree::RBTree<K, pair<const 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();}pair<iterator, bool> insert(const pair<K,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::RBTree<K, pair<const K, V>, Map_KeyOfT> _tree;};