【C++】map和set的使用

红太狼 2024-04-26 11:02 85阅读 0赞

![在这里插入图片描述][6ac7346dc5944908b5dd227e55fab217.gif_pic_center]

> ?write in front?  
> ?所属专栏： [C++学习][C]  
> ?️博客主页：[睿睿的博客主页][Link 1]  
> ?️代码仓库：?[VS2022\_C语言仓库][VS2022_C]  
> ?您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！  
> **关注我，关注我，关注我**，你们将会看到更多的优质内容！！

![在这里插入图片描述][85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]

#### 文章目录 ####

*  1. 关联式容器
 *  2. 键值对
 *  3. 树形结构的关联式容器
 *   *  3.1\`set\`：
     *   *  3.1.1:set的介绍：
         *  3.1.2set几个常用函数：
         *   *  a.count函数：
             *  b.find函数：
             *  c.边界处理的函数：
             *   *  lower\_bound和upper\_bound：
             *  equal\_range：
         *  3.1.3set的使用：
     *  3.2\`multiset\`：
     *  3.3\`map\`：
     *   *  3.3.1map的介绍：
         *  3.3.2map的常用函数：
         *   *  a.insert函数：
             *  b.map的遍历：
             *  c.\[\]访问：
         *  3.3.3map的使用：
     *  3.4multimap:
 *  一道经典例题：
 *   *  方法1：
     *  方法2：
     *  方法3（不推荐）：

## 1. 关联式容器 ##

在初阶阶段，我们已经接触过STL中的部分容器，比如：list，vector，deque，forward\_list(C++11)等，这些容器统称为**序列式容器**，因为其底层为**线性序列**的数据结构，里面**存储的是元素本身**。

那什么是**关联式容器**？它与序列式容器有什么区别？  
  关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是`<key, value>`结构的**键值对**，并且在数据检索时比序列式容器效率更高（实现是AVL树，就是**进阶版的二叉搜索树**）。

## 2. 键值对 ##

用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量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)
    {
        }
    };

## 3. 树形结构的关联式容器 ##

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

### 3.1`set`： ###

#### 3.1.1:set的介绍： ####

1.  set是**按照一定次序**存储元素的**容器**
2.  set中的元素**不能在容器中修改**(元素总是const)，但是可以从容器中插入或删除它们。  
    ![在这里插入图片描述][9581745efc774d7d973857fbf5ccdba5.png]
3.  set在底层是用二叉搜索树(**红黑树**)实现的。
4.  与`map`不同，`map`中存储的是真正的键值对`<key, value>`，`set`中只放`value`，但在**底层实际存放**的是`<value, value>`构成的键值对。
5.  set中插入元素时，**只需要插入value**即可，不需要构造键值对。
6.  set中的元素**不可以重复**(因此可以使用set进行去重)。
7.  使用set的**迭代器遍历**set中的元素，可以得到**有序**序列
8.  set中的元素**默认按照小于**来比较：`less<T>`  
    ![在这里插入图片描述][3d8d2a4655614cb99131ed612bde069e.png]
9.  set中查找某个元素，时间复杂度为： l o g 2 n log\_2 n log2n

#### 3.1.2set几个常用函数： ####

和其他容器一样，set的迭代器，构造函数，析构函数，容量,插入删除等函数可以自己去查看文档了，在这里我就讲几个常用和易错的几个函数：

##### a.count函数： #####

![在这里插入图片描述][8fd4f8ae9b7d404a947ea2674f6a8366.png]  
  此函数就是返回val值在set里面有多少个。但是因为set里面的元素不重复，所以这个函数在set里面只可能返回0或1，所以我们查找元素在不在的时候可以使用这个函数。

##### b.find函数： #####

![在这里插入图片描述][2555b5a8db064c97be3fa21433387389.png]  
  其实这个函数也很简单，我们只需要注意一下他的返回值：

*  找到了就返回那个地方的迭代器
 *  没找到就返回末尾的迭代器`end()`

##### c.边界处理的函数： #####

###### lower\_bound和upper\_bound： ######

说白了，这两个函数就是为了`erase()`服务的：他们可以给erase提供一个范围空间，供其删除中间的内容。  
![在这里插入图片描述][60eeeeca20084baa9e7ae8ac50a59f05.png]  
![在这里插入图片描述][4bb42d3c34e7413c8084975b3c552a5f.png]  
由于erase删除的时候是左闭右开的原则，这两个函数根据这个原则，`lower_bound`返回的值是`>=val`的，而`upper_bound`返回的值是>val的（都是为了左开右闭准备的）  
举个?：

multiset<int> s;
    	for (int i = 1; i < 10; i++)
    	{
        
    		s.insert(i * 10);//10 20 30 40 50 60 70 80 90
    	}
    
    	auto itlow = s.lower_bound(30);//30
    	auto itup = s.upper_bound(60);//70
    
    	cout << *itlow << endl;
    	cout << *itup << endl;
    	s.erase(itlow,itup);//左闭右开，删除了30，40，50，60

##### equal\_range： #####

![在这里插入图片描述][fa2975d0c84e49c7b9160136eab1da1f.png]  
  说白了，这个函数也是应该使用在multiset里面更好，他是返回val值的一小段区间，其实也是为了erase这个val值。他返回的这个值是一个pair，第一个其实就相当于`lower__bound`，第二个就相当于`upper__bound`

auto ret = s.equal_range(30);//该函数返回的是一个pair，因为也要左闭右开，所以还是和什么一样，而pair的first是lower，second是upper
    	auto itlow = ret.first;//>=  这里相当于lower_bound
    	auto itup = ret.second;//>	 这里相当于upper_bound
    	cout << *itlow << endl;//
    	cout << *itup << endl;
    	s.erase(itlow,itup);//左闭右开

#### 3.1.3set的使用： ####

set可以进行去重，或者检查有没有重复的元素,比如我们之前做的判断链表是否为环形链表的题，如果我们将链表的结点都存入set，如果发现一样的，那就一定是环形链表了。（判断记得用`count()`更简单）

### 3.2`multiset`： ###

其实有两个函数就是为multiset写的：  
![在这里插入图片描述][a8a0382481cf42dcb46e3af905f61a16.png]  
还要就是在删除`erase(val)`或通过`equal_range()`删除val的时候，会将val值**全部删掉**！！

### 3.3`map`： ###

#### 3.3.1map的介绍： ####

1.  在map中，键值key通常用于排序和唯一的标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型  
    value\_type绑定在一起，为其取别名称为pair:typedef pair<const key, T> value\_type;
2.  在内部，map中的元素总是**按照键值key进行比较排序**的。
3.  map支持下标访问符**加粗样式**，即在\[\]中放入key，就可以找到与key对应的**value**。
4.  map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树)
5.  key的值不能改，value的值可以改：

typedef pair<const key, T> value_type;

#### 3.3.2map的常用函数： ####

##### a.insert函数： #####

对于pair类型，我们该怎么插入呢？有下面几种方法：

map<string, string> mp;
    	//c++98!!
    	//方法一：构造后插入
    	pair<string, string> k1("insert", "插入");
    	mp.insert(k1);
    	//方法二:匿名对象插入
    	mp.insert(pair<string, string> ("sort", "排序"));
    	//方法三：调用make_pair函数
    	mp.insert(make_pair("string", "字符串"));
    
    	//c++11:支持了多参数的构造函数隐式类型转换!!
    
    	mp.insert({
         "map","映射" });

##### b.map的遍历： #####

那么，我们的map如何遍历呢？  
其实还是和其他的容器一样，只是我们的map里面是pair类型，要多一次解引用：

auto it = mp.begin();
    	while (it != mp.end())
    	{
        
    	(*it).second = "xxx";
    	//(*it).first = "xxx";只能修改第二个值，不能修改第一个值
    	cout << (*it).first << " :" << (*it).second << endl;
    	it++;
    	}
    	cout << endl;
    	while (it != mp.end())
    	{
        
    		cout << it->first << " :" << it->second << endl;//这里本来应该是it->->first原本是：
    		//pair<K,V> operator->()
    		//{
        
    			//return &it->val;
    		//}
    		it++;
    	}
    
    	for (const auto& kv : mp)
    	{
        
    		//kv.second = "ccc";
    		cout << kv.first << " :" << kv.second << endl;
    	}

##### c.\[\]访问： #####

如果要通过map来统计次数该如何统计呢？  
通常大家会这样统计：

string arr[] = {
         "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    	map<string, int> mp;
    
    	for (auto& ch : arr)
    	{
        
    		auto it=mp.find(ch);
    		if (it == mp.end())
    		{
        
    			mp.insert({
         ch,1 });
    		}
    		else
    		{
        
    			it->second++;
    		}
    	}

但是还要更简便的方法，那就是使用\[\]。我们先来看看他的使用：  
![在这里插入图片描述][ed32674d5231479d9f4f14ed77368a7f.png]  
实际上这里的源码是这样的：  
![在这里插入图片描述][42e0bd8e64734a5eaca90c3c00a331cd.png]  
这里就不得不说`insert`的返回值了：  
![在这里插入图片描述][68710b23a7bf4827b927ab8ad6453bc4.png]  
所以上面\[\]的实现简化下来是这样的：  
![在这里插入图片描述][c898726ae1e0426aa12c4fe055344ad3.png]  
所以上面的统计次数可以这样来写：

string arr[] = {
         "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
    	map<string, int> mp;
    for (auto& ch : arr)
    	{
        
    		mp[ch]++;
    	}

这样的话，我们就可以通过key来插入/修改value的值了，是不是很方便呢？

#### 3.3.3map的使用： ####

map其实就是一种映射关系，以后只要见到有映射关系的题目都可以通过map来实现：  
比如之前的括号的题目：  
![在这里插入图片描述][b1b2fbf4b74c4a059dfb91b7ad69df77.png]  
还有随机链表复制的题目。

### 3.4multimap: ###

multimap和multiset类似，就是可以存入相同的key的值。

## 一道经典例题： ##

[前k个高频单词][k]  
![在这里插入图片描述][732785890f1c4f77be59eb55a0002c2c.png]  
在学习了map之后，我们就可以通过map进行计数，而且而且！map还顺便排了个序！！虽然不是最终结果，但是还是给我们省了很多步骤。下面有三种方法解决这个问题：

### 方法1： ###

先用map统计次数，而且此时也正好按字典序排序了，但是要按次序排序，而我们map不能通过算法里面的排序（快排是用数组的），所以我们用`vector`来保存`pair`。但是最后在快排的时候，**快排没有稳定性**（**相对位置会改变**），所以我们用另外一个排序，叫`stable_sort`来排序。

class Solution {
        
    public:
    
    	struct Greater
    	{
        
    		bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2)
    		{
        
    			return kv1.second > kv2.second;
    		}
    	};
    	vector<string> topKFrequent(vector<string>& words, int k)
    	{
        
    		map<string, int> countmap;
    		for (const auto& ch : words)
    		{
        
    			countmap[ch]++;
    		}
    		vector<string> v;
    		vector<pair<string, int>>kv(countmap.begin(), countmap.end());
    		stable_sort(kv.begin(), kv.end(), Greater());
    		for (int i = 0; i < k; i++)
    		{
        
    			v.push_back(kv[i].first);
    		}
    		return v;
    	}
    };

### 方法2： ###

其实，我们还可以通过对**仿函数进行限制**，还是可以使用sort函数排序的。此时仿函数的限制就非常的巧妙！！在次数相等的时候让其通过字典序来比！！

class Solution {
        
    public:
    
    	struct Greater
    	{
        
    		bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2)
    		{
        
    			return kv1.second > kv2.second || kv1.second == kv2.second && kv1.first < kv2.first;
    		}
    	};
    	vector<string> topKFrequent(vector<string>& words, int k)
    	{
        
    		map<string, int> countmap;
    		for (const auto& ch : words)
    		{
        
    			countmap[ch]++;
    		}
    		vector<string> v;
    		vector<pair<string, int>>kv(countmap.begin(), countmap.end());
    		sort(kv.begin(), kv.end(), Greater());
    		for (int i = 0; i < k; i++)
    		{
        
    			v.push_back(kv[i].first);
    		}
    		return v;
    	}
    };

### 方法3（不推荐）： ###

multimap在构建的时候，在排序有可能是稳定的（这个看编译器，其他编译器不一定对）。所以如果multimap稳定的情况下，我们就可以在创建一个multimap，来通过次数再来排一次序！

class Solution {
        
    public:
    
    	struct Greater
    	{
        
    		bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2)
    		{
        
    			return kv1.second > kv2.second || kv1.second == kv2.second && kv1.first < kv2.first;
    		}
    	};
    	vector<string> topKFrequent(vector<string>& words, int k)
    	{
        
    		map<string, int> countmap;
    		for (const auto& ch : words)
    		{
        
    			countmap[ch]++;
    		}
    		multimap<int, string, greater<int>> sortMap;
    		for (const auto& e : countmap)
    		{
        
    			sortMap.insert({
         e.second,e.first });
    		}
    
    		vector<string> v;
    		auto it = sortMap.begin();
    		while (k--)
    		{
        
    			v.push_back(it->second);
    			++it;
    		}
    		return v;
    	}
    };

更新不易，辛苦各位小伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

> **专栏订阅：**  
> [每日一题][Link 2]  
> [C语言学习][C 1]  
> [算法][Link 3]  
> [智力题][Link 4]  
> [初阶数据结构][Link 5]  
> [Linux学习][Linux]  
> [C++学习][C]  
> 更新不易，辛苦各位小伙伴们动动小手，?三连走一走?? ~ ~ ~ 你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！

![在这里插入图片描述][55270e2552774a17a711aa978da84193.gif_pic_center]

[6ac7346dc5944908b5dd227e55fab217.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/3355ddee969f4f5bbf58ddd5734192ca.gif
[C]: https://blog.csdn.net/qq_74310471/category_12289978.html
[Link 1]: https://blog.csdn.net/qq_74310471?spm=1000.2115.3001.5343
[VS2022_C]: https://gitee.com/zhangxuruihhhh/c-language-learning
[85d8f838a7524c8bb8bed80b7ac059c1.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/19499bddb5b54205bfdad0aa27d9148e.gif
[9581745efc774d7d973857fbf5ccdba5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/12cf5cf16a384f1fb443c1d12c88b4ac.png
[3d8d2a4655614cb99131ed612bde069e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/5c786ac430484c6593b360e569d56ba0.png
[8fd4f8ae9b7d404a947ea2674f6a8366.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/57fbe9b4769b49faad4a3ab0e1d8c9c3.png
[2555b5a8db064c97be3fa21433387389.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/b29cb6f39304441289ffd973b6f04b37.png
[60eeeeca20084baa9e7ae8ac50a59f05.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/f278904221544061bf3a84b5e6175c05.png
[4bb42d3c34e7413c8084975b3c552a5f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/2be21f054f924a35ad62bdfb13dfa0c4.png
[fa2975d0c84e49c7b9160136eab1da1f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/5905b65231a443ea99620ff6a95c0720.png
[a8a0382481cf42dcb46e3af905f61a16.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/b141886d1dec4eae862c2dfb4e6b9d6d.png
[ed32674d5231479d9f4f14ed77368a7f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/ea30312f90c24ddb8622f082b03a80f4.png
[42e0bd8e64734a5eaca90c3c00a331cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/da831f65b0044845a8178d77544e0e90.png
[68710b23a7bf4827b927ab8ad6453bc4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/ab3481e0d8c3498c937bd41868157e83.png
[c898726ae1e0426aa12c4fe055344ad3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/09a882afc1ee4285beed842aafe61a4e.png
[b1b2fbf4b74c4a059dfb91b7ad69df77.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/3f39dd13b0fc46fe95a810b08be8ba2c.png
[k]: https://leetcode.cn/problems/top-k-frequent-words/description/
[732785890f1c4f77be59eb55a0002c2c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/0b9997946ae04ea08fa96843bcc5620d.png
[Link 2]: https://blog.csdn.net/qq_74310471/category_12166401.html?spm=1001.2014.3001.5482
[C 1]: https://blog.csdn.net/qq_74310471/category_12157207.html?spm=1001.2014.3001.5482
[Link 3]: https://blog.csdn.net/qq_74310471/category_12144452.html?spm=1001.2014.3001.5482
[Link 4]: https://blog.csdn.net/qq_74310471/category_12166402.html
[Link 5]: https://blog.csdn.net/qq_74310471/category_12216969.html?spm=1001.2014.3001.5482
[Linux]: https://blog.csdn.net/qq_74310471/category_12291120.html
[55270e2552774a17a711aa978da84193.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/e3fe24455e5d40baac081a84bed5860d.gif