STL整理


1. 主要组件

  • 容器(Containers):各种数据结构,如Vector,List,Deque,Set,Map,用来存放数据,STL容器是一种Class Template。

  • 算法(Algorithms):各种常用算法如Sort,Search,Copy,Erase,从实现的角度来看,STL算法是一种Function Templates。

  • 迭代器(Iterators):扮演容器与算法之间的胶合剂,是所谓的“泛型指针”,共有五种类型,以及其它衍生变化,从实现的角度来看,迭代器是一种将:Operators*,Operator->,Operator++,Operator--等相关操作予以重载的Class Template。所有STL容器都附带有自己专属的迭代器——是的,只有容器设计者才知道如何遍历自己的元素,原生指针(Native pointer)也是一种迭代器。

  • 仿函数(Functors):行为类似函数,可作为算法的某种策略(Policy),从实现的角度来看,仿函数是一种重载了Operator()的Class 或 Class Template。一般函数指针可视为狭义的仿函数。

  • 适配器(配接器)(Adapters):一种用来修饰容器(Containers)或仿函数(Functors)或迭代器(Iterators)接口的东西,例如:STL提供的Queue和Stack,虽然看似容器,其实只能算是一种容器配接器,因为 它们的底部完全借助Deque,所有操作有底层的Deque供应。改变Functor接口者,称为Function Adapter;改变Container接口者,称为Container Adapter;改变Iterator接口者,称为Iterator Adapter。

  • 分配器(Allocators):负责空间配置与管理,从实现的角度来看,配置器是一个实现了动态空间配置、空间管理、空间释放的Class Template。


2.Vector原理

  • 数据安排及操作方式与array非常相似。两者的唯一差别在于空间运用的灵活性。

  • 静态空间,一旦配置好了就不能改变了,如果程序需要一个更大的array,只能自己再申请一个更大的array,然后将以前的array中的内容全部拷贝到新的array中。

  • 动态开辟的空间,随着元素的加入,它的内部机制会自动扩充空间以容纳新的元素。

  • 在增加元素时,如果超过自身最大的容量,vector则将自身的容量扩充为原来的两倍。扩充空间需要经过的步骤:重新配置空间,元素移动,释放旧的内存空间。一旦vector空间重新配置,则指向原来vector的所有迭代器都失效了,因为vector的地址改变了

  • vector为什么要用加倍扩容而不是每次增加一个固定的扩容容量?

        vector在push_back以成倍增长可以在均摊后达到O(1)的事件复杂度,相对于增长指定大小的O(n)时间复杂度更好。

        为了防止申请内存的浪费,现在使用较多的有2倍与1.5倍的增长方式,而1.5倍的增长方式可以更好的实现对内存的重复利用。

  • vector的扩容方式为什么是1.5倍或2倍?
  • 假如说我们是以2倍方式扩容(1,2,4,8,16),则第i次扩容期间所需要的空间总量就是2^i次方,如果第4次扩容时总共需要8个元素大小的空间,但是前3次已经释放的空间加起来的总量,刚好是7,而7小于8,不足以我们第4次扩容时所需要的空间,也就是说,如果恰巧以2倍方式扩容,那么每次扩容时前面释放的空间它都不足以支持本次的扩容!!!那么如果是以更高倍数的方式进行扩容,则这个空间它的浪费情况就会更高!!!也就是说,以2倍或者更高倍数的方式进行扩容,会存在2个问题:

    • 空间浪费可能比较大

    • 无法使用前面已经释放的空间

  • STL标准没有严格说明我们应该按照哪一种方式进行扩容,因此不同STL的实现厂商都是按照自己的方式进行扩容的。

  • 一般情况下,在Windows的VS系列编译器下,是按照1.5倍的方式进行扩容,在Linux的g++中,是按照2倍的方式进行扩容的。

  • size、resize、reserve、capacity的区别

        size表示当前vector中有多少个元素(即finish – start);当前容器所存储的个数,

        resize可以改变有效空间的大小,也有改变默认值的功能。capacity的大小也会随着改变。可以有多个参数。创建指定数量的元素并指定vector的存储空间。既分配空间又创建对象。

        reserve是直接扩充到已经确定的大小,可以减少多次开辟、释放空间的问题(优化push_back),从而达到提高效率的目的,其次还可以减少多次要拷贝数据的问题。reserve它只是保证vector中的空间大小(capacity)最少达到参数所指定的大小n。并且它只有一个参数。指定vector的元素总数,不创建对象。

        capacity函数表示它已经分配的内存中可以容纳多少元素(即end_of_storage – start)。即容器在分配新的存储空间能存储的元素总数。返回vector中能存储元素的最大数。

  • vector可能导致其迭代器失效的操作有哪些?

        resize、reserve、insert、assign、push_back等会引起其底层空间改变的操作,都有可能使迭代器失效。

        指定位置元素的删除操作--erase。

  • push_back和emplace_back的区别?

        emplace_back() 和 push_back() 的主要区别,就在于底层实现的机制不同。push_back() 向容器尾部添加元素时,首先会创建这个元素,然后再将这个元素拷贝或者移动到容器中(如果是拷贝的话,事后会自行销毁先前创建的这个元素);而 emplace_back() 在实现时,则是直接在容器尾部创建这个元素,省去了拷贝或移动元素的过程。


