黄龙云 加强网站建设,营业推广怎么写,软件开发工具包什么意思,红河网站建设文章目录1. 关联式容器1.1 键值对1.2 树形结构的关联式容器2. set2.1 set的介绍2.2 set的插入2.3 set的删除和查找2.4 lower_bound和upper_bound3. multiset3.1 count4. map4.1 map的介绍4.2 map的插入4.3 map的遍历4.4 map的[ ]5. multimap1. 关联式容器
我们之前学的vector、…
文章目录1. 关联式容器1.1 键值对1.2 树形结构的关联式容器2. set2.1 set的介绍2.2 set的插入2.3 set的删除和查找2.4 lower_bound和upper_bound3. multiset3.1 count4. map4.1 map的介绍4.2 map的插入4.3 map的遍历4.4 map的[ ]5. multimap1. 关联式容器
我们之前学的vector、list、deque、forward_list(C11)等这些容器统称为序列式容器因为其底层为线性序列的数据结构里面存储的是元素本身。
那什么是关联式容器它与序列式容器有什么区别 关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是key, value结构的键值对在数据检索时比序列式容器效率更高。
1.1 键值对
用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量key和valuekey代表键值value表示与key对应的信息。
1.2 树形结构的关联式容器
根据应用场景的不同STL总共实现了两种不同结构的管理式容器树型结构与哈希结构。树型结构的关联式容器主要有四种map、set、multimap、multiset。这四种容器的共同点是使用平衡搜索树(即红黑树)作为其底层结果容器中的元素是一个有序的序列。
2. set
2.1 set的介绍 set的模板参数说明 第一个参数是set中存放元素的类型实际在底层存储key, value的键值对第二个是一个比较器(默认小于)第三个是一个空间适配器(以后再说)。
解释说明 1. set是按照一定次序存储元素的容器 2. 在set中元素的value也标识它(value就是key类型为T)并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)但是可以从容器中插入或删除它们。 3. 在内部set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。 4. set在底层是用二叉搜索树(红黑树)实现的。
当我们想用二叉搜索树key模型时就可以使用set了。
2.2 set的插入 set里面重定义的key_type和value_type代表的是T
使用如下 我们可以看出打印出来的结果是经过排序和去重的。set的插入迭代器不会发生失效问题。
2.3 set的删除和查找 这里删除的第二个函数的返回值意思是你成功删除了多少个。因为这个set里面是去重的而后面有一个不去重的版本。
要删除前我们需要一个函数查找 我们来看一下它的返回值 找到了就返回位置的迭代器没找到就返回迭代器的end()。这个set里面的find函数时间复杂度是O(logN)而在算法里有一个暴力查找的时间复杂度是O(N)。
使用如下
2.4 lower_bound和upper_bound 这个函数是什么意思呢我们来看下面的代码 从结果我们来看返回 val位置迭代器 。3返回3位置 6 返回7位置。 这个函数的应用场景可以删除x的所有值 那么upper_bound是什么情况呢 返回val位置迭代器 。3返回4位置 6返回7位置。
3. multiset 它和set包含的是同一个头文件。不同的区别是它插入的数据可以重复。
3.1 count 这个count函数是统计这个树里有多少个。set也有这个函数但是set是不重复的所以只会出现0或1。而这个multiset是可以重复的那么erase函数的返回值也有作用了。 然后multiset的find函数它找的是中序遍历的第一个结点的迭代器。
4. map
4.1 map的介绍 map的模板参数说明 key: 键值对中key的类型。 T 键值对中value的类型。 Compare: 比较器的类型map中的元素是按照key来比较的缺省情况下按照小于来比较一般情况下(内置类型元素)该参数不需要传递如果无法比较时(自定义类型)需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)。 Alloc通过空间配置器来申请底层空间不需要用户传递除非用户不想使用标准库提供的空间配置器。
解释说明 1. map是关联容器它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。 2. 在map中键值key通常用于排序和唯一标识元素而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同并且在map的内部key与value通过成员类型value_type绑定在一起为其取别名称为pair:typedef pairconst key, T value_type。 3. map支持下标访问符即在[]中放入key就可以找到与key对应的value。 4. map通常被实现为二叉搜索树(更准确的说平衡二叉搜索树(红黑树))。
如果我们想使用KV模型的时候我们可以使用map(防重复)。
4.2 map的插入 map里面重定义的value_type是一个结构pair。我们可以看一下这个pair在STL里面是怎么定义的 使用如下 这是三种构造方式。make_pair是一个函数模板 使用这个函数我们就不需要写参数了。
返回值的意义 这句话的意思是返回一个pair第一个参数first被设置成一个迭代器指向新插入的位置如果key存在那么就指向已经存在位置的迭代器。第二个参数second如果成功插入返回真如果key存在返回假。
4.3 map的遍历 从这里我们可以看出迭代器it不能直接解引用。因为这里我们是用pair这个结构体把key和value包含在一起了。所以这里的*it是pair这个结构体。我么可以这样 如果使用auto我们需要这样写
4.4 map的[ ]
之前我们写过统计一个东西出现的次数那么这里我们也可以使用map了。 然后根据我们学的insert返回值其实我们可以再优化一下。因为如果我们插入一个不存在的时候find会查找一遍。然后进入else时insert又会查找一遍。我们可以这样改 那么方括号[ ]我们可以这样使用 这是为什么我们先来看一下map的[ ] 这里的key_type是stringmapped_type是int。源码如下 这个mapped_type()是value的匿名构造。然后就是调用了insert它的返回值是pairiterator,bool调用了first就是iterator解引用后调用second就是value。如果我们要插入的key在map中我们可以查找并修改value。因为它的返回值是引用。如果我们要插入的key不在map中我们可以插入并修改value。
5. multimap 它和map包含的是同一个头文件。不同的区别是它插入的数据可以重复。 相比mapmultimap最大的区别是它不接受方括号的使用。 可以看出插入的返回值也不是pair了而是新插入位置的迭代器。
