C++ 关联式容器详解：set、map 及其变体的深度剖析----《Hello C++ Wrold!》(19)--(C/C++)
文章目录
前言
在 C++ 标准库中，容器是数据存储和操作的核心工具，而关联式容器凭借其高效的查找、插入和删除特性，在处理需要快速检索的数据时展现出独特的优势。set、multiset、map 和 multimap 作为 C++ 中常用的关联式容器，底层通常基于红黑树实现，这使得它们在保证数据有序性的同时，能将基本操作的时间复杂度控制在 O (log n) 级别，远超序列式容器在查找操作上的表现。
本文将系统地介绍这几类关联式容器的特性、类模板参数、构造函数及常用接口，深入剖析 set 与 map 在存储模型（k 模型与 k-v 模型）上的差异，以及 multiset、multimap 与对应基础容器在去重特性上的区别。此外，还将通过具体的作业案例，展示这些容器在实际问题中的应用，帮助读者理解如何根据场景选择合适的容器，以及如何高效地运用其接口解决问题。无论是对 C++ 初学者巩固容器知识，还是对有经验的开发者优化代码效率，本文都具有一定的参考价值。
set
set的类模板参数声明
set的构造函数声明
eg: set<int> s; set常见的几个接口
operator =:返回的是
begin endrbegin rendcbegin cendcrbegin crend
empty size insert erase swap clear find
lower_bound>=传入值的第一个值upper_bound:返回的是>传入值的第一个值equal_range:第一个迭代器返回的是第一个>=val的值的迭代器，第二个迭代器返回的是第一个>val的迭代器，没有的话，就返回end()那个的迭代器
（注意eg:是查找到的顺序，而不是插入的顺序,因为插入还会涉及到旋转）
count:返回的是里面值为val的个数
注意:1.没有operator[]
而且,传值的话，如果里面没有这个值，是不会报错的;传迭代器，没有这个迭代器，是会报错的
multiset
这个相较于set的区别就是,他不会去重而已；其他的接口跟set一模一样
上面的count和equal_range一般只有multiset会用到
map
相比于set其实就是map是k-v模型,set是k模型
注意:set和multiset的iterator迭代器其实也是const_iterator类型的,map则不是；但是他们都不能修改key
map的类模板参数声明
这里的Cmopare是key进去参与比较的key的类型要是不支持比较大小的话，自己要写仿函数
map的构造函数声明
map常用的几个接口
operator=operator[] begin end rbegin rend cbegin cend crbegin crend empty size insert erase swap clear find count lower_bound upper_bound equeal_range 其中的operator[]是传入key，返回value
其中的insert要重点讲解一下:
插入过程中比较的是key,所以key相同,value不同的是插入不进来的(map的话)
关于insert的返回值:
如果key已经在树里面，返回pair<树里面key所在节点的iterator,false>
如果key不在树里面，返回pair<新插入key所在节点的iterator,true>
multimap
这个相较于map的区别就是,他不会去重而已；有俩个接口跟map不一样
1.multimap没有operator[]
2.multimap的insert的返回值跟map的不一样
注意:multimap跟unordered_map别搞混了
pair
这个类型可以用来存储两个类型的变量
如果想要自动能推导类型的话,要用make_pairpair也是支持比较大小的:（默认是升序）
是先比first,first一样就比second
引申:函数模板是可以自动推导类型的，但是类模板是不可以的!
作业部分
下列说法正确的是（A） A.set中的某个元素值不能被直接修改 B.map和unordered_map都是C++11提供的关联式容器//map是C++98，unordered_map是C++11 C.因为map和set的底层数据结构相同，因此在实现时set底层实际存储的是<key, key>的键值对 //map和set底层结构都是红黑树，而其底层红黑树在实现时并没有区分是存k模型还是kv模型 D.map和multimap中都重载了[]运算符//multimap没有 下面关于set的说法正确的是（B） A.set中一定不能存储键值对，只能存储key//set中可以存储键值对，实例化set时，将set中元素类型设置为pair即可 B.set可以将序列中重复性的元素去除掉 下面关于map和set说法错误的是（C）
A.map中存储的是键值对，set中只储存了key
B.map和set查询的时间复杂度都是O(log_2N)
C.map和set都重载了[]运算符
D.map和set底层都是使用红黑树实现的
力扣 349. 两个数组的交集 做法:把两个组的值放到两个set中去重，然后依次比较: 1.小的++ 2.相等的话，这个值就是交集值，储存这个值，然后同时++ 引申: 处理差集的话: 把两个组的值放到两个set中去重，然后依次比较: 1.小的就是差集里的值，储存这个值，然后小的++ 2.相等的话就同时++ 代码展示:classSolution{public: vector<int>intersection(vector<int>& nums1, vector<int>& nums2){ vector<int>v; set<int>s1(nums1.begin(),nums1.end()); set<int>s2(nums2.begin(),nums2.end());auto it1 = s1.begin();auto it2 = s2.begin();while(it1!=s1.end()&&it2!=s2.end()){if(*it1<*it2) it1++;elseif(*it2<*it1) it2++;else{ v.push_back(*it1); it1++;it2++;}}return v;}};力扣 692. 前K个高频单词 做法:先放map里面去统计次数,然后排序就可以了 (map不能用sort,因为map里面是双向迭代器，sort要求是随机访问迭代器) 这里排序有三种方法: 1.放vector里用sort 2.放vector里用stable_sort 3.用两个map->一个<string,int>map,一个<int,string>multimap(后者用来比较) 引申:要求按字典序排列时，通常是升序 比如:a在abc前面 引申:sort里面比较的那个重载的写法eg:
代码展示:classSolution{public:structGreater{booloperator()(pair<string,int>kv1,pair<string,int>kv2){return kv1.second>kv2.second||(kv1.first<kv2.first&&kv1.second == kv2.second);}}; vector<string>topKFrequent(vector<string>& words,int k){ map<string,int>Map;for(auto e:words) Map[e]++; vector<pair<string,int>>vv(Map.begin(),Map.end());stable_sort(vv.begin(),vv.end(),Greater()); vector<string>v;for(int i =0;i<k;i++){ v.push_back(vv[i].first);}return v;}};sort和stable_sort的区别
stable_sort更稳定，在两个值比较时是相等的话，sort不一定会按原来这俩个数的顺序去排，但是stable_sort就会