程序员经验分享-hwhale

STL —— vector，list，deque，使用与优缺点比较

2023-05-16

关于vector list deque 已经做过介绍，本文是对三种容器的优劣做出比较。
下面是vector list deque的博客链接
vector
list
deque

vector/list对比

底层结构

  • 动态顺序表，一段连续空间
  • 带头结点的双向循环链表

随机访问

  • 支持随机访问，访问某个元素效率O(1)
  • 不支持随机访问，访问某个元素效率O(N)

插入和删除

  • 任意位置插入和删除效率低，需要搬移元素，时间复杂度为O(N)，插入时有可能需要增容，增容：开辟新空间，拷贝元素，释放旧空间，导致效率更低
  • 任意位置插入和删除效率高，不需要搬移元素，时间复杂度为O(1)

空间利用率

  • 底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高
  • 底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低

迭代器

  • 原生态指针
  • 对原生态指针(节点指针)进行封装

迭代器失效

  • 在插入元素时，要给所有的迭代器重新赋值，因为插入元素有可能会导致重新扩容，致使原来迭代器失效，删除时，当前迭代器需要重新赋值否则会失效
  • 插入元素不会导致迭代器失效，删除元素时，只会导致当前迭代器失效，其他迭代器不受影响

使用场景

  • 需要高效存储，支持随机访问，不关心插入删除效率
  • 大量插入和删除操作，不关心随机访问

deque

deque是一个双端队列， 因为底层结构的特殊性，当不需要进行遍历的时候，推荐使用deque，比如stack和queue底部使用的就是deque。
deque综合了上述vector和list的所有优点，唯一的缺陷是，deque由于结构原因，当进行遍历的时候会存在大量的计算，因此效率会极低。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

STL

vector

list

deque

使用与优缺点比较

STL —— vector，list，deque，使用与优缺点比较 的相关文章

  • 如何在 Flutter 中创建网络图像列表

    我使用 Carousel Pro 包在屏幕上实现轮播 在这个 Carousel 类中它需要一个图像列表 Carousel 类的语法是 Carousel images NetworkImage https cdn images 1 mediu

  • 引用计数指针的STL类？

    这应该是微不足道的 但我似乎找不到它 除非不存在这样的类 智能指针的 STL 类 或类集 是什么 UPDATE 感谢您的回复 我必须说我很惊讶没有标准实施 我最终使用了这个 http archive gamedev net referenc

  • 使用 STL 迭代器而不初始化它

    我想做这样的事情 container iterator it NULL switch eSomeEnum case Container1 it vecContainer1 begin break case Container2 it vec

  • 如何使用 std::pair 创建一个集合，该集合使用绑定根据 ::第二个对成员进行排序

    我知道我可以使用以下内容 template

  • 比较通用列表和数组

    为什么 generic list 比 array 慢 通用列表比数组稍慢 但在大多数情况下您不会注意到 主要与稍微复杂的查找有关 据说 List 在幕后 使用数组 但不能保证以与数组相同的方式将节点保留在相邻内存中 然而 我早在 2005

  • 添加到 std::vector 的中间

    有没有办法将值添加到 a 的中间vector在 C 中 假设我有 vector

  • 在 Python 中使用列表理解来执行类似于 zip() 的操作？

    我是一名 Python 新手 我想做的事情之一就是围绕列表理解进行思考 我可以看到这是一个非常强大的功能 值得学习 cities Chicago Detroit Atlanta airports ORD DTW ATL print zip

  • Python如何拆分列表列表？

    我有一个清单清单 myList 1 2 3 4 5 6 7 8 9 10 我想将其分成三个单独的列表 每个列表都有自己的名称 a 1 2 3 b 4 5 6 c 7 8 9 10 我该怎么做呢 您可以直接解压它 a b c myList

  • Android 动态添加联系表单

    Hi 我想实现如图所示的表单 不知道他们如何动态添加字段 这是列表视图吗 可扩展列表 用户可以在运行时添加和删除 我已经检查了包含子项目的可扩展列表 但我们在数组中定义子元素 在图像中它们动态添加 任何指南 链接 Thanks Custom

  • 合并多个列表

    鉴于我有一个列表列表 List

  • 计算 List 中相似的相邻项目数

    我试图在列表中找到相似的相邻项目并计算其数量 例如 List

  • 使用步骤 c++ 构建向量

    是否可以在不使用 C 中的循环的情况下以固定步骤创建从一个值到另一个值的向量 例如 我想用步长 0 5 构建一个从 1 到 10 的向量 在 MATLAB 中我可以按如下方式执行此操作 vector 1 0 5 10 c 中有类似的东西吗

  • 检查多个位置的值并仅在源唯一时返回匹配项

    假设我有一个清单Vendors 阿斯达 乐购 Spar 我有一个清单Sources 或者这个类比中的供应商 家乐氏 Kellogg 吉百利 Cadbury 雀巢 Nestle 强生 Johnsons 帮宝适 Pampers Simple 等

  • 从向量中删除向量::end

    当我使用时它工作正常吗 什么也不做 vector

  • 矩阵向量变换

    我正在编写一个代码来制作软件蒙皮器 骨骼 皮肤动画 并且我正处于 优化 阶段 蒙皮器工作得很好 并且在 Core 上 1 09 毫秒内对 4900 个三角形网格与 22 个骨骼进行蒙皮Duo 2 Ghz 笔记本 我需要知道的是 1 有人可以

  • 在Python中将整数附加到列表的开头[重复]

    这个问题在这里已经有答案了 如何在列表的开头添加一个整数 1 2 3 42 1 2 3 gt gt gt x 42 gt gt gt xs 1 2 3 gt gt gt xs insert 0 x gt gt gt xs 42 1 2 3

  • List.Clear() 在 C# 中是如何实现的？

    我假设它使用数组来实现 List 怎么List Clear 实施的 它实际上清理了数组还是只是为此列表创建了一个新数组 public class List private Array array public void Clear1 arr

  • 通过 id 从通用列表中删除对象

    我有一个像这样的域类 public class DomainClass public virtual string name get set public virtual IList

  • 在Python中创建N*N*N列表时出现问题

    我正在尝试创建一个 3 维 NNPython 中的 N 列表 如下所示 n 3 l 0 n n n 不幸的是 这似乎没有正确地 克隆 列表 正如我所想的那样 gt gt gt l 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

  • Java 阻止列表实现

    我在 SO 和 Google 上搜索了这个问题的答案 但到目前为止找不到合适的解决方案 我目前正在研究图形路由问题中的 LayerManager 管理器负责提供和重置一组固定的层 我想使用阻止列表来实现消费者 生产者模式 以便只要没有可用的

