devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【C++】map、set，multiset和multimap的使用及底层原理【完整版】_setmuliset遍历

作者：繁依Fanyi0 | 2024-06-04 16:05:49

赞

踩

setmuliset遍历

目录

一、map和set的使用

1、序列式容器和关联式容器

2、set的使用讲解

 3、map的使用讲解

二、multiset和multimap 

1、multiset和multimap的使用

2、OJ题：前k个高频单词

一、map和set的使用

1、序列式容器和关联式容器

序列式容器：vector/list/string/deque

序列式容器才支持push等操作，关联式容器不支持

关联式容器：map/set/unordered_map/unordered_set

set和map的底层实现是平衡搜索二叉树

2、set的使用讲解

  • set就是搜索树中的key模型
  • set的特性：①、会对插入的数据自动排序 ②、set是不允许修改值的 ③、set中不允许出现重复的数值，即使存在，也只会留一个
  • set的遍历：①、迭代器遍历 ②、范围for遍历（因为支持迭代器遍历就一定支持范围for）
  • set的拷贝构造
  • set的插入只有insert，其没有push、pop等，因为它是关联式容器
  • set的find，find找到了会返回被查找元素的迭代器，没找到返回end()，故应检查找没找到
  • 那set的find和库里面提供的find有什么区别呢？
  • 都可实现查找，区别在于效率
  • set是搜索二叉树的：时间复杂度：O（logN），而算法中的是O（N）
  • 算法中的find是个模板，其实现是为了所有容器可以通用它，故set尽量用自己的find 
  • set的删除
  • ①、erase(待删除位置的迭代器)  ②、erase(待删除数据) ③、erase(s.begin(), s.end())【即迭代器头和尾，其效果等价于clear   】

因为set是key模型，是看在不在，如果把中国所有人的信息存入到set中，最多搜索次数才31次，因为搜索二叉树的效率：O（logN）2^31就=20多亿了，这个效率是非常好的

代码如下：

  1. void test_set()
  2. {
  3. 	set<int> s;
  4. 	s.insert(3);
  5. 	s.insert(1);
  6. 	s.insert(4);
  7. 	s.insert(3);
  8. 	s.insert(7);
  9.  
  10. 	//set : 排序+去重
  11. 	set<int>::iterator it = s.begin();
  12. 	while (it != s.end())
  13. 	{
  14. 		cout << *it << " ";
  15. 		++it;
  16. 	}
  17. 	cout << endl;
  18.  
  19. 	//支持迭代器，就支持范围for
  20. 	for (auto e : s)
  21. 	{
  22. 		cout << e << " ";
  23. 	}
  24. 	cout << endl;
  25.  
  26. 	set<int> copy(s);//set的深拷贝
  27. 	for (auto& e : copy)
  28. 	{
  29. 		cout << e << " ";
  30. 	}
  31. 	cout << endl;
  32.  
  33. 	//auto pos = s.find(3);//可用auto推导类型
  34. 	//set<int>::iterator pos = s.find(3);//find查找返回迭代器 
  35. 	find找到了会返回元素的迭代器，没找到返回end()
  36. 	//if (pos != s.end())
  37. 	//{//找到了才能删除
  38. 	//	s.erase(pos);//erase会删除迭代器位置的数据
  39. 	//}
  40. 	//若erase直接给值，若值不存在，也不会报错，但迭代器必须存在那个位置
  41.  
  42. 	set<int>::iterator pos = find(s.begin(), s.end(), 3);//使用算法中的find
  43. 	if (pos != s.end())
  44. 	{
  45. 		s.erase(pos);
  46. 	}
  47.  
  48. 	for (auto& e : s)
  49. 	{
  50. 		cout << e << " ";
  51. 	}
  52. 	cout << endl;
  53. }

