C++ 关联式容器详解：set、map 及其变体的深度剖析----《Hello C++ Wrold!》(19)--(C/C++)
文章目录
- 前言
- set
-
- set的类模板参数声明
- set的构造函数声明
- set常见的几个接口
- multiset
- map
-
- map的类模板参数声明
- map的构造函数声明
- map常用的几个接口
- multimap
- pair
- 作业部分
-
- sort和stable_sort的区别
前言
在 C++ 标准库中，容器是数据存储和操作的核心工具，而关联式容器凭借其高效的查找、插入和删除特性，在处理需要快速检索的数据时展现出独特的优势。set、multiset、map 和 multimap 作为 C++ 中常用的关联式容器，底层通常基于红黑树实现，这使得它们在保证数据有序性的同时，能将基本操作的时间复杂度控制在 O (log n) 级别，远超序列式容器在查找操作上的表现。
本文将系统地介绍这几类关联式容器的特性、类模板参数、构造函数及常用接口，深入剖析 set 与 map 在存储模型（k 模型与 k-v 模型）上的差异，以及 multiset、multimap 与对应基础容器在去重特性上的区别。此外，还将通过具体的作业案例，展示这些容器在实际问题中的应用，帮助读者理解如何根据场景选择合适的容器，以及如何高效地运用其接口解决问题。无论是对 C++ 初学者巩固容器知识，还是对有经验的开发者优化代码效率，本文都具有一定的参考价值。
set
set的类模板参数声明
set的构造函数声明
eg: set 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[]2.`set`会自动排序和去重 3.里面的`erase`的用法跟其他接口有点不同
而且,传值的话，如果里面没有这个值，是不会报错的;传迭代器，没有这个迭代器，是会报错的
4.这里的`find`跟库函数里面的`find`的对比:这里的find是二分查找--时间复杂度是O(logn)库函数里面的find是暴力遍历--时间复杂度是O(n)
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 sizeinsert erase swap clearfind count lower_bound upper_bound equeal_range其中的
operator[]是传入key，返回value
其中的
insert要重点讲解一下:
插入过程中比较的是
key,所以key相同,value不同的是插入不进来的(map的话)关于
insert的返回值:如果
key已经在树里面，返回pair如果
key不在树里面，返回pair一般常用的用法:eg:C++98 map1.insert(make_pair(\"string\",\"字符串\"))--一般用这个map1.insert(pair(\"string\",\"字符串\"))C++11 多参数的构造函数隐式类型转换map1.insert({\"string\",\"字符串\"})
multimap
这个相较于map的区别就是,他不会去重而已；有俩个接口跟
map不一样1.
multimap没有operator[]
2.multimap的insert的返回值跟map的不一样
注意:
multimap跟unordered_map别搞混了
pair
这个类型可以用来存储两个类型的变量
eg: pairp1(1,\"p\");如果想要自动能推导类型的话,要用
make_pair用法eg: make_pair(1,3)
pair也是支持比较大小的:（默认是升序）是先比first,first一样就比second
引申:函数模板是可以自动推导类型的，但是类模板是不可以的!
作业部分
下列说法正确的是（A）A.set中的某个元素值不能被直接修改B.map和unordered_map都是C++11提供的关联式容器//map是C++98，unordered_map是C++11C.因为map和set的底层数据结构相同，因此在实现时set底层实际存储的是的键值对//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. 两个数组的交集
力扣 349. 两个数组的交集做法:把两个组的值放到两个set中去重，然后依次比较: 1.小的++ 2.相等的话，这个值就是交集值，储存这个值，然后同时++引申:处理差集的话:把两个组的值放到两个set中去重，然后依次比较: 1.小的就是差集里的值，储存这个值，然后小的++2.相等的话就同时++代码展示:class Solution {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++; else if(*it2<*it1) it2++; else{ v.push_back(*it1); it1++;it2++; } } return v; }};力扣 692. 前K个高频单词
力扣 692. 前K个高频单词做法:先放map里面去统计次数,然后排序就可以了(map不能用sort,因为map里面是双向迭代器，sort要求是随机访问迭代器)这里排序有三种方法:1.放vector里用sort2.放vector里用stable_sort3.用两个map->一个map,一个multimap(后者用来比较)引申:要求按字典序排列时，通常是升序比如:a在abc前面引申:
sort里面比较的那个重载的写法eg:
代码展示:class Solution {public:struct Greater{ bool operator() (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就会
