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.xdnf.cn/news/5229.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

FreeRTOS 队列详解

目录 一、引言 二、FreeRTOS 队列的基本概念 1.定义与作用 2.队列的长度和数据大小 三、FreeRTOS 队列的特点 1.先进先出(FIFO)特性 2.值传递方式 3.多任务访问 4.阻塞机制 四、FreeRTOS 队列的操作方法 1.创建队列 2.写队列(发送…

Java项目实战II基于Spring Boot的问卷调查系统的设计与实现(开发文档+数据库+源码)

目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发,CSDN平台Java领域新星创作者,专注于大学生项目实战开发、讲解和毕业答疑辅导 一、前言 在当今信息爆炸的时代,问卷调查…

基于JavaWeb的宿舍管理系统的设计与实现

项目描述 临近学期结束,还是毕业设计,你还在做java程序网络编程,期末作业,老师的作业要求觉得大了吗?不知道毕业设计该怎么办?网页功能的数量是否太多?没有合适的类型或系统?等等。这里根据疫情当下,你想解决的问…

EPSON机械手与第三方相机的校准功能设计By python

EPSON机械手与第三方相机的校准功能设计By python 使用Python来实现EPSON机械手与第三方相机的校准功能是一个复杂但可行的任务。这通常涉及以下几个步骤:硬件接口通信、图像处理、标定算法实现和控制逻辑编写。 1. 环境准备 首先,库 pip install numpy opencv-python pyse…

【电子通识】白皮书、应用手册、用户指南、快速入门指南一般的定义是什么?

一般大厂家的器件或模块,除了给数据表以外,还提供应用手册、技术说明、白皮书等各种文档资料。 如下图所示为ST25 NFC/RFID标签和读卡器的文件资料:其中就有技术说明、白皮书、应用手册等。 如下所示为TI INA228技术文档相关资料: 也有应用手册、用户指南、技术文章…

【真实对抗环境】MC-Net: Realistic Sample Generation for Black-Box Attacks

原文标题: MC-Net: Realistic Sample Generation for Black-Box Attacks 原文代码: https://github.com/jiaokailun/A-fast 发布年度: 2024 发布期刊: TIFS 目录 摘要背景创新点模型实验结论 摘要 One area of current research …

0-基于图的组合优化算法学习(NeurIPS 2017)(未完)

文章目录 Abstract1 Introduction2 图上的贪婪算法的通用表述Abstract 为NP-hard组合优化问题设计好的启发式或近似算法通常需要大量的专业知识和试错。我们能否自动化这个具有挑战性、乏味的过程,而不是学习算法呢?在许多实际应用中,通常是相同的优化问题一次又一次地被解…

ctfshow(316)--XSS漏洞--反射性XSS

Web316 进入界面: 审计 显示是关于反射性XSS的题目。 思路 首先想到利用XSS平台解题,看其他师傅的wp提示flag是在cookie中。 当前页面的cookie是flagyou%20are%20not%20admin%20no%20flag。 但是这里我使用XSS平台,显示的cookie还是这样…

AI 大模型重塑软件开发流程

一、AI 大模型的定义 AI 大模型是指具有大量参数和复杂结构的人工智能模型,通过在大规模数据上进行训练,可以学习到丰富的知识和模式。这些模型通常基于深度学习技术,如神经网络,能够处理自然语言、图像、音频等多种类型的数据&am…

LeetCode 3216. 交换后字典序最小的字符串[简单]

. - 力扣(LeetCode) 题目 给你一个仅由数字组成的字符串 s,在最多交换一次 相邻 且具有相同 奇偶性 的数字后,返回可以得到的字典序最小的字符串。 相同奇偶性:如果两个数字都是奇数或都是偶数,则它们具…

建筑行业员工离职SOP的数字化管理

在建筑行业,随着数字化转型的深入,对员工离职的标准操作程序(SOP)进行数字化管理变得尤为重要。这不仅有助于提高管理效率,还能确保离职流程的规范性和合规性。本文将探讨建筑行业如何通过数字化手段管理员工离职SOP&a…

【你也能从零基础学会网站开发】 SQL Server结构化查询语言数据操作应用--DML篇 浅谈SQL JOIN多表查询之FULL JOIN 全连接查询

🚀 个人主页 极客小俊 ✍🏻 作者简介:程序猿、设计师、技术分享 🐋 希望大家多多支持, 我们一起学习和进步! 🏅 欢迎评论 ❤️点赞💬评论 📂收藏 📂加关注 FULL JOIN 全连…

高效数据集成:从旺店通到金蝶云

高效数据集成:从旺店通到金蝶云 旺店通旗舰奇门数据集成到金蝶云星空:柏为销售出库单07.25 在现代企业的运营中,数据的高效流转和准确对接是确保业务顺畅运行的关键。本文将分享一个实际案例——如何通过轻易云数据集成平台,将旺…

Python进阶之IO操作

文章目录 一、文件的读取二、文件内容的写入三、之操作文件夹四、StringIO与BytesIO 一、文件的读取 在python里面,可以使用open函数来打开文件,具体语法如下: open(filename, mode)filename:文件名,一般包括该文件所…

Bert框架详解(上)

目录 一、传统的自然语言处理框架存在的问题 1、RNN网络计算时存在的问题 2、传统word2vec存在的问题 二、Bert模型机制 1、编码-解码框架(Encoder-Decoder) (1)、编码器(Encoder) (2&…

SuperMap iDesktop 崖山数据库型的数据源创建

作者:lzzzz 本文主要介绍如何创建崖山数据库型的数据源,使用版本为超图idesktopX:11.2.1 ,使用环境:Windows 10;yashandb:23.2.5.100,使用环境:centos 7.9。 崖山数据库…

今日 AI 简报| Claude 推出 AI 自动化操作电脑功能、浏览器 AI 助手、全栈 AI 应用构建器、全能文档解析工具等

❤️ 如果你也关注大模型与 AI 的发展现状,且对大模型应用开发非常感兴趣,我会快速跟你分享最新的感兴趣的 AI 应用和热点信息,也会不定期分享自己的想法和开源实例,欢迎关注我哦! 🥦 微信公众号&#xff…

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

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

详解Java之Spring MVC篇二

目录 获取Cookie/Session 理解Cookie 理解Session Cookie和Session的区别 获取Cookie 获取Session 获取Header 获取User-Agent 获取Cookie/Session 理解Cookie HTTP协议自身是“无状态”协议,但是在实际开发中,我们很多时候是需要知道请求之间的…

基于SSM的学生考勤管理系统的设计与实现

项目描述 临近学期结束,还是毕业设计,你还在做java程序网络编程,期末作业,老师的作业要求觉得大了吗?不知道毕业设计该怎么办?网页功能的数量是否太多?没有合适的类型或系统?等等。这里根据疫情当下,你想解决的问…