【C++】map set

一、关联式容器

我们在前面已经接触过 STL 中的部分容器，比如：vector、list、deque、等，这些容器统称为序列式容器(一级容器)，因为其底层为线性序列的数据结构，里面存储的是元素本身。

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

二、键值对

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量 key 和 value，key 代表键值，value 表示与 key 对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。

SGI-STL中关于键值对的定义：

		template <class T1, class T2>struct pair{typedef T1 first_type;typedef T2 second_type;T1 first;T2 second;pair(): first(T1()), second(T2()){}pair(const T1& a, const T2& b): first(a), second(b){}};

三、树形结构的关联式容器

根据应用场景的不同，STL 总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset；这四种容器的共同点是：使用平衡搜索树(即红黑树) 作为其底层结果，容器中的元素是一个有序的序列。下面一依次介绍每一个容器。

1. set

（1）set 的介绍

首先我们可以看一下 set 的文档介绍：set 文档介绍.

简单概括：

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

2. 在 set 中，元素的 value 也标识它(value就是 key，类型为 T)，并且每个 value 必须是唯一的。
   set 中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。

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

注意：

1. 与 map/multimap 不同，map/multimap 中存储的是真正的键值对 <key, value>，set 中只放 value，但在底层实际存放的是由 <value, value> 构成的键值对。
2. set 中插入元素时，只需要插入 value 即可，不需要构造键值对。
3. set 中的元素不可以重复 (因此可以使用set进行去重) ；
4. 使用 set 的迭代器遍历 set 中的元素，可以得到有序序列；
5. set 中的元素默认按照小于来比较；
6. set 中查找某个元素，时间复杂度为：O(logN).

（2）set 的使用

在使用之前我们先看一下 set 的模板参数列表：

其中：

• T: set 中存放元素的类型，实际在底层存储 <value, value> 的键值对。
• Compare：仿函数，set 中元素默认按照小于来比较
• Alloc：set 中元素空间的管理方式，使用STL提供的空间配置器管理

1. insert

下面我们简单插入几个元素并打印出来：

		void test1(){set<int> s;s.insert(2);s.insert(6);s.insert(1);s.insert(4);s.insert(9);s.insert(9);s.insert(9);s.insert(0);for (auto& e : s){cout << e << " ";}cout << endl;}

由于 set 底层有迭代器，所以可以使用范围 for. 运行结果如下：

我们看到 set 打印出来是有序的并且去重了；在这里我们可以看一下 insert 的返回值：

如上图，当我们插入的是一个值的时候，它的返回值是一个 pair 类型的键值对，所以我们可以简单用一个 pair 类型的变量接收，观察它对应的数据，如下：

		void test1(){set<int> s;s.insert(2);s.insert(6);s.insert(1);s.insert(4);s.insert(9);s.insert(0);pair<set<int>::iterator, bool> it1 = s.insert(9);cout << *(it1.first) << "  ";cout << it1.second<< endl;pair<set<int>::iterator, bool> it2 = s.insert(10);cout << *(it2.first) << "  ";cout << it2.second << endl;}

如上代码，我们在已经有 9 的 s 中再次插入 9，我们观察它的返回值中的 first 和 second；然后我们插入 s 中没有的 10，继续观察；结果如下：

如上图，我们看到插入已有元素后，因为返回的 first 是个迭代器，所以需要解引用才能得到里面的值，里面的值给我们返回了已经存在的 9；而 second 返回了 0 即 false，代表插入失败。

插入没有的元素的时候 first 返回的是新插入的值所在节点的迭代器；second 则是 1，即 true，代表插入成功。

2. erase

删除和我们往常用的差不多，直接删除需要删除的元素即可；注意删除成功返回 1；删除失败返回 0；

也可以直接给迭代器的位置直接删除，没有返回值。

