本期我们来学习map和set
目录
关联式容器
键值对
pair
树形结构的关联式容器
set
multiset
map
multimap
关联式容器
我们已经接触过
STL
中的部分容器,比如:
vector
、
list
、
deque
、forward_list(C++11)等,这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面存储的是元素本身。那什么是关联式容器?它与序列式容器有什么区别?
关联式容器
也是用来存储数据的,与序列式容器不同的是,其
里面存储的是
<key, value>
结构的
键值对,在数据检索时比序列式容器效率更高
键值对
用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量
key
和
value
,
key
代
表键值,
value
表示与
key
对应的信息
。比如:现在要建立一个英汉互译的字典,那该字典中必然有英文单词与其对应的中文含义,而且,英文单词与其中文含义是一一对应的关系,即通过该应该单词,在词典中就可以找到与其对应的中文含义。
SGI-STL中关于键值对的定义:
pair
template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()), second(T2())
{}
pair(const T1& a, const T2& b): first(a), second(b)
{}
};
树形结构的关联式容器
根据应用场景的不桶,
STL
总共实现了两种不同结构的管理式容器:树型结构与哈希结构。
树型结
构的关联式容器主要有四种:
map
、
set
、
multimap
、
multiset
。这四种容器的共同点是:使用平衡搜索树(
即红黑树
)
作为其底层结果,容器中的元素是一个有序的序列。下面一依次介绍每一个容器。
set
![](https://img-blog.csdnimg.cn/9eea11185a504708b985861b8b8376e9.png)
1. set
是按照一定次序存储元素的容器
2.
在
set
中,元素的
value
也标识它
(value
就是
key
,类型为
T)
,并且每个
value
必须是唯一的。
set
中的元素不能在容器中修改
(
元素总是
const)
,但是可以从容器中插入或删除它们。
3.
在内部,
set
中的元素总是按照其内部比较对象
(
类型比较
)
所指示的特定严格弱排序准则进行排序。
4. set
容器通过
key
访问单个元素的速度通常比
unordered_set
容器慢,但它们允许根据顺序对
子集进行直接迭代。
5. set
在底层是用二叉搜索树
(
红黑树
)
实现的。
注意:
1.
与
map/multimap
不同,
map/multimap
中存储的是真正的键值对
<key, value>
,
set
中只放
value
,但在底层实际存放的是由
<value, value>
构成的键值对。
2. set
中插入元素时,只需要插入
value
即可,不需要构造键值对。
3. set
中的元素不可以重复
(
因此可以使用
set
进行去重
)
。
4.
使用
set
的迭代器遍历
set
中的元素,可以得到有序序列
5. set
中的元素默认按照小于来比较
6. set
中查找某个元素,时间复杂度为:
$log_2 n$
7. set
中的元素不允许修改
(
为什么
?)
8. set
中的底层使用二叉搜索树
(
红黑树
)
来实现
我们发现,set的模板参数比我们之前学的多了一个compare,这是仿函数,支持key比较大小的
![](https://img-blog.csdnimg.cn/a4ddfd8267944a2c85bc0be3a4a11f12.png)
我们来看它的构造,有拷贝构造,默认构造以及迭代器区间初始化
![](https://img-blog.csdnimg.cn/1acfdc4197cd46d68842e17d2b0a354a.png)
set的迭代器是双向迭代器
![](https://img-blog.csdnimg.cn/6cbe523783fc454982106bdfd9a1877f.png)
这里的key_type和value_type都是T,这里我们后面会讲
下面我们简单使用一下
![](https://img-blog.csdnimg.cn/0047e4c5f1e3473c812ddcd8ead31dce.png)
使用没什么问题,我们在这里还发现一个问题,它的输出结果是有序的,因为它走的是中序遍历
![](https://img-blog.csdnimg.cn/455ec897f92f4fa1b51b73c1412c82d7.png)
而且还会去重,去重的原理是如果一个值已经有了,那就不插入
![](https://img-blog.csdnimg.cn/329aade2f84941fb8e4d8255309dc8f0.png)
也可以使用范围for遍历
![](https://img-blog.csdnimg.cn/fbbc6f97d8d8427c8ba1f9b7aff14df5.png)
erase支持迭代器位置,值已经迭代器区间
![](https://img-blog.csdnimg.cn/bea386fa32e34da2b930495d0ba3e23f.png)
我们根据情况选择即可
![](https://img-blog.csdnimg.cn/6e5e6c7671eb46d6ac4b5d9a013fc983.png)
如果直接删除值,值不存在没什么问题,但如果用find先查找的话,这里就会报错,因为pos不存在
![](https://img-blog.csdnimg.cn/a2c489cd94b746919f512d181cdb6ac0.png)
我们再看看这两个find有什么区别,一个是set自己的find,另一个是算法库里的
set自己的find最多查找高度次,时间复杂度是O(longN),而算法库的find是暴力查找,是O(N),所以我们最好不要用库里面的
![](https://img-blog.csdnimg.cn/919db054e04f4074ac070150ad93500a.png)
还有一个count,这个set这里基本用不到
![](https://img-blog.csdnimg.cn/f6905d64cf954f1ea090d39553044ad5.png)
和find差不多,我们传一个元素,如果在返回1,不在就返回0
![](https://img-blog.csdnimg.cn/8428baf69964422394dcdf0d71e3da92.png)
find是返回迭代器,而count是返回1或者0
![](https://img-blog.csdnimg.cn/e1b04066c08145ec8a7acf146435565e.png)
还有这三个函数,是寻找边界的特殊情况用的,我们来看看例子就明白了
比如我们查找30和60,itlow得到的就是30,而itup是比60大的,因为迭代器区间是左闭右开,这样就可以和迭代器适配,可以保证30到60之间删除(包括60)
![](https://img-blog.csdnimg.cn/aef0699786fa4fc288fdf41ac2a615a4.png)
如果我们找35,得到的是40,lower_bound查找的是>=的值,upper_bound是>
![](https://img-blog.csdnimg.cn/a8d8a885478940a695b197bdb402f4b4.png)
equal_range也是一样,会查找一个左闭右开的区间
multiset
![](https://img-blog.csdnimg.cn/0c61a375b2f64b2d944c0e3dbd0601c2.png)
我们再看这个容器,它用起来和set是一样的
![](https://img-blog.csdnimg.cn/3e219b58d2424dafae152958c3648f8f.png)
它和set的区别就是它允许有重复
![](https://img-blog.csdnimg.cn/b6b6f3f35a854831812850083fe6beff.png)
如果我们要删除所有的5,我们上面的equal_range就是这样使用的 ,count也是在这里使用,这里可以算出有多少个5,我们可以认为这两个接口就是专门为multiset设计的,set有这两个接口只是为了保持接口一致罢了
![](https://img-blog.csdnimg.cn/78dfe553ef7f446098019f28d777ff53.png)
当有重复值时,find返回的是中序的第一个
equal_range返回的是>=,如果给的值不存在,返回的就是不存在的区间
map
![](https://img-blog.csdnimg.cn/d9619123f23145bda65f98fe5848c1aa.png)
1. map
是关联容器,它按照特定的次序
(
按照
key
来比较
)
存储由键值
key
和值
value
组合而成的元素。
2.
在
map
中,键值
key
通常用于排序和惟一地标识元素,而值
value
中存储与此键值
key
关联的
内容。键值
key
和值
value
的类型可能不同,并且在
map
的内部,
key
与
value
通过成员类型
value_type
绑定在一起,为其取别名称为
pair:
typedef pair<const key, T> value_type;
3.
在内部,
map
中的元素总是按照键值
key
进行比较排序的。
4. map
中通过键值访问单个元素的速度通常比
unordered_map
容器慢,但
map
允许根据顺序
对元素进行直接迭代
(
即对
map
中的元素进行迭代时,可以得到一个有序的序列
)
。
5. map
支持下标访问符,即在
[]
中放入
key
,就可以找到与
key
对应的
value
。
6. map
通常被实现为二叉搜索树
(
更准确的说:平衡二叉搜索树
(
红黑树
))
。
![](https://img-blog.csdnimg.cn/7cd1a106041e48eb887bd85edec9fcaa.png)
map这里也有三个type,下面我们简单使用一下
![](https://img-blog.csdnimg.cn/059a2800169641148846349502982f6d.png)
我们先看insert
![](https://img-blog.csdnimg.cn/2c600feef0064379a31005e1ca8b4c11.png)
map是kv模型,所以使用起来非常麻烦,那么可不可以像我们以前那样直接传呢?答案是可以的
![](https://img-blog.csdnimg.cn/4a7aa11cae824df8b927d17ef28d0955.png)
原因是有make_pair
![](https://img-blog.csdnimg.cn/048c03613ea9418f87ba1270073c6505.png)
就像这样,这里就是map的插入
![](https://img-blog.csdnimg.cn/66ffeb3eba2f483c9a67f1809b937c5e.png)
当然还可以更简洁一点,直接用{ }括起来,这是因为C++11支持多参数的构造函数隐式类型转换,也就是说这种写法在C++98是不能用的
![](https://img-blog.csdnimg.cn/4e89ffb2c8dc4022ad8e7c3ce30ff3ee.png)
接着我们来遍历,但是按照我们之前写的遍历,这里就出错了,原因是pair不支持流插入和流提取
![](https://img-blog.csdnimg.cn/1d8601d1302c495898dd30ef40dbc3d3.png)
那为什么这里不像我们写的那样直接用key和value,而要使用一个pair?
原因是operator*返回的话不方便,如果直接使用,C++是不支持返回两个值的,所以设计了一个pair结构
![](https://img-blog.csdnimg.cn/c8658e189ae54862ac99e967193ab92e.png)
所以得这样写
如果觉得上面的写法麻烦还可以用->
![](https://img-blog.csdnimg.cn/f140da374360427c9420215c6a7699bb.png)
大概就是这样
![](https://img-blog.csdnimg.cn/7af4955deeaa4b7caf7f2c17dffaaf64.png)
我们之前也说过,如果不是编译器优化,这里是要有两个箭头的 ,第一个是运算符重载,第二个是访问
![](https://img-blog.csdnimg.cn/30ad39dc79fb4df18d424e9d7339415c.png)
也可以用范围for
![](https://img-blog.csdnimg.cn/cb0e6dd05f8a420ca1566cd9b1e92ba2.png)
first是不允许修改的,second可以修改
![](https://img-blog.csdnimg.cn/2eb4d84373fc4c56b315ffe4ec32f3aa.png)
如果key相同,value不同,是不能插入了,key相同时不插入,不覆盖 ,也就是插入过程中只比较key,value无所谓
![](https://img-blog.csdnimg.cn/63c4b1e00e2f41598e0004b84eeaa12b.png)
erase也是一样,只看key在不在
![](https://img-blog.csdnimg.cn/8af2f044a19749f9b04f61c4f096423f.png)
下面我们来看看[ ]
![](https://img-blog.csdnimg.cn/c4a9113fc39949d495a547d1ac3f48cb.png)
我们来看这个统计次数,我们以后就可以直接用map
![](https://img-blog.csdnimg.cn/c8fdedb391bf4cb09082fa21efc56992.png)
而且代码可以优化,我们可以使用 [ ]
map的[ ] 不是常规的,而是给key,返回对应的value
后面的++我们懂,但是水果第一次出现是怎么回事呢?
![](https://img-blog.csdnimg.cn/3af3f2cda84d42029fb1f7a9183f0b53.png)
它返回了这么个东西,借助了insert的返回值
![](https://img-blog.csdnimg.cn/8ca65d5f3fe145f1993c687b2eade6f5.png)
我们可以看到insert的返回值是一个pair
![](https://img-blog.csdnimg.cn/a44e54123d5744f89f967007ee4bcbb8.png)
大致翻译一下:这里返回一个pair,这个pair的first被设置为迭代器,要么指向新插入的元素,要么指向和key相等的元素,second被设计为true,如果key在里面返回false
也就是说,key已经在树里面,返回pair<树里面key所在节点的iterator,false>,如果key不在树里面,返回pair<新插入key所在节点的iterator,true>
![](https://img-blog.csdnimg.cn/b62978483be74cc2942f3b38c2834abd.png)
如果我们自己设计就是这样,ret里除了key,另一个是匿名对象,根据value的变化而变化,如果key不在树里面, 那就插入成功,如果value是int那就是0,如果是string就是空的string,如果插入失败,也没有影响,因为insert只看key,而return时,first是迭代器,有了迭代器我们就可以取到second
![](https://img-blog.csdnimg.cn/5c9a137283dd404fbf974eda201078de.png)
我们结合起来理解一下,水果第一次出现时,insert,key是水果,value是int,int的匿名对象缺省值是0,然后返回这个次数,++一下就变成了1,如果有的话,那就插入失败,再返回次数,++次数就可以计数了
![](https://img-blog.csdnimg.cn/6af9552635f44bcc82d986daf3875d4c.png)
我们来一步一步看这个
我们经过dict["sort"]时是不影响的
![](https://img-blog.csdnimg.cn/be73649331f841b89f6a2dcf2b3e6b09.png)
这里是可以读的,也就是说,这里是查找+读
经过dict["map"]时,监视窗口多了一个map,value是空的,和我们前面看到的一样,[ ] 的本质是insert
![](https://img-blog.csdnimg.cn/4a7978e6019c45149f358ddfe6c2cc7b.png)
接着我们修改了value(空的value)
这次我们修改了insert的value
![](https://img-blog.csdnimg.cn/f0a485a875af4034ab174dab0318fcba.png)
最后一个就是插入+修改了(修改空的value)
[ ] 的功能非常多,我们用的时候也就要小心一点
multimap
![](https://img-blog.csdnimg.cn/b64c7d63621e42c4b2cd5fa7e529b3c6.png)
这个也没啥好说的,对于map就和multiset对于set似的,就是可以有重复的key
不同的地方在于multimap没有提供operator[ ],所以insert也不一样了,不提供pair了,插入永远成功,其他功能一样
以上即为本期全部内容,希望大家可以有所收获
如有错误,还请指正