1.关联式容器与键值对

 前导文章：C++ 二叉树进阶-CSDN博客

之前我们学习的线性的容器，如：vector deque list等都叫作序列式容器

与之对立的概念是关联式容器

关联式容器 也是用来存储数据的，与序列式容器不同的是，其 里面存储的是 <key, value> 结构的 键值对，在数据检索时比序列式容器效率更高 。

key就是键值，可以在容器中通过键值直接找到value.

比如：现在要建立一个英汉互译的字典，那该字典中必然 有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应 该单词，在词典中就可以找到与其对应的中文含义

我们在 前导文章中的代码的基础上继续往下写：

                             

在搜索二叉树中，有两种典型的模型：key模型和key_value模型

key模型对应set，key_value模型对应map

---

2. set

1. set 是按照一定次序存储元素的容器

2. 在 set 中，元素的 value 也标识它 (value 就是 key ，类型为 T) ，并且每个 value 必须是唯一的。

set 中的元素不能在容器中修改 ( 元素总是 const) ，但是可以从容器中插入或删除它们。

3. 在内部， set 中的元素总是按照其内部比较对象 ( 类型比较 ) 所指示的特定严格弱排序准则进行排序。

4. set 容器通过 key 访问单个元素的速度通常比 unordered_set 容器慢，但它们允许根据顺序对

子集进行直接迭代。

5. set 在底层是用二叉搜索树 ( 红黑树 ) 实现的。

set有三个参数，元素类型、用于比较的仿函数（默认是less）、内存池。

set的操作：

插入操作只有insert（先不管emplace）, 线性的数据结构才能push。

set的底层是二叉搜索树中的key模式，并且迭代器在底层默认走的是中序

二叉搜索树的中序遍历一定是有序的，而且还有去重的功能：

  set能够去重（insert了两个三最后还是只出了一个3）： 

                       

---

set的构造：

在c++98下，set只有范围构造和拷贝构造两种使用方法。

可以用迭代器range构造：

因为节点也是存的指针，所以拷贝构造也是走树的深拷贝：

                                              

关于销毁：

在实现析构函数时：

因为析构函数不能有参数，所以我们需要通过在析构函数里套一个Destroy函数来完成析构：

~BSTree()
{Destroy(_root);_root = nullptr;
}

采用后序遍历一个一个销毁节点

为什么要套用？

因为树的销毁是采用递归销毁的办法，而析构函数不能传参，也就无法递归

同理，拷贝构造也是需要递归遍历，也需要封装。

不能直接用BST(const BSTNode<K,V>& Node)去递归拷贝。

增删查改：

删除最小值就是删除begin()对应的数据就行。

因为iterator走的是中序遍历，所以begin()对应的一定是最左值，而最左值就是最小的数据。

                                   

可以通过erase的返回值来判断是否erase成功：

---

关于erase删除的报错：

erase删除数值

比如erase(80) , 有80就删除成功，没有80就删除失败。但是删除失败不会报错。

erase删除迭代器：

但是如果使用find()返回的迭代器来删除，find又没有找到，就会报错。

因为find在没有找到的时候，返回值是end(),直接erase(end())就会报错。

---

查找：

库中的find是根据iterator全部遍历一遍，暴力查找

set中的find是按照搜索二叉树走的；

因此效率有很大差距。

还有个count函数用于计数：

但是由于搜索二叉树是一种不允许冗余数据的容器

所以在目前的使用情境下，该数据存在就返回1，不存在就返回0

                       

因此在set中，count函数一般直接用于判断元素是否存在。 

---

lower_bound  和 upper_bound（返回的都是>或>=val的第一个数据）

louwer_bound返回的就是set中>=val的第一个数据的iterator

如果没有合适的元素，返回的就是end()

upper_bound同理：

返回的是set中第一个>val的数据的iterator

直接看官网的测试用例：

但是根据cpp左闭右开的性质，lower_bound(30)返回的就是30

upper_bound(60)返回的就是稍大于60的值（此处应该是70），最终能把[30,70)区间里的所有数都删掉，所以删掉的还是[30,60]的数据

---

3. multiset

multiset是set的变种容器：允许有冗余的元素，允许修改容器里的元素。

multiset和set的区别：

因为multiset是可以插入相同元素的，所以在find时，multiset的find返回的是中序遇到的第一个值：

