c++ map与multiset的介绍
STL的两种容器
1、序列式容器
按物理存储顺序线性排列，元素间无严格关联（交换位置不破坏结构），通过 “位置索引”（如下标、迭代器顺序）访问。
| 容器类型 | 特点与典型场景 | |
|---|---|---|
vector | 动态数组，随机访问快，尾部增删高效 | |
list | 双向链表，任意位置增删高效（O (1)） | |
deque | 双端队列，支持首尾高效增删、随机访问 | |
array | 静态数组，大小编译期确定，更接近原生数组 | |
forward_list | 单向链表，空间更紧凑，仅支持前向遍历 |
关联式容器
⾮线性结构， 两个位置有紧密的关联关系（交换位置破坏结构）。如：set、map、unordered_set、unordered_map等。
map和set底层是红⿊树，红⿊树是⼀颗平衡⼆叉搜索树。set是key搜索场景的结构， map是key/value搜索场景的结构。（）
相当于在地下停车场，key是车牌，而value对应停车时间，车位信息。
set
set类的介绍
1.set的底层是平衡二叉树/二叉搜索树（红黑树），增删查效率是O(logN) ，迭代器遍历是⾛的搜索树的中序，是有序的，
2、set元素有唯一的key值，set底层是⽤红⿊树实现，增删查效率是 O(logN) ，迭代器遍历是⾛的搜索树的中序，所以是有序。
3.set中的元素不能被修改，因为set在底层是用二叉搜索树来实现的，若是对二叉搜索树当中某个结点的值进行了修改，那么这棵树将不再是二叉搜索树。
注：红黑树包含二叉搜索树。
| 成员函数 | 功能描述 |
|---|---|
insert | 插入指定元素，保证元素唯一性，插入重复元素会被忽略 |
erase | 删除指定元素，可根据值或迭代器删除，删除成功返回受影响元素数量（一般为 1，删除迭代器指向元素时无返回值相关严格数量含义 ） |
find | 查找指定元素，找到则返回指向该元素的迭代器，未找到返回 end() 迭代器 |
size | 获取容器中元素的个数，返回 size_type 类型值（通常是无符号整数 ） |
empty | 判断容器是否为空，为空返回 true，否则返回 false |
clear | 清空容器，删除所有元素，使容器大小变为 0 |
swap | 交换两个 set 容器中的数据，需保证两个容器类型匹配（相同模板参数 ） |
count | 获取容器中指定元素值的元素个数，因 set 元素唯一，返回值只能是 0 或 1 |
set定义
insert与迭代器
#include<iostream>
using namespace std;
#include<set>
#include<string>
int main()
{//去重+升序排序set<int> s;//去重+降序排序//set<int, greater<int>> s;//插入一个值s.insert(5);s.insert(2);s.insert(1);//（正向）迭代器set<int>::iterator it = s.begin();//auto it=s.begin();while (it != s.end()){//*it=1;不能常量赋值cout << *it << " ";++it;}cout << endl;//（反向迭代器）set<int>::reverse_iterator rit = s.rbegin();while (rit!=s.rend()){cout << *rit << " ";rit++;}cout << endl;//插入一段值，相同则失败s.insert({ 2,4,5 });//范围for遍历for(auto e : s){cout << e << " ";}cout << endl;//遍历string比较ascll码的大小比较set<string> s2 = { "apple","banana","mango" };for (auto& e : s2){cout << e << " ";}return 0;
}find和erase，set函数的使用
#include<iostream>
using namespace std;
#include<set>
#include<string>
int main()
{set<int> s = { 2,4,6,7,8,3 };//删除最小值s.erase(s.begin());for (auto e : s){cout << e << " ";}cout << endl;//查找删除int x;cin >> x;auto un = s.find(x);if (un != s.end()){s.erase(un);}else {cout << "没有" << endl;}for (auto e : s){cout << e << " ";}//算法库实现的查找O(n)auto pos1 = find(s.begin(), s.end(),x);// set⾃⾝实现的查找O(logN)auto pos2 = s.find(x);//利用count间接查找int v;cin >> v;if (s.count(v)){cout << v << "在" << endl;}else {cout << v << "不在" << endl;}// 查找个数cout << s.count(2) << endl;//容器大小cout << s.size() << endl;//容器判空cout << s.empty() << endl;//交换两个容器set<int> s1{ 11,22,33,44 };s.swap(s1);return 0;
}
查找并删除一段区间
int main()
{std::set<int> s;for (int i = 1; i < 10; i++)s.insert(i * 10);for (auto e : s){cout << e << " ";}cout << endl;//查找一段区间//[itlow,itup)包含[30,60]auto itlow = s.lower_bound(30);auto itup = s.upper_bound(60);//删除这区间s.erase(itlow, itup);for (auto e : s){cout << e << " ";}return 0;
}
multiset
multiset和set的使⽤基本完全类似，主要区别点在于multiset⽀持值冗余，那么 insert/find/count/erase都围绕着⽀持值冗余有所差异，具体参看下⾯的样例代码理解
#include<iostream>
#include<set>
using namespace std;
int main()
{// 相⽐set不同的是，multiset是排序，但是不去重multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };auto it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;// 相⽐set不同的是，x可能会存在多个，find查找中序的第⼀个int x;cin >> x;auto pos = s.find(x);while (pos != s.end() && *pos == x){cout << *pos << " ";++pos;}cout << endl;cout << s.count(x) << endl;// 相⽐set不同的是，count会返回x的实际个数// 相⽐set不同的是，erase给值时会删除所有的xs.erase(x);for (auto e : s){cout << e << " ";}cout << endl;return 0;
}