• map和set详解

    目录

    前言

    一、关联式容器

    1、关联式容器概念

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

    二、set与multiset

    1.set的介绍

    2.set的使用

    2.1set的插入与遍历

    2.2 set的查找与删除

    3、multiset的介绍与使用

    3.1 multiset的遍历

    3.2 multiset的查找

    3.3 multiset的删除

     三、map和multimap

    1、map的介绍

    2、map的使用 

    2.1map的插入

    2.2map的遍历

     2.3通过map的迭代器修改数据

    2.4 统计次数

     2.5 [ ]的扩展学习

    3、multimap

    总结

    前言

    哈喽，小伙伴们大家好。今天我们继续来学习STL容器，今天我将主要介绍map和set的使用。话不多说，拿好小本本，我们赶快开始吧。

    一、关联式容器

    1、关联式容器概念

    在之前我们接触过STL的部分容器，比如vector，deque，list。这些容器统称为序列式容器，底层为线性结构，存储的是元素本身。那什么是关联式容器呢？

    关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器中存储的结构的键值对，有助于数据检索。键值对是一种一一对应的结构，key代表键值，value代表键值所对应的信息。英汉互译词典利用的就是这种结构，即中文和英文一一对应，通过英文就能找到对应的中文。

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

    根据应用场景不同，STL创建了两种关联式容器，分别是树形结构和哈希结构，今天我们主要学习树形结构的容器。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。

    二、set与multiset

    1.set的介绍

    • set是按照一定次序存储元素的容器，set中插入元素时，只需要插入value即可，不需要构造键值对。但在底层实际存放的是由构成的键值对。
    • 在set中，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
    •  set中的底层使用二叉搜索树(红黑树)来实现。

    2.set的使用

    2.1set的插入与遍历

    在插入过程中，遇到重复的值会自动跳过。遍历时借助迭代器，迭代器采用的是树结构的中序遍历，这样遍历出来的数据是有顺序的。

    1. void test_set1()
    2. {
    3. 	set<int> s;
    4. 	s.insert(3);
    5. 	s.insert(1);
    6. 	s.insert(2);
    7. 	s.insert(14);
    8. 	s.insert(36);
    9. 	s.insert(4);
    10. 	s.insert(3);
    11. 	s.insert(3);
    12.     // 遍历方式1：
    13. 	set<int>::iterator it = s.begin();
    14. 	while (it != s.end())
    15. 	{
    16. 		// 不能修改已经插入的值
    17. 		// *it += 1;
    18.         cout << *it << " ";
    19. 		++it;
    20. 	}
    21. 	cout << endl;
    22.     // 遍历方式2：
    23. 	for (auto e : s)
    24. 	{
    25. 		cout << e << " ";
    26. 	}
    27. 	cout << endl;
    28. }

    2.2 set的查找与删除

    查找会返回特定值对应位置的迭代器。如果没有找到则返回尾部的迭代器。删除通常有两种方式，通过值删除或通过查找到的位置删除。

    区别是通过值删除，如果要删除的值没在set中则不处理，也不会报错。而通过查找位置删除，如果找不到还依旧删除则会报错。

    1. void test_set2()
    2. {
    3. 	set<int> s;
    4. 	s.insert(3);
    5. 	s.insert(1);
    6. 	s.insert(2);
    7. 	s.insert(14);
    8. 	s.insert(36);
    9. 	s.insert(4);
    10. 	s.insert(3);
    11. 	s.insert(3);
    12.  
    13. 	// 先查找，找到了再删。没找到，也去删会报错
    14. 	auto pos = s.find(4);
    15. 	if (pos != s.end())
    16. 	{
    17. 		s.erase(pos);
    18. 	}
    19.  
    20. 	pos = s.find(40);
    21. 	//s.erase(pos);
    22. 	if (pos != s.end())
    23. 	{
    24. 		s.erase(pos);
    25. 	}
    26.  
    27. 	// 在就删除，不在就不处理也不报错
    28. 	s.erase(3);
    29. 	s.erase(30);
    30. }

    3、multiset的介绍与使用

    multiset与set的唯一区别是允许键值冗余，可以存储相同的数据，在插入时会统一插入到相同值的右边或最左边，依然保持着大小关系。除了下面几点外，其它与set几乎没有区别。

    3.1 multiset的遍历

    如果multiset中有相同的值，在遍历时会遍历多次。

    1. void test_set3()
    2. {
    3. 	multiset<int> s;
    4. 	s.insert(3);
    5. 	s.insert(1);
    6. 	s.insert(2);
    7. 	s.insert(14);
    8. 	s.insert(36);
    9. 	s.insert(4);
    10. 	s.insert(3);
    11. 	s.insert(3);
    12. 	s.insert(3);
    13.  
    14. 	// 排序
    15. 	multiset<int>::iterator it = s.begin();
    16. 	while (it != s.end())
    17. 	{
    18. 		cout << *it << " ";
    19. 		++it;
    20. 	}
    21. 	cout << endl;
    22. }

    3.2 multiset的查找

    find查到的值有多个时，它得到的是中序的第一个。count函数可以用在计算相同值的个数，这个函数在set中几乎没有意义，因为都是1，但在multiset中可能会用到。

    1. 	// find查找的val有多个的时候，那么他找到的是中序的第一个
    2. 	multiset<int>::iterator pos = s.find(3);
    3. 	while (*pos == 3)
    4. 	{
    5. 		cout << *pos << endl;
    6. 		++pos;
    7. 	}
    8. 	cout << s.count(3) << endl;

    3.3 multiset的删除

    如果在multiset中存在多个相同的值，使用erase函数会删除掉所有值。

    1. void test_set3()
    2. {
    3. 	multiset<int> s;
    4. 	s.insert(3);
    5. 	s.insert(1);
    6. 	s.insert(2);
    7. 	s.insert(14);
    8. 	s.insert(36);
    9. 	s.insert(4);
    10. 	s.insert(3);
    11. 	s.insert(3);
    12. 	s.insert(3);
    13.  
    14. 	multiset<int>::iterator it = s.begin();
    15. 	while (it != s.end())
    16. 	{
    17. 		cout << *it << " ";
    18. 		++it;
    19. 	}
    20. 	cout << endl;
    21.  
    22. 	s.erase(3);
    23. 	it = s.begin();
    24. 	while (it != s.end())
    25. 	{
    26. 		cout << *it << " ";
    27. 		++it;
    28. 	}
    29. 	cout << endl;
    30. }

     三、map和multimap

    1、map的介绍

    • map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
    • 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的。
      内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:   typedef pair value_type;
    • 在内部，map中的元素总是按照键值key进行比较排序的。
    • map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
    • key的值是唯一的，一个key值只能对应一个value，但一个value可以对应多个key。

    2、map的使用 

    2.1map的插入

    STL中提供了pair类把key和value绑定到了一起，所以插入数据时需要插入pair类型对象。可以理解为pair类就是为了map而生的。

     插入pair类型数据时有两种方法，一种是调用pair的构造函数，构造一个匿名对象插入，另一种是直接调用接口。

    1. void test_map1()
    2. {
    3. 	map<int, double> m;
    4. 	// 调用pair的构造函数，构造一个匿名对象插入
    5. 	m.insert(pair<int, double>(1, 1.1));
    6. 	m.insert(pair<int, double>(5, 5.5));
    7. 	m.insert(pair<int, double>(2, 2.2));
    8. 	m.insert(pair<int, double>(2, 3.3)); // key相同就会插入失败
    9.  
    10. 	// 调用函数模板，构造对象，
    11. 	// 好处:是不需要去声明pair的参数，让函数模板自己推演，用起来方便些
    12. 	m.insert(make_pair(2, 2.2));
    13. }

    当类型名称过长时，我们可以通过typedef来简化代码，增强可读性。

    1. void map2()
    2. {
    3.     //项目不展开命名空间，都要指定std，写起来会比较长
    4. 	//std::map dict;
    5. 	//dict.insert(std::pair("insert", "插入"));
    6. 	std::map::iterator it = dict.begin();
    7. 	//auto dit = dict.begin();
    8. 	//while (dit != dict.end())
    9. 	//{
    10. 	//	cout << dit->first << ":" << dit->second << endl;
    11. 	//	++dit;
    12. 	//}
    13. 	//cout << endl;
    14.  
    15. 	// 通过typedef 简化命名
    16. 	typedef std::map DICT;
    17. 	typedef std::pair DICT_KV;
    18. 	typedef std::map::iterator DICT_ITER;
    19.  
    20. 	DICT dict;
    21. 	dict.insert(DICT_KV("insert", "插入"));
    22.     DICT_ITER dit = dict.begin();
    23. 	//auto dit = dict.begin();
    24. 	while (dit != dict.end())
    25. 	{
    26. 		cout << dit->first << ":" << dit->second << endl;
    27. 		++dit;
    28. 	}
    29. 	cout << endl;
    30. }

    2.2map的遍历

    1. dit = dict.begin();
    2. 	while (dit != dict.end())
    3. 	{
    4. 		cout << dit->first << ":" << dit->second << endl;
    5. 		++dit;
    6. 	}
    7. 	cout << endl;

     2.3通过map的迭代器修改数据

    map中的key是不能改变的，但是value可以。map的迭代器返回的是pair元素的位置，可以通过迭代器对pair中的second成员进行修改。

    1. void map3()
    2. {
    3. 	typedef std::map DICT;
    4. 	typedef std::pair DICT_KV;
    5. 	typedef std::map::iterator DICT_ITER;
    6. 	DICT dict;
    7. 	dict.insert(DICT_KV("insert", "插入"));
    8. 	dict.insert(DICT_KV("sort", "排序"));
    9. 	dict.insert(DICT_KV("left", "左边"));
    10. 	// 修改map的value数据
    11. 	auto ret = dict.find("left");
    12. 	if (ret != dict.end())
    13. 	{
    14. 		//ret->second.insert(ret->second.size() - 1, "、剩余");
    15. 		// 可读性优化技巧
    16. 		string& str = ret->second;
    17. 		str.insert(str.size() - 1, "、剩余");
    18. 	}
    19. }

    2.4 统计次数

    方法一：

    查找是否存在，如果第一次存在就插入,后续再出现就把pair的second++。

    1. void count1
    2. {    
    3.     string arr[] = { "香蕉", "苹果", "香蕉", "榴莲", "草莓", "苹果","西瓜", "香蕉", "草莓","西瓜"};
    4.     mapint> countMap;
    5. 	for (const auto& str : arr)
    6. 	{
    7. 		// 思路：第一次出现，插入, 后续再出现就++次数ret->second
    8. 		mapint>::iterator ret = countMap.find(str);
    9. 		if (ret != countMap.end())
    10. 		{
    11. 			ret->second++;
    12. 		}
    13. 		else
    14. 		{
    15. 			countMap.insert(make_pair(str, 1));
    16. 		}
    17. 	}
    18. }
    19.

     方法二：

    我们来看一下map中insert函数的返回值。

     insert会返回一个pair类型的数据，pair的second为一个bool类型，插入成功为true，插入失败为false。而first为一个迭代器，如果新插入的数据不存在，则返回新插入数据的迭代器。如果新插入的数据存在，则返回之前数值相等的旧数据的迭代器。

    1. void count2()
    2. {
    3. 	string arr[] = { "香蕉", "苹果", "香蕉", "榴莲", "草莓", "苹果","西瓜", "香蕉", "草莓","西瓜" };
    4. 	mapint> countMap;
    5. 	for (const auto& str : arr)
    6. 	{
    7. 		// 先插入，如果str已经在map中，insert会返回str所在节点的迭代器，我们++次数即可
    8. 		//pair::iterator, bool>  ret = countMap.insert(make_pair(str, 1));
    9. 		auto ret = countMap.insert(make_pair(str, 1));
    10. 		if (ret.second == false)
    11. 		{
    12. 			ret.first->second++;
    13. 		}
    14. 	}
    15. }

    方法三：

    我们先来看一下map中[]是怎样进行重载的。

    等价于下面的代码： 

     结合insert的返回值看可以的值，[k]等价于k对应的value。

    所以第三种计数方法代码如下：

    1. void count3()
    2. {
    3. 	string arr[] = { "香蕉", "苹果", "香蕉", "榴莲", "草莓", "苹果","西瓜", "香蕉", "草莓","西瓜" };
    4. 	mapint> countMap;
    5. 	for (const auto& str : arr)
    6. 	{
    7. 		countMap[str]++;
    8. 	}
    9.  
    10. 	for (const auto& e : countMap)
    11. 	{
    12. 		cout << e.first << ":" << e.second << endl;
    13. 	}
    14. }

     2.5 [ ]的扩展学习

    1. 	// 关于[]的一些扩展学习
    2. 	map dict;
    3. 	dict.insert(make_pair("sort", "排序"));
    4. 	dict["left"] = "左边";  // 插入+修改
    5. 	dict["insert"]; // 插入
    6. 	dict["insert"] = "插入";     // 修改
    7. 	dict["left"] = "左边、剩余";  // 修改
    8. 	dict.erase("left");

    3、multimap

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

    实际问题：找出大家最喜欢的三种水果

    过程：（1）统计次数（2）排序

    排序方法一：使用multimap

    1. void search_fruit()
    2. {
    3.     string arr[] = { "香蕉", "苹果", "香蕉", "榴莲", "草莓", "苹果","西瓜", "香蕉", "草莓","西瓜" };
    4. 	//统计次数
    5. 	mapint> countmap;
    6. 	for (const auto& str : arr)
    7. 	{
    8. 		countmap[str]++;
    9. 	}
    10.     //因为int的次数可能重复，所以需要使用multimap
    11. 	multimap<int, string> sortmap;
    12. 	for (const auto& e : countmap)
    13. 	{
    14. 		sortmap.insert(make_pair(e.second, e.first));
    15. 	}
    16. 	for (const auto& e : sortmap)
    17. 	{
    18. 		cout << e.second << ":" << e.first << endl;
    19. 	}
    20. }

    排序方法二：使用vector传countmap的迭代器

    1. struct mapit_com
    2. {
    3.     //函数对象
    4. 	bool operator()(mapint>::iterator x,mapint>:: iterator y)
    5. 	{
    6. 		return x->second < y->second;
    7. 	}
    8. };
    9.  
    10. void search_fruit()
    11. {
    12.     string arr[] = { "香蕉", "苹果", "香蕉", "榴莲", "草莓", "苹果","西瓜", "香蕉", "草莓","西瓜" };
    13. 	//统计次数
    14. 	mapint> countmap;
    15. 	for (const auto& str : arr)
    16. 	{
    17. 		countmap[str]++;
    18. 	}
    19.     //利用vector排序
    20.     vectorint>::iterator> sortv;
    21. 	auto countmapit = countmap.begin();
    22. 	while (countmapit != countmap.end())
    23. 	{
    24. 		sortv.push_back(countmapit);
    25. 		countmapit++;
    26. 	}
    27.     sort(sortv.begin(), sortv.end(), mapit_com());
    28. }

    排序方法三：利用set排序，把countmap的迭代器存起来

    1. 	//......
    2.     // 利用set排序  --不拷贝pair数据
    3. 	setint>::iterator, MapItCompare> sortSet;
    4. 	countMapIt = countMap.begin();
    5. 	while (countMapIt != countMap.end())
    6. 	{
    7. 		sortSet.insert(countMapIt);
    8. 		++countMapIt;
    9. 	}
    10.

    总结

    本文主要介绍了map和set的使用，在之后的文章中我将介绍AVL树，并用AVL树来模拟实现map和set，如果小伙伴们有兴趣可以关注我。感谢大家的阅读，山高路远，来日方长，我们下次见。

  • 相关阅读:
    计算params的参数两和flops
    如何用一个插件解决 Serverless 灰度发布难题？
    如何计算 GPT 的 Tokens 数量？
    springboot-starter如何整合阿里云datahub呢？
    使用命令进行把新代码上传到git上
    我用chatgpt写了一款程序
    系统编程 day13 (linux) 共享内存的知识 与函数的运用
    JS——循环结构经典例题解析与分享
    数据加密的常见方法
    mac连不上5gwifi怎么解决 macbook无法连接5g wifi
  • 原文地址：https://blog.csdn.net/weixin_59371851/article/details/126471676