序列式容器:vector,list,deque,forward_lsit都是序列式容器,因为它们的底层都是线性序列的数据结构,存放的是元素本身。
1. 之前所学的vector,list,deque等容器都是序列式容器,因为他们的底层数据结构都是线性的,并且数据结构中存储的都是元素数据本身,也就是单一的变量。 而下面所学的set、map、multimap、multiset等容器都是关联式容器,他们内部存储的不再是单一的元素数据,存储的而是<key,value>的键值对,由于每个键值对之间都有关联,所以其结构天生就具有优势,在数据检索时效率要比序列式容器高的多。
容器操作函数find(begin, end, val) 返回值是迭代器,没找到返回end。 容器类型和元素类型都相同,可以用赋值vec1=vec2。容器类型不同或元素类型不同,但是兼容可以用assign函数来赋值。 vector容器中的元素以连续的方式存放【动态数组】。有预先分配策略,需要重新分配时加倍当前容量。capacity函数获取目前能够存储的元素总数,reserve函数设置capacity。 string中的字符也是连续存储的,也有迭代器string::iterator。string类将string
我们之前在学习 set 和 map 基本使用时就介绍了 set 和 map 底层都是红黑树,但这里有一个问题 – set 是K模型的容器,而 map 是KV模型的容器,那它们底层为什么能同样都使用红黑树呢?我们可以通过阅读源码来解答这个问题。(本文中使用的源码为 SGI 的 stl30 版本)
上一篇文章我们实现了红黑树,但是我们实现的那个类并不是特别完善,所以,为了后面map和set的模拟实现,我们先对之前写的那个红黑树的类做一些补充和完善。
set / map与unordered_set / unordered_map 使用功能基本相同,但是两者的底层结构不同
1. 在源码里面,对于map和set的实现,底层是用同一棵红黑树封装出来的,并不是用了两棵红黑树,一个红黑树结点存key,一个红黑树结点存<key,value>的键值对,这样的方式太不符合大佬的水准了,实际上在红黑树底层中用了一个模板参数Value来代表红黑树结点存储对象的类型,这个类型可能是pair键值对,也有可能是key类型。 所以在红黑树这一层中是不知道他自己的结点要存储什么类型的对象的,故而需要模板参数来接收存储对象的类型。
红黑树的基本情况我们已经在上一篇文章中学习过了,本文主要研究的是红黑树的实际应用:封装实现 set 和 map,看看如何通过一棵红黑树满足两个不同的数据结构;在正式封装之前,先要对之前的红黑树进行完善,增加必要功能
在C++初阶的时候,我们已经接触了 STL 中的部分容器并进行了模拟实现,比如 vector、list、stack、queue 等,这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面存储的是元素本身;
std::pair 是C++标准库中提供的一个简单的键值对实现。它包含在 <utility> 头文件中。一个 std::pair 有两个公有成员:first 和 second,分别表示键和值==(first<= =>key ; second<= =>value)==
STL简称标准模版库,被容纳在C++标准程序库,包含了许多基本数据结构和基本算法,使程序员写起来得心应手。
容器和算法通过迭代器可以进行无缝地连接。在STL中几乎所有的代码都采用了模板类和模板函数的方式,这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
与之前的双参数<class K, class V>相比,改良之后的T作为了全部的数据域,即T也可以代表pair类型。
之前介绍过标准库中的顺序容器,顺序容器是元素在内存中按照一定顺序进行排列的,都是按线性结构进行排列。除了顺序容器外,c++中还有关联容器。与顺序容器不同的是,关联容器中元素是按照关键字来保存和访问的。与之相对的顺序容器是按它们在容器中的位置来顺序的保存和访问的。
在 C++ 语言中的 标准模板库 ( STL , Standard Template Library ) 中的 std::set 集合容器 类提供了一个 lower_bound 成员函数 ;
由于博主的能力有限,所以为了方便大家对于map和set的学习,我放一个官方的map和set的链接供大家参考: https://cplusplus.com/
C++map和set的介绍及使用 零、前言 一、关联式容器 二、键值对 三、C++中的set 1、set的介绍 2、set的使用 四、C++中的multiset 五、C++中的map 1、map的介绍 2、map的使用 六、C++中的multimap 零、前言 本章主要讲解C++中的一个关联式容器map和set的介绍及其使用 一、关联式容器 容器分类: 序列式容器:初阶阶段中学习过STL中的部分容器,如:vector、list、deque等,这些容器统称为序列式容器,因为其底层为线性序列的数据结
a.push_back(x)把元素x插入到vector a的尾部。 a.pop_back()删除vector a的最后一个元素。
用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量key和value,key代表键值,value表示与key对应的信息。
set和map底层数据结构都是红黑树,红黑树的data域段为==pair<key, value>==类型。
这一章介绍了标准库中的关联容器们,主要是11.3的对有序关联容器操作的介绍。这章比较短,也只是比较工具性的东西,快速浏览即可。下一章就是C++的重要运用:动态内存管理。
我们来看一下这几个模板参数 第一个value就决定了哈希表里面每个data里面存的数据类型,第二个参数key就是用来获取单独的键值key,因为unordered_map进行查找这些操作的时候是用key进行散列的,需要比较的话也是用key,但他里面存的是pair。 第三个这个HashFcn就是接收一个仿函数,用来将比如字符串这些类型转换为整型的。 第四个的作用就和红黑树封装那里的KeyOfT一样,用来提取key的。 那我们先看这么多。
上次的文章遗留了一个问题没有回答,有些小伙伴有些疑问。就是为什么说set是关联式的容器,这个关联体现在哪里。
T: set中存放元素的类型,实际在底层存储<value, value>的键值对。 **Compare:**set中元素默认按照小于来比较 **Alloc:**set中元素空间的管理方式,使用STL提供的空间配置器管理
在 C++98 中,STL 提供了底层为红黑树结构的一系列关联式容器,在查询时效率可达到 O(logN),即最差情况下只需要比较红黑树的高度次;但是当树中的节点非常多时,其查询效率也不够极致。
set 和 map 是 STL 中的容器之一,不同于普通容器,它俩的查找速度极快,常用来存储各种经常被检索的数据,因为这俩容器的底层是平衡二叉搜索树中的红黑树。除此之外,还可以借助其特殊的性质,解决部分难题
比如:vector、list、deque、forward_list(C++11)等,这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面存储的是元素本身。
关于哈希表的两种实现方法:闭散列、开散列 已经在上一篇文章中学习过了,闭散列 存在 踩踏 问题,十分影响效率,因此在实践中往往会选择更加优秀的 开散列,哈希表(开散列)又叫做 哈希桶,作为被选中的结构,我们需要对其进行改造,完善哈希桶,使其最终能封装出 unordered_set 与 unordered_map
之前我们学的list,vector等等是序列式容器,这里的set和map和之后的哈希表都是关联式容器,比如说搜索二叉树我们想插入一个值,不能随意的插入,因为每个数都是有关联的,需要找到准确位置才能进行插入。
集合具有共同特征的事物,可以是由两个迭代器定义的范围内的一系列对象,也可以是一种有特殊特征的容器类型。
map与set在STL中实现是一样的 对于value_type,map的第二个模板参数是pair,而set的第二个模板参数是key 这样写是为了map和set使用同一颗红黑树去复用map和set
顺序容器有以下三种:可变长动态数组 vector、双端队列 deque、双向链表 list。
set 参数只有 key,但是map除了key还有value。我们还是需要KV模型的红黑树的:
树型结构的关联式容器主要有四种:map、set、multimap、multiset四种容器的共同点是:使用平衡搜索树(即红黑树)作为其底层结果,容器中的元素是一个有序的序列。
二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。因此,咱们中国的邻居俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。
注:在迭代关联容器时,我们可以确保按键的顺序访问,而与元素在容器中的存放位置完全无关。
对于有序容器,关键字类型必须定义元素比较的方法。默认情况下,标准库使用关键字类型的<运算符来比较两个关键字。
从c++11标准以来,c++中std定义的几种容器的效率非常高,优化的非常好,完全没有必要自己去定义类似的数据结构。了解使用它们,可以满足90%的日常编程需要。该篇文章基于c++11标准,从用户角度来介绍常用的顺序容器与并联容器(如果想从内部了解它们是怎么实现的,推荐看看《std源码剖析》这本书)。它们包括:
Map/Multimap 映射容器属于关联容器,它的每个键对应着每个值,容器的数据结构同样采用红黑树进行管理,插入的键不允许重复,但值是可以重复的,如果使用Multimap声明映射容器,则同样可以插入相同的键值。
这些容器和数组非常类似,都是在逻辑上连续的(但内存不一定是连续的),与数组不同的是,容器可以非常方便的动态管理,而不是固定元素大小
map和set的底层都是由红黑树实现的。 所以这里将上次实现的红黑树插入拿来用。 首先想一想,搜索二叉树不能修改值,因为会破坏整棵树的平衡。 set与map的部分源码:
⭐写在前面的话:本系列文章旨在短时间内回顾C/C++语法中的重点与易错点,巩固算法竞赛与写题过程中常用的语法知识,精准地解决学过但有遗忘的情况,为算法刷题打下坚实的基础。
STL中基本的关联式容器有map和set,它们都是以红黑树作为其底层的结构,具有非常高的查找、删除效率,内容会按照键值自动排序。 使用map的注意事项: 1、关联式容器的键值是不允许修改的,所以永远不要试图去修改关联式容器的键值 2、插入数据时,如果使用的是insert,并且新插入的键值在原映射中已经存在,那么只是单纯的插入不成功,不会对原映射造成影响,如果使用[]进行插入操作,并且新插入的键值在原映射中已经存在,那么会将原映射中的实值改成要插入的实值。 3、insert插入操作会用到pair结构,pair
长久以来,软件界一直希望建立一种可重复利用的东西,以及一种得以制造出”可重复运用的东西”的方法,从函数(functions),类别(classes),函数库(function libraries),类别库(class libraries)、各种组件,从模块化设计,到面向对象(object oriented ),为的就是复用性的提升。
unordered_map、unordered_set与map、set的区别是unoedered系列无序,除此之外功能上没有区别。但二者之间底层不同,前者底层为哈希,后者为红黑树。之前所学到的红黑树封装map和set时,为了map和set能够共用一套红黑树结构,我们将红黑树的参数类型以及模板数量类型进行的改良,增加一个能够读取参数相应大小的仿函数KeyOfT,对于这次的封装,同样采用这种方式。上一篇中实现了两种方法:开放地址法、哈希桶,由于源码采用哈希桶并且哈希桶的方式能够更好的解决冲突问题,因此再次以哈希桶为基准进行改良,进而封装unordered_set和unordered_map。
set的介绍 C++中的set是一个STL容器,它是一个自动排序的集合(即将数据存入set,我们通过迭代器顺序访问出来时,数据是有序的),内部使用红黑树(后面会讲解)来实现。它的特点是不允许重复元素,而且插入元素时自动进行排序。
我们在前面已经接触过 STL 中的部分容器,比如:vector、list、deque、等,这些容器统称为序列式容器(一级容器),因为其底层为线性序列的数据结构,里面存储的是元素本身。
vector变长数组,倍增的思想//系统为某一程序分配空间时,所需的时间与空间大小无关,与申请次数有关
领取专属 10元无门槛券
手把手带您无忧上云