C ++ STL容器：deque和list有什么区别？
两者有什么区别？ 我的意思是方法都是一样的。 所以，对于一个用户来说，他们的工作是一致的。
那是对的吗？？
从（过时的，但仍然非常有用） SGI STL总结deque ：
一个deque非常像一个向量，就像向量一样，它是一个序列，支持对元素的随机访问，在序列的末尾不断的插入和删除元素，以及在中间线性地插入和删除元素。
deque与vector不同的主要方式是deque也支持序列开始处的元素的恒定时间插入和移除。 另外，deque没有类似vector的容量（）和reserve（）的成员函数，也没有提供任何与这些成员函数关联的迭代器有效性保证。
以下是来自同一网站的list摘要：
一个列表是一个双向链表。 也就是说，它是一个支持向前和向后遍历的序列，以及（分期付款）在开始或结束或中间的元素的常量时间插入和删除。 列表具有重要的属性，插入和拼接不会使迭代器无法列出元素，即使删除也只会使指向被删除元素的迭代器失效。 迭代器的sorting可能会改变（也就是说，list :: iterator在列表操作之后可能会有不同的前置或后继），但是迭代器本身不会失效或者指向不同的元素，除非该失效或突变是明确的。
总之，容器可能有共享例程，但是这些例程的时间保证因容器而异 。 当考虑将这些容器用于哪个任务时，这是非常重要的：考虑到容器将如何被最频繁地使用（例如，更多的search而不是插入/删除）将把你引导到正确的容器。
让我列举一下差异：
- Deque使用dynamic数组pipe理其元素，提供随机访问 ，并具有与vector几乎相同的界面。
- 列表pipe理其元素作为一个双向链表 ，并不提供随机访问 。
- Deque提供快速插入和删除在结束和开始。 在中间插入和删除元素相对较慢，因为直到两端中的任何一个的所有元素都可以被移动以腾出空间或填充间隙。
- 在列表中 ，插入和删除元素在每个位置都很快，包括两端。
- Deque ：任何插入或删除除开始或结束以外的元素都将使所有引用deque元素的指针，引用和迭代器无效。
- 列表 ：插入和删除元素不会使指针，引用和迭代器无效到其他元素。
复杂
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（）。
另一个重要的保证是每个不同的容器将数据存储在内存中的方式：
- 一个向量是一个连续的内存块。
- deque是一组链接的内存块，每个内存块中存有多个元素。
- 列表是分散在内存中的一组元素，即：每个内存“块”只存储一个元素。
请注意，该deque旨在平衡vector和列表的优点，而没有各自的缺点。 在内存有限的平台上，这是一个特别有趣的容器，例如微控制器。
内存存储策略往往被忽视，但是，为某个应用程序select最合适的容器往往是最重要的原因之一。