3.List原理

  • list的底层是一个双向链表,以结点为单位存放数据,结点的地址在内存中不一定连续,每次插入或删除一个元素,就配置或释放一个元素空间。

  • 和vector容器迭代器的实现方式不同,由于 list 容器的元素并不是连续存储的,所以该容器迭代器中,必须包含一个可以指向 list 容器的指针,并且该指针还可以借助重载的 *、++、--、==、!= 等运算符,实现迭代器正确的递增、递减、取值等操作。

  • 常见时间复杂度

        vector插入、查找、删除时间复杂度分别为:O(n)、O(1)、O(n);

        list插入、查找、删除时间复杂度分别为:O(1)、O(n)、O(1)。


4. deque原理

  • deque是一个双向开口的容器,所谓双向开口就是在头尾两端均可以做元素的插入和删除操作。

  • deque相比于vector最大的差异就在于,支持常数时间内对首尾两端进行插入和删除操作,而且deque没有容量的概念,其内部采用分段连续内存空间来存储元素,在插入元素的时候随时都可以重新增加一段新的空间并链接起来

  • deque提供了Ramdon Access Iterator,同时也支持随机访问和存取,但是它也为此付出了昂贵的代价,其复杂度不能跟vector的原生指针迭代器相提并论。

  • 动态开辟的二维数组空间,第二维固定长度的数组空间,扩容的时候(第一维的数组进行2倍扩容)。

    deque内部实现的是一个双向队列。元素在内存连续存放。随机存取任何元素都在常数时间完成(仅次于vector)。所有适用于vector的操作都适用于deque。在两端增删元素具有较佳的性能(大部分情况下是常数时间)。

  • deque的中控器

        deque为了维持整体连续的假象,设计一个中控器,其用来记录deque内部每一段连续空间的地址。大体上可以理解为deque中的每一段连续空间分布在内存的不连续空间上,然后用一个所谓的map作为主控,记录每一段内存空间的入口,从而做到整体连续的假象。

  • deque的迭代器是怎么回事呢?

        deque提供的是一个随机访问迭代器,由于是分段连续空间,其必须记录当前元素所在段的信息,从而在该段连续空间的边缘进行前进或者后退的时候能知道跳跃到的上一个或下一个缓冲区。deque必须完完整整的掌握和控制这些信息,以达到正确的跳跃。

  • deque的数据结构

        deque维护着一个map,用来记录每个缓冲区的位置。除了map外,deque的数据结构还维护着start和finish两个迭代器,分别指向deque的首尾。此外,他还必须知道map的大小,一旦map提供的节点不足,就需要配置一块更大的map。



参考

C++面试-STL篇,细节有点多 - cpp后端技术的文章 - 知乎

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/465505.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

MySQL数据库中的视图

视图 ​ 本篇将开始介绍有关数据库中视图的相关知识点,其中主要包含视图的基本使用,视图规则和限制。 ​ 视图是一个虚拟表,其内容由查询定义。同真实的表一样,视图包含一系列带有名称的列和行数据,视图的数据变化会…

Docker 镜像拉不动?自建 Docker Hub 加速站 解决镜像拉取失败

本文首发于只抄博客,欢迎点击原文链接了解更多内容。 前言 众所周知,6 月份的时候,Docker Hub 的镜像就已经无法正常拉取,那会随手用 Nginx 反代了一下 Docker Hub,建了个自用的镜像站,一直用到了 9 月份&…

应对传统能源企业管理人员青黄不接问题:搭建系统完善的招聘管理体系

应对传统能源企业管理人员青黄不接问题:搭建系统完善的招聘管理体系 对于很多传统能源企业由于成立时间久,发展到现在,往往都面临着一个共性问题,即未来三到五年,老员工退休后,新员工如何接续的问题。这个…

C++进阶-->红黑树的实现

1、红黑树的概念 红黑树是一棵二叉搜索树,他和前面AVL树不同的是红黑树不是通过平衡因子来保证树的平衡,而是在树结点的处加多了个记录颜色的变量,这个变量可以是红色或者黑色。通过对任何一条从根到叶子的路径上各个结点的颜色进行约束&…

Linux操作系统开机引导

linux操作系统的开机引导的过程 linux操作系统开机流程图 1、开机自检:根据bios的设置,对cpu、内存、显卡、键盘等设备进行初步检测,如果以上检测设备正常工作,系统会把控制权移交到硬盘 总结:检测包含系统启动操作系…

DataX 的安装配置和使用 (详细版)

1,上传解压 1,开始上传安装包到你虚拟机上放置安装包的文件夹 2,开始解压 ,配置环境变量 1、上传 /opt/modules 2、解压 tar -zxvf datax.tar.gz -C /opt/installs 3、修改 vi /etc/profile 配置环境变量: export DAT…

