C ++ STL中双端队列与向量的区别

C ++ STL中双端队列与向量的区别

C++标准模板库 (STL) 中的双端队列

双端队列是具有两端伸缩特性的序列容器。它们类似于向量,但在插入和删除元素的情况下更有效。与向量不同,可能无法保证连续的存储分配。

双端队列基本上是数据结构双端队列的实现。队列数据结构只允许在末尾插入和从前面删除。这就像现实生活中的队列,其中人们从前面移除并在后面添加。双端队列是队列的一种特殊情况,两端都可以进行插入和删除操作。

deque 的功能与 vector 相同,只是前后都增加了 push 和 pop 操作。

C++ STL 中的向量

向量与动态数组相同,具有在插入或删除元素时自动调整自身大小的能力,其存储由容器自动处理。向量元素被放置在连续存储中,以便可以使用迭代器访问和遍历它们。在向量中,数据被插入到最后。在末尾插入需要不同的时间,因为有时可能需要扩展阵列。删除最后一个元素只需要恒定的时间,因为不会发生大小调整。在开头或中间插入和擦除在时间上是线性的。

双端队列和向量的区别:

向量 双端队列
提供中间和结尾的插入和删除方法 提供中间、结尾、开头的插入和删除方法
前端插入删除性能差 前端插入删除性能好
连续存储元素 它包含连续存储元素的内存块列表
末尾添加和删除元素性能好 末尾添加和删除元素性能差

什么时候应该选择 Deque 而不是 Vector?

当我们的操作在开头和结尾添加和删除元素时,可以考虑选择 Deque(双端队列 ADT)。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程