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

C++之序列容器(vector,list,dueqe)

1.大体对比

在软件开发的漫长历程中,数据结构与算法始终占据着核心地位,犹如大厦的基石,稳固支撑着整个程序的运行。在众多编程语言中,数据的存储与管理方式各有千秋,而 C++ 凭借其丰富且强大的工具集脱颖而出,尤其是在处理序列数据方面,C++ 标准模板库(STL)中的序列容器 vectorlist 和 deque 更是展现出卓越的性能与高度的灵活性。

和一些编程语言中单一的数据存储方式相比,C++ 这三种序列容器的存在,无疑为开发者提供了更多样化的选择。例如,在 Python 中,主要通过列表(list)来存储序列数据,其本质上是一种动态数组,但在处理大规模数据的随机访问和频繁插入删除操作时,性能表现往往不尽如人意。反观 C++ 的 vector,它与传统数组有相似之处,却具备了自动调整大小的功能,这一特性让其在面对数据量动态变化的场景时,能够轻松应对,极大地提升了开发效率。

再将目光投向链表结构。在 Java 语言中,虽然没有像 C++ list 这样直接对应的双向链表容器,但开发者可以通过自定义类和节点来构建链表结构。然而,这种方式不仅实现起来较为繁琐,而且在进行常见的元素操作,如插入和删除时,其效率远不及 C++ 的 list。C++ 的 list 作为双向链表,每个节点都包含指向前一个节点和后一个节点的指针,这种数据结构使得在任意位置进行插入和删除操作的时间复杂度都保持在常数级别,在需要频繁修改序列数据的场景中,它的优势便得以充分彰显。

deque 则是 C++ 序列容器中的一颗独特 “新星”,它巧妙地融合了 vector 和 list 的部分优势。和 Java 中的双端队列(ArrayDeque)相比,C++ 的 deque 不仅在两端进行元素的插入和删除操作时具有高效性,而且在支持随机访问方面也毫不逊色。这意味着,在既需要快速在两端增减元素,又要对序列中的元素进行随机访问的复杂场景下,deque 能够提供更为平衡和高效的解决方案。

正是基于这些显著的特性差异,深入了解 C++ 的 vectorlist 和 deque 这三种序列容器,对于每一位追求卓越编程质量的开发者而言,都显得尤为重要。接下来,让我们拨开迷雾,详细剖析这三种序列容器的独特之处,探寻它们在不同编程场景下的最佳应用方式

 2.数据结构

1.vector(连续)

 2.list(指针)

3.deque

3.成员函数

这个三个人的成员函数是一样

3.1 创建

vector():默认构造函数,创建一个空的 vector。
vector(size_type n, const T& value = T()):创建一个包含 n 个值为 value 的元素的 vector。
vector(const vector& other):拷贝构造函数,创建一个 other 的副本。
vector(InputIterator first, InputIterator last):使用迭代器 first 到 last 范围内的元素初始化list():默认构造函数,创建一个空的 vector。
list(size_type n, const T& value = T()):创建一个包含 n 个值为 value 的元素的 vector。
list(const vector& other):拷贝构造函数,创建一个 other 的副本。
list(InputIterator first, InputIterator last):使用迭代器 first 到 last 范围内的元素初始化 deque():默认构造函数,创建一个空的 vector。
deque(size_type n, const T& value = T()):创建一个包含 n 个值为 value 的元素的 vector。
deque(const vector& other):拷贝构造函数,创建一个 other 的副本。
deque(InputIterator first, InputIterator last):使用迭代器 first 到 last 范围内的元素初始化 

 3.2 访问


back()//返回队列尾部元素的引用。
front()//返回队列头部元素的引用。
clear()//清空队列中的所有元素。
empty()//判断队列是否为空。
size()//返回队列中元素的个数。
begin()//返回头位置的迭代器
end()//返回尾+1位置的迭代器//vector没有
rbegin()//返回逆头位置的迭代器 
rend()//返回逆尾-1位置的迭代器 //list没有
下标访问 []

 3.3删除

pop_back()//删除队列尾部的元素。
pop_front()//删除队列头部的元素
erase(iterator pos):移除 pos 位置的元素。
erase(iterator first, iterator last):移除 first 到 last 范围内的元素。
clear():移除 vector 中的所有元素

3.4插入