如下代码：

		void test1(){set<int> s;s.insert(2);s.insert(6);s.insert(1);s.insert(4);s.insert(9);s.insert(0);// 打印删除前for (auto& e : s){cout << e << " ";}cout << endl;// 打印删除结果cout << s.erase(1) << endl;cout << s.erase(20) << endl;// 打印删除后for (auto& e : s){cout << e << " ";}cout << endl;}

结果如下：

3. find

如上图我们看到，find 的返回值是 iterator，那么返回的是哪个位置的迭代器呢？我们继续看它的返回值：

如上，如果找到这个元素，则返回这个元素所以在位置的迭代器；否则返回 end() 位置。可以如下使用：

		void test2(){set<int> s;s.insert(2);s.insert(6);s.insert(1);s.insert(4);s.insert(9);s.insert(0);set<int>::iterator it = s.find(6);if (it != s.end()){s.erase(it);}for (auto& e : s){cout << e << " ";}cout << endl;}

4. count

count 返回值就是统计这个元素出现多少次，但是 set 的一个特性是去重，所以返回值只有 1 和 0；所以一般用来判断在不在；如下：

		void test2(){set<int> s;s.insert(2);s.insert(6);s.insert(1);s.insert(4);s.insert(9);s.insert(0);if (s.count(6)){cout << "6在" << endl;}else{cout << "6不在" << endl;}if (s.count(10)){cout << "10在" << endl;}else{cout << "10不在" << endl;}}

5. lower_bound 和 upper_bound

• lower_bound 是返回一个 >= val 值位置的 iterator ；
• upper_bound 是返回一个 > val 值位置的 iterator ；

使用如下：

		void test3(){set<int>::iterator itlow, itup;set<int> s;// 插入 10 20 30 40 50 60 70 80 90for (int i = 1; i < 10; i++) s.insert(i * 10);  itlow = s.lower_bound(25);itup = s.upper_bound(70);s.erase(itlow, itup);   // 删除区间 [30, 40, 50, 60, 70]for (auto& e : s){cout << e << " ";}cout << endl;}

结果如下：

6. equal_range

如上图介绍，equal_range 是返回一个 pair 类型，是一个范围的边界，该范围包括 s 中与 val 等价的所有元素。使用如下：

		void test4(){set<int> s;// 插入 10 20 30 40 50 60 70 80 90for (int i = 1; i < 10; i++)s.insert(i * 10);auto ret = s.equal_range(30);cout << *ret.first << endl;   // >= valcout << *ret.second << endl;  // >  val}

结果如下：

2. multiset

multiset 文档介绍

multiset 是按照特定顺序存储元素的容器，其中元素是可以重复的；它与 set 的区别就是 multiset 可以插入重复的元素。

• multiset 的使用

multiset 的许多接口都与 set 重复，所以它们的用法大体一致；

在这就介绍一下 find，如果有多个 val ，find 返回中序的第一个 val.

如下段代码：

		void test5(){multiset<int> ms;ms.insert(2);ms.insert(2);ms.insert(1);ms.insert(4);ms.insert(2);ms.insert(2);ms.insert(0);for (auto& e : ms)cout << e << " ";cout << endl;multiset<int>::iterator it = ms.find(2);while (it != ms.end()){cout << *it << " ";++it;}cout << endl;}

结果如下，说明 find 是返回中序的第一个2：

3. map

（1）map 的介绍

我们先看一下 map 的文档介绍：map 文档介绍 .

简单概括：

1. map 是关联容器，它按照特定的次序(按照 key 来比较)存储由键值 key 和值 value 组合而成的元素。
2. 在 map 中，键值 key 通常用于排序和唯一地标识元素，而值value 中存储与此键值 key 关联的内容。键值 key 和值 value 的类型可能不同，并且在 map 的内部，key 与 value 通过成员类型 value_type 绑定在一起，为其取别名称为 pair： typedef pair<const key, T> value_type; 如下图，是文档内容的截取：

3. 在内部，map 中的元素总是按照键值 key 进行比较排序的。
4. map 中通过键值访问单个元素的速度通常比 unordered_map 容器慢，但 map 允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
5. map 支持下标访问符，即在 [] 中放入 key，就可以找到与 key 对应的 value。
6. map 通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。

（2）map 的使用

1. insert

因为 map 插入的是一对键值对，所以需要以 pair 的形式插入；我们先看一下 pair 的文档介绍：pair 文档介绍

其中它的构造函数如下：

但是我们习惯用以下这个接口初始化一个键值对对象：make_pair，如下：

所以我们插入的时候可以以如下两种方式插入：

		void test6(){map<string, string> dict;dict.insert(pair<string, string>("insert", "插入"));dict.insert(make_pair("string", "字符串"));map<string, string>::iterator it = dict.begin();while (it != dict.end()){cout << (*it).first << ":" << (*it).second << endl;//cout << it->first << ":" << it->second << endl;++it;}}

因为 iterator 迭代器封装的是一个个节点，所以解引用得到的是一个 pair 类型的键值对，所以解引用后使用 . 指定访问 first 还是 second；而 -> 我们在 list 部分讲过，当节点中存的类型是自定义类型的时候，我们使用 -> 就可以方便一点进行指定元素的访问，而 pair 正好就是自定义类型，所以用 -> 访问更方便。

注意，这里的是省略了一个 ->，实际上 it->first 就是 it.operator->()->first；其中 it.operator->() 是取到 pair 的地址，再使用 -> 即可进行指定元素访问。

然后其它接口的使用和 set 的用法差不多，只是 map 的类型变成了 pair 而已；所以其它接口不再进行介绍，下面开始介绍 map 中的最重要的接口：operator[].

2. operator[]

如上图和下图，operator[] 的返回值是 pair 的第二个模板参数：

我们先看一下 operator[] 的使用，如下段代码：

		void test7(){string array[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };map<string, int> mapCount;for (auto& str : array)mapCount[str]++;for (auto& kv : mapCount)cout << kv.first << ":" << kv.second << endl;}

结果如下：

实际上，调用 operator[] 就是在调用：(*((this->insert(make_pair(k,mapped_type()))).first)).second

如下图是原文档的解释：

分析如下：

其中 mapped_type 是 map 模板中的第二个模板参数类型，mapped_type() 则是默认构造的匿名对象，所以我们传 int 类型的时候，如果 key 在 map 中没有，则初始化为 0；如果有则返回 key 对应的 value；所以当我们 ++ 的时候，就可以统计次数，其实 ++ 就是作用到 pair 的 value 上。

总结：

1. map 中的的元素是键值对
2. map 中的 key 是唯一的，并且不能修改
3. 默认按照小于的方式对 key 进行比较
4. map 中的元素如果用迭代器去遍历，可以得到一个有序的序列
5. map 的底层为平衡搜索树(红黑树)，查找效率比较高 O(logN).
6. 支持 [] 操作符，operator[] 中实际进行插入查找；

4. multimap

我们可以看一下文档介绍：multimap 文档介绍

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

multimap 的使用可以参考 map，功能都是类似的，这里不再作介绍；

注意：

1. multimap 中的 key 是可以重复的。
2. multimap 中的元素默认将 key 按照小于来比较
3. multimap 中没有重载 operator[] 操作，因为 key 是可以重复的，如果此时有多个 key，就不知道返回哪个 key 对应的 value了；而且当有 key 的时候，再来一个 key，就不知道是查找还是修改了。
4. 使用时与map包含的头文件相同：

四、map 和 set 的练习

1. 前K个高频单词

题目链接 -> Leetcode -692.前K个高频单词

Leetcode -692.前K个高频单词

题目：给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

示例 1：
输入 : words = [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2
输出 : [“i”, “love”]
解析 : “i” 和 “love” 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 “i” 在 “love” 之前。

示例 2：
输入 : [“the”, “day”, “is”, “sunny”, “the”, “the”, “the”, “sunny”, “is”, “is”] , k = 4
输出 : [“the”, “is”, “sunny”, “day”]
解析 : “the”, “is”, “sunny” 和 “day” 是出现次数最多的四个单词，
出现次数依次为 4, 3, 2 和 1 次。

注意：
1 <= words.length <= 500
1 <= words[i] <= 10
words[i] 由小写英文字母组成。
k 的取值范围是[1, 不同 words[i] 的数量]

思路是先将 words 中的内容放入 map 中统计次数，再放入优先级队列中按照 cmp 方式进行比较确认优先级；其中 cmp 方法是次数多的优先，如果次数多的就按照字典顺序比较；代码如下：

		class Solution {public:// 仿函数，按照 pair 中的 second 比较，降序；如果 second 相等，按照字典顺序排序class cmp{public:bool operator()(const pair<string, int>& p1, const pair<string, int>& p2){return p1.second < p2.second || (p1.second == p2.second && p1.first > p2.first);}};vector<string> topKFrequent(vector<string>& words, int k){priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> pq;map<string, int> mp;// 先放入 map 中统计次数for (auto& str : words)mp[str]++;// 再放入优先级队列中for (auto& str : mp)pq.push(str);// 取优先级队列的前 k 个vector<string> ret;while (k--){ret.push_back(pq.top().first);pq.pop();}return ret;}};

2. 两个数组的交集

题目链接 -> Leetcode -349.两个数组的交集

Leetcode -349.两个数组的交集

题目：给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：
输入：nums1 = [1, 2, 2, 1], nums2 = [2, 2]
输出：[2]

示例 2：
输入：nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]
输出：[9, 4]
解释：[4, 9] 也是可通过的

提示：
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

思路是将两个数组分别放入 set 中，然后使用双指针找交集； 具体思路如下代码：

		class Solution {public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2){// 将 nums1 和 nums2 分别放入 set 中set<int> s1(nums1.begin(), nums1.end());set<int> s2(nums2.begin(), nums2.end());// 使用双指针的思路// 两个值相等则是交集，同时++；// 两个值不相等则小的那个++；// 直到其中一个结束vector<int> ret;set<int>::iterator it1 = s1.begin(), it2 = s2.begin();while (it1 != s1.end() && it2 != s2.end()){if (*it1 == *it2){ret.push_back(*it1);++it1, ++it2;}else if (*it1 < *it2){++it1;}else{++it2;}}return ret;}};