服饰 视频 网站建设,网站反链怎么做,云主机上传wordpress,如何做电影网站才不侵权文章目录 1. 关联式容器2. 树形结构的关联式容器3. set3.1 认识set3.1 set的使用 4. multiset5. map5.1 认识map5.2 pair5.3 map的使用对map中[]的理解 6. multimap 1. 关联式容器
在初阶阶段#xff0c;我们已经接触过STL中的部分容器 比如#xff1a;vector、list、deque、… 文章目录 1. 关联式容器2. 树形结构的关联式容器3. set3.1 认识set3.1 set的使用 4. multiset5. map5.1 认识map5.2 pair5.3 map的使用对map中[]的理解 6. multimap 1. 关联式容器
在初阶阶段我们已经接触过STL中的部分容器 比如vector、list、deque、forward_list(C11)等这些容器统称为序列式容器因为其底层为线性序列的数据结构里面存储的是元素本身。 而今天我们要学习的几个容器称为关联式容器那什么是关联式容器它与序列式容器有什么区别 关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是key, value结构的键值对在数据检索时比序列式容器效率更高。 2. 树形结构的关联式容器
根据应用场景的不同STL总共实现了两种不同结构的关联式容器树型结构与哈希结构。
树型结构的关联式容器主要有四种 map、set、multimap、multiset。 这四种容器的共同点是使用平衡二叉搜索树(即红黑树)作为其底层结构容器中的元素是一个有序的序列。 关于平衡二叉树我们后面也会讲到其实我们在前面几篇文章讲解搜索二叉树的时候也提到过普通的搜索二叉树如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。 那平衡二叉树顾名思义就是在普通搜索二叉树的基础上让它变的平衡(需要对树中的结点进行调整)。 这个我们后面讲到再细说。 下面一依次介绍每一个容器。
3. set
3.1 认识set
首先我们来看一下set 还是一个类模板有三个模板参数但其实平时我们使用的时候一般只需要管第一个模板参数就行了。 因为后两个都是缺省值的当然如果你想改变它底层搜索树的排序方式你可以自己传第二个比较方式的仿函数默认是升序。 关于set的仔细介绍大家可以去看文档 不过是英文的大家可以借助翻译工具查看
3.1 set的使用 由于我们之前已经学了好几个STL里面的容器所以这里对于这些容器的使用其实对我们应该是比较轻松的。所以我这里就不会像之前那样特别仔细去一个个介绍它的接口了很多东西相信到现在这个阶段大家看着文档都能搞懂。 它提供的接口大家可以先看一下当然其中一些都不常用。 那我们上面说到 这几个关联式容器它们的底层结构其实就是我们之前学的二叉搜索树只不过是平衡搜索树罢了。 那set其实就对应我们前面学的搜索二叉树的应用里面的K模型下面要学的map就对应KV模型。 那我们接下来就来熟悉一下它的使用
看一下它的构造函数 那我们来构造一个空的set然后插入一些值 首先使用set要包含对于的头文件#include set 我们使用insert插入几个元素这里我们看他的接口其实就没有push啥的了一般线性的序列式容器才会有push。 那然后我想打印出来看看那我们就可以使用迭代器去遍历它 但是我们看到这里打印出来是1234。 但是我们插入了好几个值啊并且是无序的那这里怎么回事呢 上面说了它的底层是平衡二叉树那我们学过二叉搜索树其实就明白怎么回事了 搜索二叉树一般是不能有重复值的所以如果多次插入相同的值后面的就会插入失败或者可以理解成它会自动进行去重另外我们知道二叉搜索树也叫做二叉排序树中序遍历就可以得到一个升序序列所以这里默认遍历打印出来就是有序了。 所以可以认为set可以实现排序去重 那支持迭代器的话我们就可以用范围for。 那大家思考一下我们可以修改它里面的值吗 当然是不行的因为我们说了它的底层是搜索树那搜索树如果我们可以任意修改里面的值的话修改之后还能保证它还是一棵搜索树吗 就不一定了因为搜索树是需要满足对于的大小规则的。 所以不能修改。 如果我们想判断一个元素在不在set对象里面 可以用find接口 但其实还可以用另一个接口——count count是统计元素的个数但是我们的set里面不允许重复值所以结果只有1和0存在就是1不存在就是0 那剩下的其它的接口我们这里就不介绍了有了前面的基础相信大家一看就会还有的就是不怎么用的或者现阶段我们不是很能看懂的。
4. multiset
那在set这个头文件里面呢出来set还有一个multiset multiset叫做多重集合multi有多种的意思嘛。 还是这些接口。 那它跟set有什么区别呢 它跟set最大的区别就是允许里面存的key值冗余。 我们可以来看一下 可以认为它有排序但没进行去重 那允许键值冗余的话它的插入怎么做呢 那就接着插就行了即使插入的是已经存在的值那搜索树的话我们说大的值要插入到右子树小的插入到左子树那现在相等的话其实插入到哪边都可以可以左边也可以右边反正平衡二叉树嘛插入之后会对结点进行调整使得两边平衡我们后面会讲平衡二叉树。 然后想给大家说一下find 现在允许键值冗余了那就有一个问题 如果我们find某个值的话跟他有多个相同的值那find的时候查找的是哪一个 规定呢它find的是中序遍历遇到的第一个。 它遍历的时候底层走的是中序遍历嘛所以打印出来才是有序的。 我们可以验证一下的 现在有4个1我们find(1)然后从返回的迭代器位置开始如果能把4个1都打印出来就证明是中序的第一个1 当然我们可以用count统计每个键值的个数 不过在实际应用中用multiset一般比较少。
5. map
5.1 认识map
map呢其实就对应搜索二叉树的KV模型它里面存的是key, value结构的键值对。即用来表示具有一 一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代表键值value表示与key对应的信息。 map的接口呢也跟set几乎差不多有需要注意的我们后面会说。
5.2 pair
那在学习map的使用之前我们来学一个STL里面的类/结构体模板——pair
我们来看一下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){}
};pair的应用 pair是将2个数据组合成一个数据当需要这样的需求时就可以使用pair。 1STL中的map就是将key和value放在一起来保存一般first对于keysecond对于value。 2另一个应用是当一个函数需要返回2个数据的时候可以选择pair 5.3 map的使用
那我们看到map的insert 它的第一个版本其实就是接收一个pair类型的对象。 key是const修饰的不能修改即键必须是唯一的value可以。 那我们来写写代码吧可以用map写一个我们之前实现的那个英汉互译的词典 map包含在头文件map中 当然插入还可以用这个 那这个make_pair是啥呢 他其实是库里面提供的一个函数模板 它可以帮助我们创建一个pair的对象用它的好处是我们不需要自己去指定类型因为模板可以自动推导类型。 然后我们来遍历打印一下 当然我们也可以这样写 那大家看这样可以吗 最后一个可以插入成功吗 不行因为键必须是唯一的不能重复值可以重复。 一个键只能对应一个值一个值可以对应多个键 也可以直接通过find键去查找值 那我们也用map再写一下统计次数的程序 跟之前的思路一样我就直接上代码了 对map中[]的理解
然后呢我们发现map呢还提供了这样一个接口 它的作用是啥呢 首先它接收的参数是键key如果输入的键与容器中元素的键匹配就返回该键对应的值的引用。 所以我们刚才的统计次数还可以这样写 for循环内一行代码就搞定了 那我们接下来就来研究一下这句代码 其实文档上面也解释了调用这个重载的[]就等效于执行这句代码 *this-insertmake_pairkmapped_type.first.second 所以这个函数大概是这样一个样子 我们看到这里面其实去调了一下insert那我们来仔细研究一下insert的返回值 我再来解释一下 首先要知道插入的话呢还是有成功和失败两种情况因为键值不允许冗余它返回的是一个pair第一个模板参数为迭代器第二个为bool。 当插入成功的时候pair的first为指向新插入元素的迭代器second为true当插入失败的时候其实就是插入的键已经存在了那它的first为容器中已存在的那个相同的等效键元素的迭代器second为false。 所以后面这个bool其实是标识插入成功还是失败。 那我们再来看这个函数 我们来拆解一下它要不然不好看 然后我们再来看里面这个insert 我们看到这里面insert也是使用make_pair这个函数创建一个pair对象第一个参数就是我们[]里面放的那个键key第二个参数传的是啥呢 我们看到它是调了值value的类型的默认构造之前我们说过有了模板之后内置类型就也需要有构造函数了那我们的value是int默认构造的值是0所以我们第一次插入刚好它的次数就是0了。然后返回这个次数对应的value的引用外面对它就正好是1。 然后后续插入相同键的话就插入失败不会将次数变成0但是依然返回次数对应pair中的second的引用我们从1继续往上就行了 当然它这上面给的有些类型是进行了typedef的我们不太好看不过它提供了一个表大家可以查阅 所以我们可以将它简化一下方便看 所以我们也可以这样玩 插入查找、修改啥的操作这样写 【总结】 1. map中的的元素是键值对 2. map中的key是唯一的并且不能修改 3. 默认按照小于的方式对key进行比较 4. map中的元素如果用迭代器去遍历可以得到一个有序的序列 5. map的底层为平衡搜索树(红黑树)查找效率比较高 O ( l o g 2 N ) O(log_2 N) O(log2N) 6. 支持[]操作符operator[]中实际进行插入查找 6. multimap
那和set一样 除了map还有multimap 我们看一下 同样的跟map相比multimap允许键key冗余 所以它的接口里面就没有[]了 简单演示一下 当然key和value都相同也是可以的。 然后其它的就不多说了有需要大家可以自己查阅文档。
