deque 和 list STL 容器有什么区别？

StackOverflow https://stackoverflow.com/questions/1436020

  •  07-07-2019
  •  | 
  •  

题

两者有什么区别？我的意思是方法都是一样的。因此，对于用户来说，它们的工作原理是相同的。

那是对的吗？？

有帮助吗？

解决方案

SGI STL 的摘要 deque ：

  

deque非常像一个向量：就像vector一样，它是一个支持随机访问元素的序列，在序列末尾不断插入和删除元素，以及线性时间插入和删除元素。中间。

     

deque与vector不同的主要方式是deque还支持在序列开头的常量时间插入和元素删除。另外，deque没有任何类似于vector的capacity（）和reserve（）的成员函数，也没有提供与这些成员函数相关的迭代器有效性的任何保证。

以下是来自 list 的摘要同一地点：

  

列表是双向链表。也就是说，它是一个支持前向和后向遍历的序列，以及（开始）（开始）常量时间插入和删除元素的开始或结束，或中间。列表具有重要的属性，即插入和拼接不会使列表元素的迭代器无效，甚至删除也只会使指向被删除元素的迭代器无效。可以更改迭代器的顺序（也就是说，list :: iterator在列表操作之后可能具有与之前不同的前导或后继），但迭代器本身不会失效或被指向不同的元素，除非该失效或突变是明确的。

总之，容器可能有共享例程，但这些例程的时间保证因容器而异。在考虑将哪些容器用于任务时，这一点非常重要：考虑到如何最常用的容器（例如，更多用于搜索而不是插入/删除）需要很长的路要走引导你到正确的容器。

其他提示

让我列出一下差异：

  • 双端队列 管理其元素动态数组, ，提供 随机 访问, ，并且几乎相同 接口作为向量。
  • 列表 将其元素管理为双向链表 并且不 提供 随机访问.
  • 双端队列 提供快速插入和删除 既是结束，也是开始。在 中插入和删除元素 中间相对较慢，因为 所有元素，直到两者中的任何一个 两端可以移动以腾出空间或 填补空白。
  • 在 列表, ，在每个位置插入和删除元素都很快， 包括两端。
  • 双端队列: ：元素的任何插入或删除 除了在开头或结尾 使所有指针、引用、 以及引用元素的迭代器 的德克。
  • 列表: ：插入和删除元素可以 不使指针、引用、 以及其他元素的迭代器。

复杂

             Insert/erase at the beginning       in middle        at the end

Deque:       Amortized constant                  Linear           Amortized constant
List:        Constant                            Constant         Constant

std :: list 基本上是一个双重链表。

std :: deque ，关于另一方面，实现更像 std :: vector 。它具有索引的持续访问时间，以及开头和结尾的插入和删除，这提供了与列表截然不同的性能特征。

没有。 deque仅在前后支持O（1）插入和删除。例如，它可以在具有环绕的向量中实现。由于它也保证了O（1）随机访问，你可以确定它不使用（只是）一个双向链表。

另一个重要的保证是每个不同容器在内存中存储数据的方式：

  • 向量是单个连续的内存块。
  • 双端队列是一组链接的内存块，每个内存块中存储多个元素。
  • 列表是分散在内存中的一组元素，即：每个内存“块”仅存储一个元素。

请注意，双端队列的设计目的是 尝试 平衡了向量和列表的优点而没有各自的缺点。在内存有限的平台（例如微控制器）中，它是一个特别有趣的容器。

内存存储策略经常被忽视，然而，它往往是为特定应用选择最合适的容器的最重要原因之一。

其他人已经很好地解释了性能差异。我只想补充一点，类似甚至相同的接口在面向对象编程中很常见 - 这是编写面向对象软件的一般方法的一部分。你不应该假设两个类的工作方式相同，只是因为它们实现了相同的接口，你应该假设一匹马像狗一样工作，因为它们都实现了attack（）和make_noise（）。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top