【C++】set和map
set和map
1、序列式容器和关联式容器
前面STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间⼀般没有紧密的关联关系，比如交换⼀下，他依旧是序列式容器。
关联容器也是用来存储数据的与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，里面是<key,value>结构的键值对，两个位置有紧密的关联关系，交换⼀下，他的存储结构就被破坏了。
map和set底层是红黑树，红黑树是一颗平衡二叉搜索树。set是key搜索场景的结构，map是key/value搜索场景的结构。
2、set
2.1 set的介绍
- set是按照一定次序存储元素的容器
- 在set中的元素的value也标识它，并且每个value必须是唯一的，set中的元素不能在容器中修改，但可以从容器中插入或删除它们
- 在内部，set中的元素总是按照其内部比较对象指示的特定严格弱排序标准进行排序
- set容器通过key访问单个元素总是按照其内部比较对象所指示的特定严格弱排序
- set中的值不能修改，数量可以变
- set底层是用红黑树实现，增删查效率是O(㏒N)
总结set两大核心特性：
- 自动去重：不能存放相同元素，插入重复值会直接失效
- 自动升序排序：容器内元素永远从小到大有序
2.2 set的使用
2.2.1 set的模版参数列表
template<classT,// set::key_type/value_typeclassCompare=less<T>,// set::key_compare/value_compareclassAlloc=allocator<T>// set::allocator_type>classset;T是set中存放元素的类型，成员类型key和value的混叠，compare是仿函数，Alloc是set中元素的空间管理方式
2.2.2 set的构造
| 构造类型标识 | 完整函数声明 |
|---|---|
| 构造空的set | explicit set (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); |
| 用[first, last)区间中的元素构造set | template set (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); |
| set的拷贝构造 | set (const set& x); |
2.2.3 set的迭代器
| 函数 | 返回值 | 作用 |
|---|---|---|
| begin() | iterator | 返回指向集合最小元素的正向迭代器 |
| end() | iterator | 返回集合末尾后一位（无有效元素，终止标记） |
| cbegin() | const_iterator | 常量正向首迭代器，只读 |
| cend() | const_iterator | 常量正向尾后迭代器 |
| rbegin() | reverse_iterator | 反向首迭代器（指向最大元素） |
| rend() | reverse_iterator | 反向尾后迭代器 |
| crbegin() | const_reverse_iterator | 常量反向首迭代器 |
| crend() | const_reverse_iterator | 常量反向尾后迭代器 |
set<int>s={5,1,5,3,4,2,6,83,9,10,22};// 中序，排序+去重set<int>::iterator it=s.begin();while(it!=s.end()){// 普通迭代器也不支持修改// *it = 1;cout<<*it<<" ";++it;}//输出1 2 3 4 5 6 9 10 22 83cout<<endl;2.2.4 set的增删查
| 函数名 | 功能分类 | 核心作用 | 返回值 | 简易示例 |
|---|---|---|---|---|
| insert | 修改操作 | 插入元素，自动去重排序，重复插入无效 | pair<iterator, bool> | s.insert(6); |
| erase | 修改操作 | 删除元素，支持值 / 迭代器 / 区间三种传参 | 删除迭代器无返回；传值返回删除个数 | s.erase(6); |
| swap | 修改操作 | 交换两个同类型 set，交换元素、比较器、分配器 | void | s1.swap(s2); |
| clear | 修改操作 | 清空容器所有元素，size 置 0 | void | s.clear(); |
| find | 查找操作 | 查找指定值，找到返回对应迭代器，未找到返回 end () | iterator / const_iterator | auto it = s.find(3); |
| count | 查找操作 | 统计目标元素数量，set 元素唯一，仅返回 0 或 1 | size_t | if(s.count(2)) |
| lower_bound | 边界查找 | 返回第一个大于等于目标值的迭代器 | iterator / const_iterator | s.lower_bound(4); |
| upper_bound | 边界查找 | 返回第一个大于目标值的迭代器 | iterator / const_iterator | s.upper_bound(4); |
set的使用案例：
set<int>s={5,1,5,3,4,2,6,83,9,10,22};set<int>::iterator it=s.begin();while(it!=s.end()){// 普通迭代器也不支持修改// *it = 1;cout<<*it<<" ";++it;}//输出1 2 3 4 5 6 9 10 22 83cout<<endl;s.insert(60);s.erase(6);for(autoe:s){cout<<e<<" ";}cout<<endl;//输出：1 2 3 4 5 9 10 22 60 83//两个find函数时间复杂度不一样autoret1=s.find(3);// O(logN)// auto ret1 = find(s.begin(), s.end(), 3); // O(N)if(ret1!=s.end()){cout<<"找到3了"<<endl;}else{cout<<"没有找到"<<endl;}if(s.count(3))//count用来计数，如果count不为0，则含有3{cout<<"找到3了"<<endl;}else{cout<<"没有找到"<<endl;}// [3, 9]// >= 3autoit1=s.lower_bound(3);//3// > 9autoit2=s.upper_bound(9);//10// [it1, it2)for(autoit=it1;it!=it2;++it){cout<<*it<<" ";}cout<<endl;//输出3 4 5 9s.erase(it1,it2);//删除3 4 5 9for(autoe:s){cout<<e<<" ";}cout<<endl;//输出1 2 10 22 60 833、multiset
- multiset是按照特定顺序存储元素的容器，且其中元素可以重复
- 在multiset中，元素的value也标识了它
- 在内部，multiset中的元素总是按照其内部的比较对象指示的特定严格若序准则排序
- multiset的底层结构是二叉搜索树
总结multiset的核心三大特性：
- 允许存放重复元素
- 自动升序排序
- 相同值会全部保留
multiset和set的接口相同，multiset的使用案例如下：
multiset<int>s={5,1,5,3,4,2,6,83,5,5,9,9,22};//允许重复// 中序，排序set<int>::iterator it=s.begin();while(it!=s.end()){// 普通迭代器也不支持修改//*it = 1;cout<<*it<<" ";++it;}cout<<endl;//输出1 2 3 4 5 5 5 5 6 9 9 22 83s.insert(5);for(autoe:s){cout<<e<<" ";}cout<<endl;//输出1 2 3 4 5 5 5 5 5 6 9 9 22 83intx;cin>>x;autopos=s.find(x);//遍历所有等于x的元素while(pos!=s.end()&&*pos==x){cout<<*pos<<" ";++pos;}cout<<endl;//输入5，输出5 5 5 5 5cout<<s.erase(5)<<endl;//返回值是本次删除的元素的总数量//输出5for(autoe:s){cout<<e<<" ";}cout<<endl;//输出1 2 3 4 6 9 9 22 83cout<<s.count(9)<<endl;//剩余容器中有2个9，输出24、map
4.1 map的介绍
- map是关联容器，它按照特定的顺序排序，存储由键值key和value组合而成
- 在map中，键值key通常用于排序和唯一标识元素，在map内部，key与value通过成员类型value_type绑定在一起，叫做pair
总结map核心特性：
- 有序：底层是红黑树，内部从小到大排序
- 键唯一：同一个key只能有一条数据
- key不能修改：pair的first（key）是const,不能改，value可以修改
4.2 map的使用
4.2.1 map的模板参数说明
template<classKey,// map::key_typeclassT,// map::mapped_typeclassCompare=less<Key>,// map::key_compareclassAlloc=allocator<pair<constKey,T>>//map::allocator_type>classmap;- key：键值对key类型
- T：键值对value类型
- Compare：比较器的类型
- Alloc：通过空间配置器来申请底层空间，不需要用户传递
4.2.2 map的构造
| 构造函数类型 | 函数原型 | 核心功能与说明 |
|---|---|---|
| 空构造（默认构造） | explicit map (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); | 创建一个空的 map 容器，可自定义 key 的比较规则（comp）和内存分配器（alloc），默认使用<升序比较、标准分配器 |
| 范围构造 | template map (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); | 从迭代器范围[first, last)中拷贝元素初始化 map，支持自定义比较规则和分配器 |
| 拷贝构造 | map (const map& x); | 用已有的 map 对象x，创建一个完全相同的副本 |
4.2.3 map的迭代器
| 函数名 | 返回迭代器类型 | 遍历方向 | 读写权限 |
|---|---|---|---|
| begin() | iterator 正向迭代器 | 从小到大（升序） | 可读、可修改 value |
| end() | iterator 正向尾后迭代器 | - | - |
| rbegin() | reverse_iterator 反向迭代器 | 从大到小（降序） | 可读、可修改 value |
| rend() | reverse_iterator 反向尾后迭代器 | - | - |
| cbegin() | const_iterator 常量正向迭代器 | 从小到大（升序） | 仅可读，禁止修改 value |
| cend() | const_iterator 常量正向尾后迭代器 | - | - |
| crbegin() | const_reverse_iterator 常量反向迭代器 | 从大到小（降序） | 仅可读，禁止修改 value |
| crend() | const_reverse_iterator 常量反向尾后迭代器 | - | - |
4.2.4 map的容量
| 函数名 | 函数原型 | 返回值 | 功能说明 | 代码示例 |
|---|---|---|---|---|
| empty() | bool empty() const; | true / false | 判断容器是否为空：1. 无元素返回 true2. 存在元素返回 false | if(mp.empty()) cout << "空容器"; |
| size() | size_type size() const; | 无符号整数（元素总个数） | 获取 map 当前存储的键值对总数 | cout << "元素数量：" << mp.size(); |
4.2.5 map的元素访问
T&operator[](constkey_type&k);三个核心行为：
- 赋值写入：已有该键，直接覆盖对应的value
map<int,string>mp;mp[1]="A";mp[1]="B";// key=1已存在，覆盖值为"B"- 读取取值：用下标读取已有键，拿到value引用
cout<<mp[1];// 输出Bmp[1]+="123";// 通过引用修改值- 自动插入：访问不存在的key时，自动新建键值对存入 map，value 默认初始化。
string s=mp[99];// 原本无key=99，执行后自动插入 {99, ""}总结示例：
voidtest_map1(){map<string,string>dict={{"left","左边"},{"right","右边"},{"insert","插入"},{"string","字符串"}};dict.insert(pair<string,string>("sort","排序"));dict.insert(make_pair("const","常量属性"));dict.insert({"string","字符串"});// 推荐dict.insert({"string","xxxx"});// 插入失败，插入只看keydict["set"];// 插入dict["set"]="集合";// 修改dict["string"]="xxxx";// 修改dict["begin"]="开始";// 插入+修改cout<<dict["set"]<<endl;// 查找 输出：集合}4.2.6 map中元素的修改
| 函数 | 重载形式 | 核心功能 | 返回值 | 关键特性 & 示例 |
|---|---|---|---|---|
| insert | 1.insert(pair<Key,T>)2.insert({k,v})3.insert(first,last) | 插入键值对 | pair<iterator, bool> / iterator | key 重复则插入失败，不会覆盖原有 valuemp.insert({“apple”, “苹果”}); |
| erase（重载 1） | size_type erase(const key_type& k) | 根据 key 删除对应元素 | size_type（0 或 1） | key 不存在不报错；map 键唯一最多删 1 个int cnt = mp.erase(“apple”); |
| erase（重载 2） | iterator erase(iterator it) | 删除迭代器指向单个元素 | 被删元素的下一个迭代器 | 必须保证 it 合法有效，不能传 end ()auto it = mp.find(2); mp.erase(it); |
| erase（重载 3） | void erase(iterator first, iterator last) | 删除区间[first, last)全部元素 | void（无返回） | 左闭右开区间，批量删除一段连续元素mp.erase(mp.begin(), mp.find(3)); |
| swap | void swap(map& x) | 交换两个同类型 map 全部内容 | void | 只交换内部指针，效率极高，不拷贝元素mp1.swap(mp2); |
| clear | void clear() | 清空容器所有键值对 | void | 执行后size()=0，empty()=truemp.clear(); |
| find | iterator find(const key_type& k) | 查找指定 key | iterator | 找到返回元素迭代器，没找到返回end()，不新增元素auto it = mp.find(“test”); |
| count | size_type count(const key_type& k) | 统计 key 存在次数 | size_type（0 或 1） | map 键唯一，仅用来判断 key 是否存在if(mp.count(“test”)){} |
4.3 map的使用案例
voidtest_map1(){pair<string,string>kv1("sort","排序");//pair<string, string> kv2("left", "左边");//pair<string, string> kv3("right", "右边");//pair<string, string> kv4 = { "insert", "插入" };//map<string, string> dict = { kv1, kv2, kv3};map<string,string>dict={{"left","左边"},{"right","右边"},{"insert","插入"},{"string","字符串"}};dict.insert(pair<string,string>("sort","排序"));dict.insert(make_pair("const","常量属性"));dict.insert({"string","字符串"});// 推荐dict.insert({"string","xxxx"});// 插入失败，插入只看keydict["set"];// 插入dict["set"]="集合";// 修改dict["string"]="xxxx";// 修改dict["begin"]="开始";// 插入+修改cout<<dict["set"]<<endl;// 查找//map<string, string>::iterator it = dict.begin();autoit=dict.begin();while(it!=dict.end()){// key不能修改，value可以修改// it->first += 'x';it->second+='x';//cout << (*it).first << ":" << (*it).second << endl;//cout << it.operator->()->first << ":" << it->second << endl;cout<<it->first<<":"<<it->second<<endl;++it;}cout<<endl;/*for (auto& kv : dict) { cout << kv.first << ":" << kv.second << endl; }*/for(auto&[k,v]:dict){cout<<k<<":"<<v<<endl;}// 结构化绑定 C++14/17auto[x,y]=kv1;//x1等价于kv1.first 的别名，y1相当于kv1.second的别名auto&[x1,y1]=kv1;x1+='x';//只改副本，不影响原kv1x+='k';string arr[]={"苹果","西瓜","苹果","西瓜","苹果","苹果","西瓜","苹果","香蕉","苹果","香蕉"};map<string,int>countMap;//for (auto& str : arr)//{// //map<string, int>::iterator it = countMap.find(str);// auto it = countMap.find(str);// if(it != countMap.end())// {// it->second++; //first是key，second是value，first不能修改// }// else// {// countMap.insert({str, 1});// }//}for(auto&str:arr){countMap[str]++;}for(auto&[k,v]:countMap){cout<<k<<":"<<v<<endl;}}5、multimap
5.1 multimap的介绍
- multimap是关联式容器，存储由key和value映射成的键值对<key, value>，其中多个键值对之间的key是可以重复的
- 在内部，multimap中的元素总是通过内部的比较对象，按照指定的特定严格弱排序标准对key进行排序的
- multimap以二叉搜索树的形式实现
multimap核心特征总结：
map：同一个key只能存1份，key唯一；multimap允许多个元素拥有完全相同的key，一个key可以对应多组不同value，eg:
mp.insert({1,"A"});mp.insert({1,"B"});// 合法，同key共存注意：
- multimap不支持 operator[] 下标运算符 mp[key]，因为multimap存在重复key，编译器无法确定你要访问哪一个key对应的value
- insert 永远插入成功
5.2 multimap的使用
multimap的接口可以参考map
voidtest_map2(){multimap<string,string>dict={{"left","左边"},{"right","右边"},{"insert","插入"},{"string","字符串"}};dict.insert(pair<string,string>("sort","排序"));dict.insert(make_pair("const","常量属性"));dict.insert({"string","字符串"});// 推荐dict.insert({"string","xxxx"});// 插入失败，插入只看key}