multiset更能解释count函数存在的意义了，count在multiset中就可以返回相同数值的节点的个数。

还有刚才的lower_bound和upper_bound两个功能下面的被我们忽视的功能：equal_range

equal_range ：找到一个数据所有相同数值所在的左闭右开的区间（multiset中相同数据一定是紧挨着的）。

因为相等的数据一定是在相邻的位置。

equal_range返回的是一个pair

pair 中有两个数据，表示的是整个满足条件的区间。

pair是一种结构体。

equal_range返回的pair就是这个区间。

---

4. map 

map结构

map就是在本文开始处讲的基于搜索二叉树的<key,value>类型

pair是一个结构体模版，在map中统一规定所有的value_type都是pair类型的。

来观察下pair:

成员有first和second

                       

map的结构和set很像

最大的区别map支持方括号访问。(将在后文解释)

---

map使用（make_pair）

现在就不需要手搓平衡二叉树了，可以直接使用map来创建一个简易字典。

               

但是这样insert是不对的，在map内部，key和value不是分开存放的，而是一起被放在pair中的

正确的四种写法：

第一种，构造有名对象。

第二种，构造匿名对象。

第三种，是库中函数make_pair()对pair<T1,T2>的一种封装

                     

第四种，多参数构造函数可以用{}来进行隐式类型转换。

其实是用{"string","字符串"}构造了一个pair，然后被insert进去。

最后还有一种初始化的方法：

map<string, string> dict = { {"left", "左边"}, {"right", "右边"},{"insert", "插入"},{ "string", "字符串" } };

使用的是所有的容器都支持的initializer_list

外围花括号就是针对一个一个pair的initializer_list, 内层花括号就是隐式类型转换构造的pair

map的遍历： 

想要访问map中的元素，需要pair.去访问内部元素（如上图）。

还可以用->去访问。因为it是像指针一样的东西，之前在链表部分也讲过

库中是通过重载operator->()来使用：

这里的it是为了可读性而省略了一个箭头。

map访问数据多是使用operator->

查询时同理：

    

---

★★★map的方括号访问（重难点）：

(mapped_type就是value_type , 也就是我们常说的value)

不同于传统的方括号访问,

参数是key，返回的是value的引用。换句话说，方括号是通过key去找value的

首先要知道map中insert的返回值：

insert返回的是一个pair
只要插入成功，bool的值就是true, iterator指向的是新插入成功的节点。

在 C++ 中，std::map 是一个基于红黑树实现的关联容器，它不允许插入具有相同键（key）的元素。std::map 的每个键值对都是唯一的，键用于组织数据，因此它会自动根据键的顺序对元素进行排序。

如果你尝试插入一个已经存在的键，std::map 会拒绝这个插入操作，并且不会覆盖原有的键值对。如果你需要检查插入是否成功，可以使用 insert 方法，它会返回一个 pair，其中 pair.second 表示插入是否成功（如果键已存在，则为 false），而 pair.first 会指向插入的元素或者已存在的元素。

这就是下图为什么第二次insert"你好"这个键失败的原因

了解了insert的原理，我们再回过头来观察方括号访问：

将operator[]的逻辑写成函数：

             

所以，如果operator[k]的时候，k是一个没有出现过的key , map就会自动创建一个k为key，v为mapped_value()的匿名构造的pair，存在map中。

并且方括号返回的是mapped_value的引用，可以再对这个value的值进行修改。

所以这个operator[]是一个插入+修改的功能。

如果我们再调用一次operator[]:

              

第二次调用["left"]，先查找有没有left，因为第一次插入已经创建了left了，所以第二次就找到了<"left","左边">，然后返回了"左边"的引用，通过赋值符号将"左边"改成了 "左边、剩余"

如果只调用一次这个：

                                             

相对于插入了一个"insert",V()的pair

小结：

                   

综上，map的方括号引用是一个复合功能。

所以使用方括号访问的时候要小心，否则一不小心就可能变成插入一个不希望插入的内容。

方括号访问了一个本来不存在的键也会导致插入一个不想插入的pair

使用这个特性，之前计数的代码就可以：

如果水果名字是第一次出现，那么就会在map中插入一个<新的水果名，0>，然后对返回值0进行一次++；如果水果名字不是第一次出现，就是直接对返回的(*iterator).second的value进行++

---

multimap

multimap 和 map 的唯一不同就是： map 中的 key 是唯一的，而 multimap 中 key 是可以

