【C++学习篇】map和set （set篇）

1.map和set的使用

1.1序列式容器和关联式容器

前⾯我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间⼀般没有紧密的关联关系，⽐如交换⼀下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。

关联式容器也是⽤来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是⾮线性结构，两个位置有紧密的关联关系，交换⼀下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。

本期讲解的map和set底层是红⿊树，红⿊树是⼀颗平衡⼆叉搜索树。set是key搜索场景的结构，map是key/value搜索场景的结构。

2. set系列的使⽤

2.1 set分类

set分为set和multiset

两者的差别set不支持key冗余插入，而multiset支持

set分类说明

https://legacy.cplusplus.com/reference/set/

2.2set类的介绍

1. set的声明如下，在官方文档中T就是set底层key的类型。（我个人认为，官方这种写法不太好，容易使初学者混淆）

2. set默认要求T⽀持⼩于⽐较，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现仿函数传给第⼆个模版参数。 3. set底层存储数据的内存是从空间配置器申请的，如果需要可以⾃⼰实现内存池，传给第三个参数。⼀般情况下，我们都不需要传后两个模版参数。 3. set底层是⽤红⿊树实现，增删查效率是 O(logN ) ，迭代器遍历是⾛的搜索树的中序（左子树 根 右子树），所以是有序的。

2.3 set的构造和迭代器

set的构造我们关注以下⼏个接⼝即可。 set的⽀持正向和反向迭代遍历，遍历默认按升序顺序，因为底层是⼆叉搜索树，迭代器遍历⾛的中序；⽀持迭代器就意味着⽀持范围for，set的iterator和const_iterator都不⽀持迭代器修改数据，修改关键字数据，破坏了底层搜索树的结构。

构造（从权威网站截取的）

迭代器

2.4set的增删查

插入insert

删除erase

查找

lower_bound 和 upper_bound

2.5 insert和迭代器遍历使⽤样例：

2.6 find和erase使⽤样例：

2.7multiset和set的差异

multiset和set的使⽤基本完全类似，主要区别点在于multiset⽀持值冗余，那insert/find/count/erase都围绕着⽀持值冗余有所差异，具体参看下⾯的样例代码理解。

本期学习就结束了，谢谢大家支持！！！