当前位置: 首页 > news >正文

vector、deque、list相关知识点

vector

  • erase返回迭代器指向删除元素后的元素
  • insert返回迭代器指插入的元素
  • reserve只给容器底层开指定大小内存空间,并不添加新元素

deque

底层数据结构

动态开辟的二维数组,一维数组从2开始,以2倍方式扩容,每次扩容和,原来第二维数组,从新的第一维数组下标oldsize/2开始存放,上下都预留空行,方便deque在首尾添加删除元素

在这里插入图片描述

deque适用于首尾进行操作的场景,和vector比,多了push_frontpop_front()

deque底层内存是否是连续的?

不是,分段连续的,每个第二维是连续的

vector、deque、list对比

  • vector特点:动态数组,内存是连续的,2倍的方式进行扩容,

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

容器的纵向考察:容器掌握的深度

容器的横向考察:各个相似容器之间的对比

vector和deque的区别

vector底层是动态开辟的一维数组,deque则是动态开辟的二维数组

前中后插入删除元素时间复杂度:中间O(n)和末尾O(1), 首部插入deque O(1),vector则是O(n)

对于内存使用效率:vector需要内存空间必须完全连续,deque只需分段连续

中间进行inserterasevector效率更好一点,因为deque分段连续,在边界位置移动需要多余的操作

vector和list区别

vector底层数据结构是数组,list为双向循环链表

数组:增加删除O(n),查询O(n),随机访问O(1)

链表:(考虑搜索时间)增加删除O(1),查询O(n),随机访问O(n)

容器适配器

其实源代码上更接近代理模式

queue和stack底层默认使用deque;priority_queue则使用vector,为什么?

vector初始内存使用效率不如deque,deque一开始就有比较大的第二维连续空间,vector则需要多次的二倍扩容操作。

对于queue需要支持尾插头删,用deque时间复杂度低O(1)

vector需要大片的连续内存,而deque只需要分段的内存,当存储大量数据时,显然deque对于内存的利用率更好一些。

这就是queue和stack底层默认使用deque的理由;

priority_queue堆底层用vector,因为堆是树形结构,底层用vector数组存储更方便随机访问树的节点(下标直接算)。如根节点i,左子节点为 2 i + 1 2i+1 2i+1,右子节点为 2 i + 2 2i+2 2i+2

priority_queue默认是大根堆,比较函数对象为less

http://www.lryc.cn/news/65861.html

相关文章:

  • 多维时序 | MATLAB实现基于VMD-SSA-LSSVM、SSA-LSSVM、VMD-LSSVM、LSSVM的多变量时间序列预测对比
  • 设计模式——适配器模式(类适配器、对象适配器)
  • iOS开发多target
  • 100种思维模型之每日评估思维模型-58
  • libreoffice api
  • 全网最火,Web自动化测试驱动模型详全,一语点通超实用...
  • 如何写软件测试简历项目经验,靠这个面试都要赶场
  • 【Linux】Linux下安装Mysql(图文解说详细版)
  • Cookie和Session的API、登录页面
  • C++数据结构:手撕红黑树
  • Spring IoC 深度学习
  • C语言从入门到精通第17天(指针和数组联用)
  • Android9.0 原生系统SystemUI下拉状态栏和通知栏视图之锁屏通知布局
  • 音视频八股文(10)-- mp4结构
  • python算法中的深度学习算法之深度信念网络(详解)
  • SPSS如何绘制常用统计图之案例实训?
  • 打动人心的故事 | 如何利用文案在Facebook上塑造品牌形象
  • 什么是模糊控制?
  • 仿抖音开发需要注意的问题
  • 如何根据期刊缩写查找期刊?
  • 数据发送流程
  • 堆及其应用
  • MySQL数据库备份脚本
  • 【2023 · CANN训练营第一季】应用开发深入讲解——第三章应用调试
  • 黎曼几何与黎曼流形
  • lua | 运算符与字符串
  • NetBackup 10.2 新功能介绍:PostgreSQL 和 MySQL 自动化恢复达成
  • ADRV9002官方例程开发过程中遇到的问题
  • Figma转换为sketch,分享这3款工具
  • 淘宝天猫1688京东商品详情API接口,封装接口可高并发