容器讲解之set和map
目录
一、set
1、set介绍：
set文档链接：set - C++ Reference (cplusplus.com)
C++中的set用来存储非重复（唯一）元素，并按照默认升序自动排序。set的底层是红黑树，查找、删除、插入的效率都很高（logN）。
2、set的构造
上面的是98标准的set构造，从上到下分别为默认构造、迭代器区间构造以及拷贝构造。
在11标准后，set还支持initializer_list构造，其支持初始化列表构造。
例如：
3、set的迭代器
set的迭代器是一个双向迭代器，能够使用范围for进行遍历。但是，我们不能够通过迭代器来修改set中的key元素。
4、set的接口：
set的接口我们仅需要记下常用的几个增删查改，其它的可以看文档了解一下。
&&1、插入，insert：
insert分为两种情况：1、插入单个元素。2、插入一段迭代器区间。
&&2、查找，find、count
如果find查找到指定对象则返回目标迭代器，否则返回end迭代器。
count则返回查找对象在容器中的个数。
&&3、删除，erase
erase既可以删除一个指定的对象也可以删除一段指定的迭代器区间。
&&4、lower_bound、upper_bound
lower_bound返回第一个大于等于目标对象的迭代器，而upper_bound返回第一个大于目标对象的迭代器。
之所以这么设计是为了配对迭代器区间的左闭右开原则。
int main()
{
set<int> b = {1,2,3,4,5,6,7,8,9};
auto it1 = b.lower_bound(2);
auto it2 = b.upper_bound(6);
set<int> c = { it1,it2 };
for (int x : c)
{
cout << x << " ";
}
return 0;
}5、set的排序方式
下面是set的模板参数：
其中第二个参数Compare是专门用来控制排序方式的，默认的是Less<T>也就是升序。
如果我们需要改变排序方式我们可以使用greater<T>。
或者自己创建一个仿函数进行控制：
template<class T>
struct Greater
{
bool operator()(const T& x1,const T& x2)
{
return x1 > x2;
}
};
int main()
{
set<int, Greater<int>> a = { 1,2,10,32,4,5,3,7,8,9 };
for (int x : a)
{
cout << x << " ";
}
return 0;
} 但运行的时候会出现这样的报错：
这是因为重载函数没有设置为const成员函数，而必须设置为const成员函数的原因是：
- 让容器能在常量上下文中调用比较器；
- 保证比较器不修改自身状态，符合 “纯比较” 的语义；
- 遵循 C++ 标准库的设计惯例，提升代码的健壮性和兼容性
故应更改为：
bool operator()(const T& x1,const T& x2)const二、multiset
mulitset的使用方法与set基本相同，但是multiset支持存储重复的对象。
三、map
1、map的介绍
map的文档：map - C++ Reference (cplusplus.com)
map和set一样底层都是红黑树，但与set不同的是，map存储键值对，即每个元素包含两个部分：一个键（key）和一个值（value）。同样不能出现重复的键（key）、默认升序（排序改变方法和set一样）、不能直接修改建（key），如果需要修改应先删除再插入。
2、pair类型
map底层的红黑树节点中的数据，使用pair存储键值对数据。
pair可以在两个不同类型的对象之间建立关联关系，并且能够通过公共成员first和second分别访问第一、第二个对象。
3、map的构造
和set一样，map支持无参构造、迭代器区间构造、拷贝构造、初始化列表构造。
从上面就可以看出map容器存储的就是pair类型，我们可以直接使用pair类型来初始化map对象。
但我们依旧可以像上面的b对象一样使用初始化列表构造，并且其中的{“ha”,1}之类还使用到pair的隐式类型转化。
4、map的接口
&&1、insert
insert支持单个数据插入、指定位置插入、迭代器区间插入。
在单个数据插入时（情况1），函数返回一个pair类型对象，该pair类型对象的first是插入的pair对象，second则是判断是否成功插入的bool值。
在指定位置插入时返回插入位置的迭代器，或者是返回容器中已经存在的对象的迭代器。
迭代器区间插入无返回值。
&&2、erase
erase删除的是键（key）而与链（val）无关。
在第二种情况下erase返回被删除对象在容器中的个数。
&&3、find和count
find和count都是在容器中查找指定对象，但是find返回的是键（key）迭代器（没找到返回map::end）而count返回键（key）在容器中的个数。
find和count的时间复杂度都是（longN）。
&&4、operator[ ]（重点）
map使用重载的[ ]时，如果[ ]中的对象容器中没有则会将其插入到容器中，链（val）调用其默认构造初始化；如果[ ]中的对象容器中存在则会返回对象的链（val）；除此之外，[ ]还支持修改链（val）。
四、multimap
multimap的使用方式与map基本相同，但由于multimap支持键（key）冗，导致insert/find/erase/count等接口在具体使用的时候会有细微的差别。
也是由于存在冗余的情况，multimap并没有支持operator[ ]。
1、erase
multimap的erase在第二种传入键的情况下会删除所有跟键冗余的对象。
2、find和count
与map不同的是，multimap的find会返回中序遍历中的第一个目标对象的迭代器；count则会返回容器中目标对象的总个数。
码道开发者社区，聚焦华为云码道 CodeArts 代码智能体，沉淀 Agent、Skill、鸿蒙开发实战内容，供开发者查阅资料、交流技术、分享工程实践
更多推荐
12
0- 0
已为社区贡献1条内容
所有评论(0)