C ++ STL中双端队列与向量的区别
C++标准模板库 (STL) 中的双端队列
双端队列是具有两端伸缩特性的序列容器。它们类似于向量,但在插入和删除元素的情况下更有效。与向量不同,可能无法保证连续的存储分配。
双端队列基本上是数据结构双端队列的实现。队列数据结构只允许在末尾插入和从前面删除。这就像现实生活中的队列,其中人们从前面移除并在后面添加。双端队列是队列的一种特殊情况,两端都可以进行插入和删除操作。
deque 的功能与 vector 相同,只是前后都增加了 push 和 pop 操作。
C++ STL 中的向量
向量与动态数组相同,具有在插入或删除元素时自动调整自身大小的能力,其存储由容器自动处理。向量元素被放置在连续存储中,以便可以使用迭代器访问和遍历它们。在向量中,数据被插入到最后。在末尾插入需要不同的时间,因为有时可能需要扩展阵列。删除最后一个元素只需要恒定的时间,因为不会发生大小调整。在开头或中间插入和擦除在时间上是线性的。
双端队列和向量的区别:
向量 | 双端队列 |
---|---|
提供中间和结尾的插入和删除方法 | 提供中间、结尾、开头的插入和删除方法 |
前端插入删除性能差 | 前端插入删除性能好 |
连续存储元素 | 它包含连续存储元素的内存块列表 |
末尾添加和删除元素性能好 | 末尾添加和删除元素性能差 |
什么时候应该选择 Deque 而不是 Vector?
当我们的操作在开头和结尾添加和删除元素时,可以考虑选择 Deque(双端队列 ADT)。