蓝桥杯第21场小白入门赛补题

5.蓝桥派对 思路 :一个区间与多少个其他区间有关联,先对所有区间左端点和右端点从小到大排序,对于每个询问,我们先算出[1,r]这个区间里有多少个区间的起点即区间总数,使用upper_bound函数,然后使用lower_bo…

Linux篇(常见入门命令)

目录 一、开启终端 二、Linux命令格式 1. 什么是Linux 的命令? 三、Linux下的命令补全 四、切换用户 五、uname:查看操作系统信息 六、ls:查看目录下文件 1. 用法一 2. 用法二 3. 用法三 七、pwd:显示当前路径 八、cd&…

7.qsqlquerymodel 与 qtableview使用

目录 qtableview 委托QStyledItemDelegateQAbstractItemDelegateCheckBoxItemDelegate使用 qtableview 委托 //设置单元格委托 void setItemDelegate(QAbstractItemDelegate *delegate); QAbstractItemDelegate *itemDelegate() const;//设置列委托 void setItemDelegateForCol…

AMD显卡低负载看视频掉驱动(chrome edge浏览器) 高负载玩游戏却稳定 解决方法——关闭MPO

2024.11.6更新 关闭MPO有点用但是还是驱动掉到恶心,找到终极方法了视频输出直接插主板走核显,稳得一笔,3dmark跑了个分几乎没变化。核显负责桌面浏览器,独显就专心只跑游戏。等24.11驱动再看看 问题 折磨的开始是天下苦黄狗久矣&…

VS2022远程连接调试编译Linux环境下的C++代码

工具:VS2022 虚拟机:RHEL 8.0 一、下载必要工具 1.VS2022组件安装 打开VS2022Installer,点击修改下载必要工具。 选择Linux 和嵌入式开发,然后点击右下角的修改! 等待安装........ 安装完成后,创建Linu…

AI笔筒操作说明及应用场景

AI笔筒由来: 在快节奏的现代办公环境中,我们一直在寻找既能提升效率、增添便利,又能融入企业文化、展现个人品味的桌面伙伴。为此,我们特推出专为追求卓越、注重细节的您设计的AI笔筒礼品版,它集高科技与实用性于一身…

爱普生 SG–WriterⅡ 石英可编程手工烧录器

在电子制造与研发的复杂世界中,爱普生 SG–WriterⅡ 石英可编程手工烧录器犹如一把神奇的钥匙,开启了石英晶振编程的无限可能,为众多领域的电子设备注入了精准与稳定的灵魂。 作为手工烧录器,SG–WriterⅡ 独具特色。在当今多样化…

数据库->索引

目录 一、索引是什么 二、索引的数据结构 1.HASH 2.二叉搜索树 3.N叉树(B树) 4.B树 5.B树与B树的区别 三、MYSQL的页 1.页文件头与页文件尾 2.页主体 3.页目录 4.数据页头 四、B在MYSQL索引中的应用 1.应用 2.计算三层树⾼的B树可以存放多少条记录 五、索引分类…

mongodb 按条件进行备份和恢复

在宝塔面板环境下,可以在定时任务设置备份mongodb但是存在缺陷,mongodb如果存储日志,一定时间后会特别巨大,全量备份会导致服务器卡死并很快耗尽磁盘空间,按一定的条件对进行,按天备份数据是必须的。我们用…

从SRE视角透视DevOps的构建精髓

SRE 侧重系统稳定性,DevOps 强调开发运维协作。SRE 实践助力DevOps,提升系统稳定性与团队协作效率。 SRE 运用软件工程的原理,将系统管理员的手工任务自动化,负责运维由系统组件构成的服务,确保服务稳定运行。SRE职责涵…

【数据库】elasticsearch

1、架构 es会为每个索引创建一定数量的主分片和副本分片。 分片(Shard): 将索引数据分割成多个部分,每个部分都是一个独立的索引。 主要目的是实现数据的分布式存储和并行处理,从而提高系统的扩展性和性能。 在创建索…

深度学习基础知识-编解码结构理论超详细讲解

编解码结构(Encoder-Decoder)是一种应用广泛且高效的神经网络架构,最早用于序列到序列(Seq2Seq)任务,如机器翻译、图像生成、文本生成等。随着深度学习的发展,编解码结构不断演变出多种模型变体…

spark-on-k8s 介绍

spark-on-k8s 介绍 摘要 最近一段时间都在做与spark相关的项目,主要是与最近今年比较火的隐私计算相结合,主要是在机密计算领域使用spark做大数据分析、SQL等业务,从中也了解到了一些spark的知识,现在做一个简单的总结&#xff…

探索PickleDB:Python中的轻量级数据存储利器

文章目录 探索PickleDB:Python中的轻量级数据存储利器1. 背景:为什么选择PickleDB?2. PickleDB是什么?3. 如何安装PickleDB?4. 简单的库函数使用方法创建和打开数据库设置数据获取数据删除数据保存数据库 5. 应用场景与…