重复的 。并且multimap不支持方括号访问，inser返回的也只是iterator，而不是一个pair

 甚至还可以在<key,value>都相同的情况下insert一个一模一样的pair

---

5. 大试牛刀

138. 随机链表的复制 - 力扣（LeetCode） 

我们曾经使用C语言解决过这个问题，解决方法是在原链表的基础上，每一个节点后面都拷贝一份一样的，这样做的本质就是建立相对映射关系。

但是现在有了map可以自主建立映射关系了，就不需要上述麻烦了。

先遍历深拷贝一下节点：

                 

每深拷贝一个节点，就赛一个进入map，可以insert进去也可以直接通过方括号访问调用insert

                 

然后通过映射关系处理深拷贝的所有节点的random

class Solution {
public:Node* copyRandomList(Node* head) {Node* cur = head;map<Node*,Node*> NodeMap;Node* phead = nullptr;Node* ptail = nullptr;while(cur){if(ptail==nullptr){phead = ptail = new Node(cur->val);}else{ptail->next = new Node(cur->val);ptail = ptail->next;}  //每拷贝一个，就让被拷贝的和其对应的两个节点入mapNodeMap.insert(make_pair(cur,ptail));//也可以这样进入map//NodeMap[cur] = ptail;cur = cur->next;}//最后来处理randomcur = head;ptail = phead;while(cur){if(cur->random == nullptr){ptail->random = nullptr;}else{ptail->random = NodeMap[cur->random];}cur = cur->next;ptail = ptail->next;}return phead;}
};

---

判断是否有环

142. 环形链表 II - 力扣（LeetCode）

放在以前，我们需要利用追击问题的数学知识，推出：

在fast和slow相遇在meet点时，从头出发一个cur，cur和slow同时遍历，一定在环的入口相遇。

现在利用set插入时的特点，第一个插入失败的元素就是环的入口点。

class Solution {
public:ListNode *detectCycle(ListNode *head) {set<ListNode*> s;ListNode* cur = head;while(cur && (s.insert(cur)).second){cur = cur->next;}return cur;}
};

---

349. 两个数组的交集 - 力扣（LeetCode）

求交集或者差集，第一步建议：排序+去重

先使用set的迭代器区间构造：

                              

然后使用双指针：

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {set<int> s1(nums1.begin(),nums1.end());set<int> s2(nums2.begin(),nums2.end());auto it1 = s1.begin();auto it2 = s2.begin();vector<int> ans;while(it1 != s1.end() && it2 != s2.end()){if(*it1 == *it2){ans.push_back(*it1);++it1,++it2;}else if(*it1 < *it2){++it1;}else{++it2;}}return ans;}
};

用set可以完美实现排序加去重。然后再利用一个双指针依次遍历

实践中，云平台的同步服务就需要以上的通过交集和并集的同步操作

---

692. 前K个高频单词 - 力扣（LeetCode） 

        这是一个映射+topk的结合问题，思路如下：

        先把words中的词全部加入到map<单词，出现次数>中去（同遍历水果名字并且计数）

为了让map中的数据根据出现次数来排序，又需要把map中的一个一个pair给放入vector中，然后自己传仿函数（根据出现次数和字典序来排序），比较完之后再将排在前面的k个数据给push到要返回的vector<string>中去。

但是要通过countMap.second来排序以便获得topk

但是排序（数据量小直接用sort,数据量大的时候必须用优先级队列）必须用支持随机迭代器的容器。

所以先将map中的数据入到一个vector中去

 不过对于pair自带的比大小：

不同于我们的期望，我们现在只希望按照次数去比较，所以需要我们自己去实现一个仿函数

然后再创建一个vector来储存答案。

但是发很多测试用例不能通过。

原因是忽略了一个题目的要求：

也不能直接在最后的vector中排序，因为只要求对出现次数相同的单词进行字典序排序

明明在加入到map中的时候已经经过了一次字典序的排序，为怎么现在又乱了？

因为sort的底层是快排，快排是不稳定排序。

可以使用stable_sort：

                

或者改写我们的仿函数：

注意，关于sort要传的用于比较的仿函数：

        返回值需要是bool并且要传两个参数 ，希望是降序就要保证第一个参数大于第二个参数为真。

但是此题的字典序是针对string的升序，所以后面的条件是小于号。