运行结果： 

  

 3、map的使用讲解

  • map就是搜索树中的key/value模型
  • map的遍历：①、迭代器遍历 ②、范围for遍历
  • map的类型是pair，pair存的一个是key的，一个是value的类型
  • map的构造函数：①、pair构造函数 ②、make_pair函数模板构造一个pair对象
  1. void test_map1()
  2. {
  3. 	map<int, int> m;
  4. 	//m.insert(1, 1);//编译不通过
  5. 	m.insert(pair<int, int>(1, 1));//pair构造函数，构造一个匿名对象
  6. 	m.insert(pair<int, int>(3, 3));
  7. 	m.insert(pair<int, int>(2, 2));
  8. 	m.insert(make_pair(4, 4));	   //函数模板构造一个pair对象
  9.  
  10. 	map<int, int>::iterator it = m.begin();
  11. 	while (it != m.end())
  12. 	{	//*it等价于pair,而要访问它的成员
  13. 		cout << it->first << ":" << it->second << " " << endl;
  14. 		//也可以用(*it).first    (*it).second
  15. 		//operator* 返回值是节点中值的引用
  16. 		//operator->返回值是节点中值的指针，即pair<k,v>指针
  17. 		//本质上为了可读性，这里省略了一个->
  18. 		++it; 
  19. 	}
  20. 	cout << endl;
  21.  
  22. 	for (auto& e : m)
  23. 	{//first就是key值，即pair中的第一个值，second就是value值，即pair中的第二个值
  24. 		cout << e.first << ":" << e.second << endl;
  25. 	}
  26.  
  27. }

  • map构造函数两种方法的区别

  1.  
  2. void test_map2()
  3. {
  4. 	//一般写项目不会把std库中的全引进来，而是如下代码，make_pair明显更加简洁
  5. 	std::map<std::string, std::string> dict;
  6. 	dict.insert(pair<std::string, std::string>("metric", "米制的"));
  7. 	dict.insert(make_pair("potent", "强大的"));
  8. 	dict.insert(make_pair("deplete", "大量减少"));
  9.  
  10.  
  11. 	std::map<std::string, std::string>::iterator it = dict.begin();
  12. 	while (it != dict.end())
  13. 	{
  14. 		cout << it->first << ":" << it->second << endl;
  15. 		++it;
  16. 	}
  17. 	cout << endl;
  18. }

可见使用make_pair会使代码更简洁

以下是map的应用：统计水果出现的次数【本质是key/value模型的应用】

法一：利用map的find（用key值来查找，而不是value值）

  1. void test_map3()
  2. {
  3. 	//用STL中的map怎么统计水果出现的次数呢？
  4. 	string strs[] = { "西瓜","樱桃","苹果","西瓜","西瓜","西瓜","西瓜","苹果" };
  5. 	map<string, int> countMap;
  6. 	for (auto & str : strs)
  7. 	{
  8. 		map<string, int>::iterator ret = countMap.find(str);
  9. 		if (ret != countMap.end())
  10. 		{
  11. 			ret->second++;//相当于value++
  12. 		}
  13. 		else
  14. 		{
  15. 			//第一次出现，直接插入value为1
  16. 			countMap.insert(make_pair(str, 1));
  17. 		}
  18. 	}
  19.  
  20. 	for (auto& e : countMap)
  21. 	{
  22. 		cout << e.first << ":" << e.second << endl;
  23. 	}
  24. }

法二、map的operator[ ]求解

我们之前学的容器只有string，vector和deque才有operator[ ]，而这里map的operator[ ]还有所不同

下面是operator[ ]的底层

可见给operator[ ]一个key值，它返回对应的value值的引用

那就可以把求水果出现的次数代码用operator[ ]实现进一步优化

  1. void test_map3()
  2. {
  3. 	//用STL中的map怎么统计水果出现的次数呢？
  4. 	string strs[] = { "西瓜","樱桃","苹果","西瓜","西瓜","西瓜","西瓜","苹果" };
  5. 	map<string, int> countMap;
  6. 	for (auto& str : strs)
  7. 	{
  8. 		//法二、operator[]实现
  9. 		countMap[str]++;//给key值:字符串,返回对应value的引用:次数
  10. 	}
  11.  
  12. 	for (auto& e : countMap)
  13. 	{
  14. 		cout << e.first << ":" << e.second << endl;
  15. 	}
  16. }