push_back(const T& value)
push_front(const T& value)
insert(iterator pos, const T& value)

 4.实现队列和栈

 栈:一种先进后出的数据结构

队列:一种先进先出的数据结构

用vector实现栈:

#include<vector>
#include<string>
using namespace std;template<class T> class stack {
private:std::vector<T> data;
public://创建stack();stack(const stack& other):data(other.data){};stack& operator=(const stack& other){data=other.data;return *this;}stack(int n, T val):data(n,val){}//访问int size()const {return data.size();}bool empty()const{if(data.size()==0)return true;elsereturn false;}T top() const{if(data.empty()==true)throw string("stack is empty");elsereturn data.back();}//插入void push(T val){data.push_back(val);}//删除void pop(){if(data.empty()==true)throw string("stack is empty");else{data.pop_back();}}~stack();};

5.总结

对比维度std::vectorstd::liststd::deque
底层结构动态数组,在内存中分配连续的存储空间。当容量不足时,通常会重新分配更大的内存块,将原数据复制过去并释放旧内存。双向链表,由一系列节点构成,每个节点包含数据、指向前一个节点的指针和指向后一个节点的指针。由多个固定大小的数组块组成,每个数组块内部连续存储,数组块之间通过指针连接,形成双端队列结构。
访问操作- 支持随机访问,可通过下标直接访问元素,时间复杂度为 \(O(1)\)。
- 访问元素非常高效,就像操作普通数组一样。
- 不支持随机访问,若要访问特定位置元素,需从头或尾开始遍历链表,时间复杂度为 (O(n))。
- 只能顺序访问元素。
- 支持随机访问,通过下标访问元素的时间复杂度为(O(1))。
- 虽然能随机访问,但由于是分段连续存储,在效率上可能略低于 vector
插入操作 在尾部插入元素效率高,平均时间复杂度为 (O(1)),但若触发内存重新分配,时间复杂度为 (O(n))。 在中间或头部插入元素,需要移动插入位置之后的所有元素,时间复杂度为 (O(n))。- 在任意位置插入元素的时间复杂度均为 (O(1)),只需修改相邻节点的指针。
- 插入操作非常灵活,效率高。
- 在头部和尾部插入元素效率高,时间复杂度为 (O(1))。
- 在中间插入元素,需要移动部分元素,时间复杂度为 (O(n)),但通常比 vector 移动元素的开销小。
删除操作- 在尾部删除元素效率高,时间复杂度为(O(1))。
- 在中间或头部删除元素,需要移动删除位置之后的所有元素,时间复杂度为 (O(n))。
 在任意位置删除元素的时间复杂度均为 (O(1)),只需修改相邻节点的指针。- 在头部和尾部删除元素效率高,时间复杂度为 \(O(1)\)。
- 在中间删除元素,需要移动部分元素,时间复杂度为 \(O(n)\),但通常比 vector 移动元素的开销小。
空间利用- 由于是连续存储,可能会有内存碎片问题。当容量不足重新分配内存时,可能会预留一定的额外空间,造成空间浪费。
- 不过,它的空间利用率相对较高,因为没有额外的指针开销。
每个节点都需要额外的指针来指向前一个和后一个节点,增加了内存开销。
- 但链表节点在内存中可以不连续存储,不会因为预留空间而造成浪费。
- 由于需要维护多个数组块以及块之间的连接信息,会有一定的额外开销。
- 不过,它在动态扩展时不需要像 vector 那样重新分配并复制大量数据,空间管理相对灵活。
迭代器-随机访问迭代器,支持 ++--+- 等操作,可以像指针一样灵活地在容器中移动。- 双向迭代器,支持 ++ 和 -- 操作,能双向遍历链表,但不支持随机访问。- 随机访问迭代器,与 vector 的迭代器类似,支持高效的随机访问操作。
迭代器失效情况- 当发生插入或删除操作导致内存重新分配时,所有迭代器、指针和引用都会失效。
- 在插入或删除元素后,插入或删除位置之后的迭代器、指针和引用会失效。
- 插入操作不会使任何迭代器、指针和引用失效。
- 删除操作只会使指向被删除节点的迭代器、指针和引用失效。
在头部或尾部插入元素时,迭代器一般不会失效,但指向元素的引用和指针可能会失效。
- 在中间插入或删除元素时,插入或删除位置之后的迭代器、指针和引用会失效。
使用场景 适合需要频繁随机访问元素,且插入和删除操作主要在尾部进行的场景,如存储一组数据并经常通过下标访问。
- 实现栈、队列等数据结构时,若操作主要集中在尾部,vector 是不错的选择。
- 适合需要频繁在任意位置进行插入和删除操作,而对随机访问需求较少的场景,如实现链表类的数据结构。
- 当需要频繁进行元素的移动、插入和删除,且不需要随机访问元素时,list 更合适。
- 适合需要在头部和尾部频繁进行插入和删除操作,同时也需要随机访问元素的场景,如实现双端队列。
- 当数据量较大,且需要在两端进行高效操作时,deque 是一个较好的选择。

相关文章:

C++之序列容器(vector,list,dueqe)

1.大体对比 在软件开发的漫长历程中&#xff0c;数据结构与算法始终占据着核心地位&#xff0c;犹如大厦的基石&#xff0c;稳固支撑着整个程序的运行。在众多编程语言中&#xff0c;数据的存储与管理方式各有千秋&#xff0c;而 C 凭借其丰富且强大的工具集脱颖而出&#xff…...

网络安全技术和协议(高软43)

系列文章目录 网络安全技术和协议 文章目录 系列文章目录前言一、网络安全技术1.防火墙2.入侵检测系统IDS3.入侵防御系统IPS 二、网络攻击和威胁三、网络安全协议四、真题在这里插入图片描述 总结 前言 本节讲明网络安全技术和协议方面的相关知识。 一、网络安全技术 1.防火…...

LeetCode697

好的&#xff0c;根据你提供的代码和LeetCode题号&#xff08;697&#xff09;&#xff0c;我将帮助你生成一个结构化的Markdown文档。首先&#xff0c;我们需要补充一些必要的信息&#xff0c;如题目描述、示例、思路分析等。如果你能提供这些信息会更好&#xff0c;否则我会基…...

js基本功(四)

ASCII ASCII(American Standard Code for Information Interchange,美国信息交换标准代码)是一种字符编码标准,用于表示英文字符、数字、标点符号以及一些控制字符。 可以通过 charCodeAt() 方法获取字符的 ASCII 码,也可以通过 String.fromCharCode() 方法将 ASCII 码转…...

linux | Vim 命令快捷操作

注&#xff1a;本文为过去的 “vim 使用笔记”。 跳转命令 跳转命令 #&#xff1a;向前查找光标当前所在单词&#xff0c;并跳转到该单词的上一个出现位置。*&#xff1a;向后查找光标当前所在单词&#xff0c;并跳转到该单词的下一个出现位置。 行内跳转 0&#xff1a;跳转…...

开源订货系统哪个好 三大订货系统源码推荐

在数字化转型加速的今天&#xff0c;企业对订货系统的需求日益增长。一款优质的订货系统源码不仅能提升供应链效率&#xff0c;还能通过二次开发满足个性化业务需求。这里结合 “标准化、易扩展” 两大核心要求&#xff0c;为您精选三款主流订货系统源码&#xff0c;助您快速搭…...

跟着 Lua 5.1 官方参考文档学习 Lua (11)

文章目录 5.4.1 – PatternsCharacter Class:Pattern Item:Pattern:Captures: string.find (s, pattern [, init [, plain]])例子&#xff1a;string.find 的简单使用 string.match (s, pattern [, init])string.gmatch (s, pattern)string.gsub (s, pattern, repl [, n])例子&…...

使用 MyBatis XML 和 QueryWrapper 实现动态查询

本文档介绍了如何在 MyBatis 中结合 XML 配置和 MyBatis-Plus 的 QueryWrapper 来实现动态查询。 1. XML 中定义基本查询 首先&#xff0c;在 MyBatis XML 文件中定义一个基本的 select 查询&#xff1a; <select id"selectCode" resultType"java.util.Ma…...

视频理解开山之作 “双流网络”

1 论文核心信息 1.1核心问题 任务&#xff1a;如何利用深度学习方法进行视频中的动作识别&#xff08;Action Recognition&#xff09;。挑战&#xff1a; 视频包含时空信息&#xff0c;既需要捕捉静态外观特征&#xff08;Spatial Information&#xff09;&#xff0c;也需要…...

每日一题——搜索二维矩阵

搜索二维矩阵 一、题目背景二、题目描述示例 1&#xff1a;示例 2&#xff1a;约束条件&#xff1a; 三、解题思路分析1. **错误思路回顾**2. **Z字形查找算法**算法步骤&#xff1a; 3. **算法优势** 四、代码实现代码说明&#xff1a; 五、测试用例测试用例 1&#xff1a;测试…...

PPT 小黑第21套

对应大猫22 动作按钮 “转到首页” 编号从1开始显示&#xff0c;点设计 -幻灯片大小 -修改幻灯片编号起始值为0&#xff08;那么第二张幻灯片页码为1&#xff09;...

大模型day01自然语言+大模型+环境

[TOC]大模型day01 自然语言处理 汉字的词是连着的&#xff0c;所以需要一个汉语处理模块&#xff0c;把词语、成语自动加空格隔开。 知识图谱构建——>从大语言文本挖掘出来 自然语言处理&#xff1a;翻译、智能语音 自然语言处理&#xff1a;理解一句话意思&#xff0c…...

VSTO(C#)Excel开发3:Range对象 处理列宽和行高

初级代码游戏的专栏介绍与文章目录-CSDN博客 我的github&#xff1a;codetoys&#xff0c;所有代码都将会位于ctfc库中。已经放入库中我会指出在库中的位置。 这些代码大部分以Linux为目标但部分代码是纯C的&#xff0c;可以在任何平台上使用。 源码指引&#xff1a;github源…...

【2025】Electron + React 架构筑基——从零到一的跨平台开发

引言 源代码仓库&#xff1a; Github仓库【electron_git】 你是否厌倦了在命令行中反复输入git status&#xff0c;却依然无法直观看到文件变化&#xff1f; 是否羡慕VS Code的丝滑Git集成&#xff0c;却苦恼于无法定制自己的专属工具&#xff1f; 本专栏将为你打开一扇新的…...

AWS 如何导入内部SSL 证书

SSL 证书的很重要的功能就是 HTTP- > HTTPS, 下面就说明一下怎么导入ssl 证书,然后绑定证书到ALB. 以下示例说明如何使用 AWS Management Console 导入证书。 从以下位置打开 ACM 控制台:https://console.aws.amazon.com/acm/home。如果您是首次使用 ACM,请查找 AWS Cer…...

清华北大推出的 DeepSeek 教程(附 PDF 下载链接)

清华和北大分别都有关于DeepSeek的分享文档&#xff0c;内容非常全面&#xff0c;从原理和具体的应用&#xff0c;大家可以认真看看。 北大 DeepSeek 系列 1&#xff1a;提示词工程和落地场景.pdf  北大 DeepSeek 系列 2&#xff1a;DeepSeek 与 AIGC 应用.pdf  清华 Deep…...

【空地协同技术教程:概念与技术手段解析】

空地协同技术教程&#xff1a;概念与技术手段解析 一、空地协同的概念与核心价值 定义 空地协同&#xff08;Air-Ground Collaboration&#xff09;是指通过无人机&#xff08;UAV&#xff09;与无人车&#xff08;UGV&#xff09;等异构平台的跨域协作&#xff0c;利用各自的…...

【2025小黑课堂】计算机二级WPS精选系列20G内容(可下载:真题+预测卷+软件+选择题)

2025年3月全国计算机等级考试即将于3月29日至31日举行。为了帮助广大考生高效备考&#xff0c;小编特意收集并整理了最新版&#xff08;备考2025年3月&#xff09;的小黑课堂计算机二级WPS 电脑题库软件&#xff0c;助力考生在考试中游刃有余&#xff0c;轻松通关&#xff01; …...

蓝桥杯备赛:炮弹

题目解析 这道题目是一道模拟加调和级数&#xff0c;难的就是调和级数&#xff0c;模拟过程比较简单。 做法 这道题目的难点在于我们在玩这个跳的过程&#xff0c;可能出现来回跳的情况&#xff0c;那么为了解决这种情况&#xff0c;我们采取的方法是设定其的上限步数。那么…...

kotlin高级用法总结

Kotlin 是一门功能强大且灵活的编程语言&#xff0c;除了基础语法外&#xff0c;它还提供了许多高级特性&#xff0c;可以帮助你编写更简洁、高效和可维护的代码。以下是 Kotlin 的一些高级用法&#xff0c;涵盖了协程、扩展函数、属性委托、内联类、反射等内容。 协程&#x…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...