aJ.*_*aJ. 116
让我列出差异:
- Deque使用动态数组管理其元素 ,提供随机访问,并且具有与向量几乎相同的接口.
- List将其元素作为双向链表进行管理 ,不提供随机访问.
- Deque在结束和开始时提供快速插入和删除.在中间插入和删除元素相对较慢,因为可以移动直到两端中的任何一个的所有元素以腾出空间或填充间隙.
- 在List中,插入和移除元素在每个位置都很快,包括两端.
- Deque:除了在开头或结尾之外的任何元素的插入或删除都会使引用双端队列元素的所有指针,引用和迭代器无效.
- 列表:插入和删除元素不会使指针,引用和其他元素的迭代器无效.
复杂
Insert/erase at the beginning in middle at the end
Deque: Amortized constant Linear Amortized constant
List: Constant Constant Constant
- 长期的操作表现如上所述.但是,单个操作可能需要比指定时间更长的时间.例如:将一个元素插入到当前容量为10且大小已经为9的向量中,如果capacity为10且size也为10,则时间为线性.因为它必须将所有元素分配并复制到新内存中. (14认同)
- @aJ:`constant`和`amortized constant`有什么区别？ (5认同)
- @aJ:deque如何提供随机访问？这个结构是如何实现的？ (4认同)
- @Lazer - 当您有提前分配内存的对象时，就会发生摊销常量。例如，当您定义向量或双端队列时，它将在内存中分配一些位置（假设为 1024）。但现在，如果您的向量或双端队列增长并且您向其中添加了越来越多的元素（因此它达到了 1024 个元素），它必须做一些事情。它必须创建一个更大的容器（可能是 2048 个单元的容器）+它还必须将所有内容复制到该更大的容器中。因此，它会在恒定的时间内起作用，直到它到达某个点（你必须等待），直到它复制了所有内容 (4认同)
fbr*_*eto 50
deque非常像向量:像vector一样,它是一个支持随机访问元素的序列,在序列末尾插入和删除元素的恒定时间,以及中间元素的线性时间插入和删除.
deque与vector不同的主要方式是deque还支持在序列开始时恒定时间插入和删除元素.此外,deque没有任何类似于vector的capacity()和reserve()的成员函数,并且不提供与这些成员函数关联的迭代器有效性的任何保证.
以下是list来自同一网站的摘要:
列表是双重链表.也就是说,它是一个支持前向和后向遍历的序列,以及(开始)(开始)常量时间插入和删除元素的开始或结束,或中间.列表具有重要的属性,即插入和拼接不会使列表元素的迭代器无效,甚至删除也只会使指向被删除元素的迭代器无效.可以更改迭代器的顺序(也就是说,list :: iterator在列表操作之后可能具有与之前不同的前导或后继),但迭代器本身不会失效或被指向不同的元素,除非该失效或突变是明确的.
总之,容器可能具有共享例程,但这些例程的时间保证因容器而异.考虑到使用的这些容器的一个任务时,这是非常重要的:考虑到如何容器将使用最频繁的(例如,更比的插入/删除搜索)走一段很长的路在指导你正确的容器.
- 实际上,时间保证是列表中最重要的第二个特征.列表的最重要特性是您可以添加和删除元素,而不是使迭代器无效!在(几乎？)每个其他STL容器中,每个编辑操作都会使所有迭代器无效 - 因此要"删除匹配项",您需要在一个操作中累积匹配项,然后在另一个操作中删除它们.在列表中,您可以按照自己的意愿浏览,删除和添加,而不必重新计算迭代器. (19认同)
- std :: list也具有'splice'方法，可让您将两个列表合并在一起 (2认同)
- 这些也是抽象的差异，因此请根据您的情况衡量现实！list 和 deque 都有 O(1) 插入/删除，但不要忘记这意味着 k * O(1)，并且 k 对 list 和 deque 有不同的值。就我而言，将对象添加到列表所需的时间是双端队列的十倍，因为列表需要更多的 new/delete 调用。这显然会因您拥有的 STL 实现而异。 (2认同)
- 您的答案是：对于 **deque**，开始/结束处的插入/删除发生在恒定时间内（以及 [cppreference 上的 std::deque 文档](https://en.cppreference.com/w/cpp/container /deque) 说的是相同的)，而 **list** 则发生在摊余常数时间内。然而，aJ.的[答案](/sf/answers/100549291/)却说相反。根据我的理解，在链表的情况下，开头的插入/删除是恒定的，而结尾的插入/删除是“O(n)”，因为它必须迭代所有节点。我在这里很困惑。您能详细说明一下吗？提前致谢！ (2认同)
lge*_*get 15
我为 C++ 课上的学生制作了插图。这是（松散地）基于（我的理解）GCC STL实现中的实现（ https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/ stl_deque.h和https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_list.h）
双端队列
集合中的元素存储在内存块中。每个块的元素数量取决于元素的大小：元素越大，每个块越少。潜在的希望是，如果无论元素的类型如何，块的大小都相似，那么大多数时候这应该对分配器有帮助。
您有一个列出内存块的数组（在 GCC 实现中称为映射）。所有内存块都已满，除了第一个内存块（可能在开头有空间）和最后一个内存块（可能在末尾有空间）。地图本身是从中心向外填充的。与 a 相反std::vector，这就是如何在恒定时间内完成两端的插入。与 a 类似std:::vector，可以在恒定时间内进行随机访问，但需要两个间接而不是一个。与 类似std::vector或相反std::list，在中间删除或插入元素的成本很高，因为您必须重新组织大部分数据结构。
双向链表
双向链表可能更常见。每个元素都存储在自己的内存块中，独立于其他元素进行分配。在每个块中，您都有元素的值和两个指针：一个指向前一个元素，一个指向下一个元素。它使得在列表中的任何位置插入元素变得非常容易，甚至将元素的子链从一个列表移动到另一个列表（称为splicing 的操作）：您只需更新插入开始和结束处的指针观点。缺点是要通过索引找到一个元素，您必须遍历指针链，因此随机访问在列表中的元素数量方面具有线性成本。
另一个重要的保证是每个不同容器在内存中存储数据的方式：
- 向量是单个连续的内存块。
- 双端队列是一组链接的内存块，其中每个内存块中存储了多个元素。
- 列表是一组分散在内存中的元素，即：每个内存“块”仅存储一个元素。
请注意，deque 旨在尝试平衡 vector 和 list 的优点，而没有各自的缺点。它是内存受限平台（例如微控制器）中的一个特别有趣的容器。
内存存储策略经常被忽视，然而，它往往是为某个应用选择最合适的容器的最重要原因之一。