法三、map的insert求解

operator[ ]的底层是调用insert实现的，故想了解operator[ ]要先了解insert

insert的其中一个版本是

pair<iterator, bool> insert (const value_type& val);

它返回值的意思：

单元素版本：（1）返回pair，其成员pair::first设置为一个迭代器，该迭代器指向新插入的元素或映射中具有等效键的元素。如果插入了新元素，则pair::第二个元素设为true，如果已经存在等效键，则设为false。

理解：

insert对于插入不存在的数据充当插入作用，pair的first指向新插入元素，second设为true，但若插入一个已经存在的数据，insert充当查找作用，pair的first指向之前存在的那个元素，second设为false

利用insert这个版本的特点，我们可以把水果出现的次数再写一个insert的版本

  1. void test_map3()
  2. {
  3. 	//用STL中的map怎么统计水果出现的次数呢？
  4. 	string strs[] = { "西瓜","樱桃","苹果","西瓜","西瓜","西瓜","西瓜","苹果" };
  5. 	map<string, int> countMap;
  6. 	for (auto & str : strs)
  7. 	{
  8. 		//法三、insert实现
  9. 		pair<map<string, int>::iterator, bool> ret = countMap.insert(make_pair(str, 1));
  10. 	    //也可写为auto ret = countMap.insert(make_pair(str, 1));
  11. 		//如果插入成功，那就说明之前在map中没出现过，value为1即可
  12. 		if (ret.second == false)
  13. 		{//插入失败，说明之前存在这个数据,迭代器指向之前出现的那个元素
  14. 			ret.first->second++;//用迭代器访问到这个元素的value值
  15. 		}
  16. 	}
  17.  
  18. 	for (auto& e : countMap)
  19. 	{
  20. 		cout << e.first << ":" << e.second << endl;
  21. 	}
  22. }

那insert是如何实现map的operator[]的？

  • 如果水果不在map中，则[ ]会insert插入pair<str, int()> 等价于 pair<str, 0>，那么返回映射对象（次数）的引用就进行了++1
  • 如果水果在map中，则operator[ ]返回水果对应的映射对象（次数）的引用，对它++

下面讲解下map的operator[ ]的多种功能

  1. void test_map3()
  2. {
  3. 	//用STL中的map怎么统计水果出现的次数呢？
  4. 	string strs[] = { "西瓜","樱桃","苹果","西瓜","西瓜","西瓜","西瓜","苹果" };
  5. 	map<string, int> countMap;
  6. 	for (auto & str : strs)
  7. 	{
  8. 		//法二、operator[]实现
  9. 		countMap[str]++;//给key值:字符串,返回对应value的引用:次数
  10. 	}
  11.  
  12. 	countMap["香蕉"];       //插入,因为第一次出现
  13. 	countMap["香蕉"] = 1;   //修改，因为operator[]返回value的引用，故可修改
  14. 	cout << countMap["香蕉"] << endl;//查找，因为香蕉已经存在了
  15. 	countMap["哈密瓜"] = 5; //插入+修改，哈密瓜第一次出现，并对他的value进行了修改
  16.  
  17. 	map<string, string> dict;
  18. 	dict.insert(make_pair("sort", "排序"));
  19. 	dict["string"];//key为string，value是string类型的构造函数【因为其是缺省值】，即空串  //插入（一般不会这样用）
  20. 	dict["string"] = "字符串";//返回value的引用，可以对其进行修改，能修改是因为返回value的引用 //修改，不算插入因为已存在
  21. 	dict["left"] = "左边";//插入+修改，因为"左边"第一次出现，故插入，插入后又对其value进行了修改
  22. 	
  23. 	for (auto& e : countMap)
  24. 	{
  25. 		cout << e.first << ":" << e.second << endl;
  26. 	}
  27. }

注：传参只能传key，不能只传value不传key，因为底层是搜索树，搜索树要用key去比较大小，key只要进去了就不能修改了

