文章目录
前言
在 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[]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 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>一般常用的用法: eg:C++98 map1.insert(make_pair("string","字符串"))--一般用这个 map1.insert(pair<string,string>("string","字符串")) C++11 多参数的构造函数隐式类型转换 map1.insert({"string","字符串"})
multimap
这个相较于map的区别就是,他不会去重而已；有俩个接口跟
map不一样1.
multimap没有operator[]
2.multimap的insert的返回值跟map的不一样
注意:
multimap跟unordered_map别搞混了
pair
这个类型可以用来存储两个类型的变量
eg: pair<int,string>p1(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++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.相等的话就同时++
代码展示:
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个高频单词
做法:先放map里面去统计次数,然后排序就可以了
(map不能用sort,因为map里面是双向迭代器，sort要求是随机访问迭代器)
这里排序有三种方法:
1.放vector里用sort
2.放vector里用stable_sort
3.用两个map->一个<string,int>map,一个<int,string>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就会