随机推荐

  • android 自定义多功能进度条

    自定义进度条 xff0c 直接在布局文件里传入颜色值 xff0c 不用自己再去写样式 xff0c 还可以 效果图 xff1a git地址

  • 树莓派L298N电机驱动程序连接图文教程

    手里有一块树莓派3闲置很久 xff0c 不知干点啥好呢 看到不少网友用树莓派做智能小车 xff0c 好像很好玩的酱紫 xff0c 就到淘宝买了一些配件 对于硬件小白的我来说安装过程并不轻松 xff0c 网上看了很多资料但有的地方介绍的并不很

  • 一个比较好用的socket 类封装(封装http 请求)

    name myhttp h function http 请求 copyright author mark date 2008 05 13 ifndef MY HTTP INCLUDE define MY HTTP INCLUDE inclu

  • Odroid U3 烧写镜像文件

    在Ubuntu下往Odroid U3板子的eMMC卡里烧写xubuntu镜像文件 xff0c 主要步骤如下 xff1a 1 下载要烧写的镜像文件 xff0c 按照需要 xff0c 我下载的是桌面版的xubuntu 13 04 desktop

  • 解决odroid-XU3的HDMI输出问题

    odroid XU3的板子直接通过microHDMI口连接显示器 xff0c 并没有显示 解决方法是修改 media boot boot ini文件 xff0c 取消屏蔽与HDMI设置相关语句 重启之后 xff0c 解决问题 由于不同的显示

  • 现有的 TypeRef 应有对应的 TypeDef(Impl)，但它没有

    现有的 TypeRef 应有对应的 TypeDef Impl xff0c 但它没有 本人需要在C 中调用C 43 43 代码 xff0c 故而建立了一个CLR项目 xff0c 建立了四个文件 xff0c 分别是两个纯C 43 43 文件 C

  • [zed2i] 相机内参数获取

    内置对应的程序 xff1a 双目SDK校正方法 关灯避免反射 xff0c 使得房间的灯光尽可能的黑 xff0c 拿着相机对准屏幕的标定板 xff08 可以不关灯 xff09 开始校正 xff0c 红圈是目标 xff0c 需要移动蓝圈 xff

  • Unity 2D独立开发手记（八）：基于A*算法的简易寻路

    被生活 43 43 了一个多月 xff0c 都没时间上来吹比了 因为破游戏准备设计敌人了 xff0c 苦于Unity自带的导航系统迟迟不适配2D项目 xff0c 即便用最新的NavMeshSurface把3D当成2D来用 xff0c 也和我

  • 新建keil工程每一个文件夹的作用

    问 xff1a 头文件stm32f10x sdio c的作用 xff1f 有时候在添加路径的时候为什么不添加src xff1f 有些工程里就添加了 新建工程的每一个文件夹的作用 core xff0c obj xff0c STM32 FWLI

  • VScode使用时常见问题

    写在篇首 xff0c vscode各种蜜汁bug xff0c 记录一下解决方案供大家参考 1 无法使用C 43 43 万能头文件 include xff1c bits stdc 43 43 h xff1e 解决方案 在刷题的时候 xff0c

  • Socket网络编程总结

    网络中进程之间如何通信 Java最初是作为网络编程语言出现的 xff0c 其对网络提供了高度的支持 xff0c 使得客户端和服务器的沟通变成了现实 xff0c 而在网络编程中 xff0c 使用最多的就是Socket 像大家熟悉的QQ MSN

  • linux tcp并发式服务器应用SELECT函数编写实例源代码（转载）

    include lt stdio h gt include lt stdlib h gt include lt unistd h gt include lt errno h gt include lt string h gt include

  • Activity启动模式与任务栈(Task)、TaskAffinity应用场景【转】

    转载请注明出处 xff08 谢谢 xff09 xff1a Activity启动模式与任务栈 Task 全面深入记录 xff08 下 xff09 activities waiting to finish 任务栈 zejian 的博客 CSDN

  • VsCode技巧快捷键

    按住Alt 43 鼠标点击可以有多处光标同时编辑 快速显示大纲 相当于eclipse的打开当前类方法列表弹框 gt 设置为Alt 43 D 搜索go to symbol in File 设置即可 vscode设置匹配花括号跳转 Ctrl 4

  • jmeter察看结果树的响应数据时显示乱码

    找到jmeter的安装路径 xff08 即解压路径 xff09 打开apache jmeter 4 0 bin jmeter properties文件 搜索 encoding 关键字 xff0c 找到如下配置 xff1a The encod

  • class 和 struct的区别

    class 和 struct 最本质的区别 class 是引用类型 xff0c 它在堆中分配空间 xff0c 栈中保存的只是引用 xff1b 而 struct 是值类型 xff0c 它在栈中分配空间 什么是class class xff08

  • 第一周——总体了解STM32以及开发环境搭建

    什么是STM32 意法半导体 xff08 ST xff09 集团于1988年6月成立 xff0c 是由意大利的SGS微电子公司和法国Thomson半导体公司合并而成 STM32系列基于专为要求高性能 低成本 低功耗的嵌入式应用专门设计的AR

  • 【ros下激光雷达的简单使用】（1）

    雷达简单使用方法 xff1a 思蓝科技S2的激光雷达 查看硬件是否连接成功 xff1a 使用lsusb wpf 64 wpfpc lsusb Bus 002 Device 001 ID 1d6b 0003 Linux Foundation

  • AMD CPU 电脑突然画面声音突然卡顿，卡碟声，画面撕裂

    有时候会突然卡顿个一两秒 xff0c 然后自己好 xff0c 如果主板买的早 xff0c 没更新过BIOS版本 xff0c 可能是因为AMD的fTPM设置有个BUG xff0c 开启之后有概率会随机卡顿 xff0c 各大厂商最新的主板驱动应

  • STL —— vector，list，deque，使用与优缺点比较

    关于vector list deque 已经做过介绍 xff0c 本文是对三种容器的优劣做出比较 下面是vector list deque的博客链接 vector list deque vector list对比 底层结构 动态顺序表 xf

热门标签