一般使用operator[]去

  • 插入+修改
  • 修改

一般不会用它去查找，因为如果key不在会插入数据

总结：

二、multiset和multimap 

1、multiset和multimap的使用

 multiset和multimap除了在set和map的基础上支持数据重复出现外，根本没什么区别

  1. void test_multi()
  2. {
  3. 	//与set的区别是允许键值key冗余（重复）
  4. 	multiset<int> ms;
  5. 	ms.insert(3);
  6. 	ms.insert(2);
  7. 	ms.insert(3);
  8. 	ms.insert(1);
  9. 	ms.insert(4);
  10. 	ms.insert(5);
  11.  
  12. 	for (auto e : ms)
  13. 	{
  14. 		cout << e << " ";
  15. 	}
  16. 	cout << endl;
  17.  
  18. 	auto pos = ms.find(3);
  19. 	cout << *pos << endl;
  20. 	++pos;
  21. 	cout << *pos << endl;
  22. 	++pos;
  23.  
  24. 	//multi_map和map的区别和set与multi_set的区别一样
  25. 	//额外区别是muti_map没有operator[]，因为当有多个相同的可以时，不知道返回哪个key对应的value
  26. 	multimap<string, int> mm;
  27. 	mm.insert(make_pair("苹果", 1));
  28. 	mm.insert(make_pair("苹果", 1));
  29. 	mm.insert(make_pair("苹果", 3));
  30. 	mm.insert(make_pair("西瓜", 2));
  31. 	mm.insert(make_pair("西瓜", 1));
  32.  
  33.  }

2、OJ题：前k个高频单词

思路：

①、先创建个map对象，利用operator[ ]对其中的字符串排序（会按ASCII码排序），那么key值应该是string，因为map是按照key值从低到高排序的 

②、因为出现频率高的在前，且还有重复数据的出现，故使用multimap和仿函数

把countMap中的数据插入到multimap中，multimap的key值是int类型的，那相当于multimap按出现频率排序，那出现频率高的就会在前，而出现频率相同的，之前operator[ ]已排好序了，按字典顺序排的，小的ASCII码在前

③、因为返回vector<string>，故只把multimap中的string存入到结果中即可，访问他的string即迭代器位置->second

  1. class Solution {
  2. public:
  3. 	vector<string> topKFrequent(vector<string>& words, int k) {
  4. 		map<string, int> countMap;
  5. 		//统计每个字符串出现了多少次
  6. 		for (auto& e : words)
  7. 		{
  8. 			countMap[e]++;//map会自动对key值排序，即对string排序，并修改对应的value值
  9. 		}
  10. 		//但我们现在需对value值排序，即对int排序,因为要找出现频率高的
  11. 		
  12. 		//法一、将pair<string, int>键值对放到vector中，用sort排序，还要写一个
  13. 		//按int比较的仿函数，因为sort是快排实现的，不稳定，排完了，还需对次数相同的按字母排,要存入vector是因为
  14. 		//sort只供支持随机访问的容器使用，如vector、deque
  15.  
  16. 		//法二、用multimap按次数排序，利用仿函数控制从大到小排
  17. 		multimap<int, string,greater<int>> sortMap;//multimap可以保证数据的重复出现
  18. 		for (auto& kv : countMap)
  19. 		{
  20. 			sortMap.insert(make_pair(kv.second, kv.first));//排完序后插入到multimap,其会按int从大到小排
  21. 			//排完后
  22. 			//出现次数高的在前面，而出现次数相同的，之前已用operator[]按string排序了
  23. 		}
  24.  
  25. 		vector<string> v;
  26. 		auto it = sortMap.begin();
  27. 		while (it != sortMap.end())
  28. 		{
  29. 			if (k == 0)
  30. 				break;
  31. 			v.push_back(it->second);//插入字符串
  32. 			++it;
  33. 			--k;//插入完一个就--
  34. 		}
  35.  
  36. 		return v;
  37. 	}
  38. };
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/672528
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号