【C++/STL】：set和map的介绍及基本使用

目录

• 前言
• 一，树形结构的关联式容器
• 二，set
• • 1，set 的介绍
  • 2，set 常用接口的使用
  • • (1) set 的插入，迭代器遍历
    • (2) set 的区间构造，范围for
    • (3) set 的删除
    • 三，multiset
    • • 1, multiset 的介绍
      • 2，multiset 的简单使用
      • 四，map
      • • 1，map 的介绍
        • 2，map 常用接口的使用
        • • (1) map 的构造
          • (2) map 的迭代器和范围 for
          • 3，map 中的下标访问符 [ ]
          • • (1)，下标访问符 [ ] 的多种功能
            • (2)，统计字符串个数示例
            • 五，multimap
            • • 1，multimap 的介绍
              • 2，multimap 的简单使用

                前言

                在前面，我们已经接触过STL中的部分容器，比如：vector、list、deque等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？

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

                一，树形结构的关联式容器

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

                二，set

                1，set 的介绍

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

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

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

                注意：

                (1) set中的元素不可以重复(因此可以使用set进行去重)。

                (2) 使用set的迭代器遍历set中的元素，可以得到有序序列。

                (3) set中的元素默认排升序。

                (4) set中查找某个元素，时间复杂度为： l o g 2 n log_2 n log2​n。

                2，set 常用接口的使用

                使用set容器要包含头文件：

                #include 
                

                

                set 常用接口的使用举例：

                (1) set 的插入，迭代器遍历

                功能：排序+去重。

                void test_set1()
                {
                	//K模型搜索
                	//排序+去重
                	//插入
                	set s1;
                	s1.insert(1);
                	s1.insert(6);
                	s1.insert(4);
                	s1.insert(1);
                	s1.insert(14);
                	s1.insert(2);
                	s1.insert(5);
                	set::iterator it = s1.begin();
                	while (it != s1.end())
                	{
                		cout 
                	//区间构造
                	vector 2,8,4,6,3,9,2,4,5 };
                	set
                	set 6,9,2,7,3,4,7,8 };
                	for (auto e : s3)
                		cout 
                	//K模型搜索
                	//排序 不去重，允许冗余
                	//插入
                	multiset
                		cout 
                	map "string","字符串" });
                	// 5.initializer_list构造
                	map { "left", "左边" } ,{ "string","字符串" } ,{"right", "右边"} };
                }
                
                	map "string","字符串" });
                	//initializer_list构造
                	map { "left", "左边" } ,{ "string","字符串" } ,{"right", "右边"} };
                	//迭代器遍历
                	map
                		//it-first += 'x'; //err
                		//it-second += "x"; //ok
                		//cout 
                	pair
                	map "string","字符串" });
                	//插入(一般不这么用)
                	dict["right"];
                	//插入+修改
                	//operator[]返回的是value的引用，进行修改
                	dict["left"] = "左边";
                	//查找
                	cout 
                	//统计字符串个数
                	string arr[] = { "西瓜", "西瓜", "苹果", "西瓜",  "西瓜","香蕉", "苹果","西瓜", "香蕉","草莓" };
                	map
                		auto it = countMap.find(kv);
                		if (it != countMap.end()) //前面出现过
                			it-second++;
                		else
                			 //第一次出现
                			countMap.insert({ kv, 1}); //隐式类型转换
                	}
                	for (const auto& kv : countMap)
                		cout 
                	//统计字符串个数
                	string arr[] = { "西瓜", "西瓜", "苹果", "西瓜",  "西瓜","香蕉", "苹果","西瓜", "香蕉","草莓" };
                	map
                		countMap[kv]++;
                		// 插入第一个，key是苹果，不存在，插入成功，
                		// 此时value是0，插入成功后返回value的引用再++就变成1了
                	}
                	
                	for (const auto& kv : countMap)
                		cout 
                	string arr[] = { "西瓜", "西瓜", "苹果", "西瓜",  "西瓜","香蕉", "苹果","西瓜", "香蕉","草莓" };
                	map
                		countMap[kv]++;
                		//插入第一个，key是苹果，不存在，插入成功，
                		// 此时value是0，插入成功后返回value的引用再++就变成1了
                		//对次数排序，当有重复值时，要用multimap
                		multimap
                			sortMap.insert({ kv.second, kv.first });
                		}
                		
                		for (const auto& kv : sortMap)
                			cout