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

What's the difference between deque and list STL containers?

提问by Lazer

What is the difference between the two? I mean the methods are all the same. So, for a user, they work identically.

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

Is that correct??

那是对的吗？？

采纳答案by fbrereto

From the (dated but still very useful) SGI STLsummary of deque:

来自（过时但仍然非常有用的）SGI STL摘要deque：

A deque is very much like a vector: like vector, it is a sequence that supports random access to elements, constant time insertion and removal of elements at the end of the sequence, and linear time insertion and removal of elements in the middle.

The main way in which deque differs from vector is that deque also supports constant time insertion and removal of elements at the beginning of the sequence. Additionally, deque does not have any member functions analogous to vector's capacity() and reserve(), and does not provide any of the guarantees on iterator validity that are associated with those member functions.

deque很像vector：和vector一样，它是一个序列，支持元素的随机访问，序列末尾元素的恒定时间插入和移除，以及中间元素的线性时间插入和移除。

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

Here's the summary on listfrom the same site:

这是list来自同一站点的摘要：

A list is a doubly linked list. That is, it is a Sequence that supports both forward and backward traversal, and (amortized) constant time insertion and removal of elements at the beginning or the end, or in the middle. Lists have the important property that insertion and splicing do not invalidate iterators to list elements, and that even removal invalidates only the iterators that point to the elements that are removed. The ordering of iterators may be changed (that is, list::iterator might have a different predecessor or successor after a list operation than it did before), but the iterators themselves will not be invalidated or made to point to different elements unless that invalidation or mutation is explicit.

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

In summary the containers may have shared routines but the time guarantees for those routines differ from container to container. This is very important when considering which of these containers to use for a task: taking into account howthe container will be most frequently used (e.g., more for searching than for insertion/deletion) goes a long way in directing you to the right container.

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

回答by aJ.

Let me list down the differences:

让我列出差异：

• Dequemanages its elements with a dynamic array, provides random access, and has almost the same interface as a vector.
• Listmanages its elements as a doubly linked listand does not provide random access.

• Deque使用动态数组管理其元素 ，提供随机访问，并具有与向量几乎相同的接口。
• List 将其元素作为双向链表进行管理 ，并且不提供随机访问。

---

---

• Dequeprovides Fast insertions and deletions at both the end and the beginning. Inserting and deleting elements in the middle is relatively slow because all elements up to either of both ends may be moved to make room or to fill a gap.
• In List, inserting and removing elements is fast at each position, including both ends.

• Deque在结尾和开头都提供了快速插入和删除。在中间插入和删除元素相对较慢，因为可能移动到两端任一端的所有元素以腾出空间或填充间隙。
• 在List 中，在每个位置插入和删除元素都很快，包括两端。

---

---

• Deque: Any insertion or deletion of elements other than at the beginning or end invalidates all pointers, references, and iterators that refer to elements of the deque.
• List: Inserting and deleting elements does not invalidate pointers, references, and iterators to other elements.

• Deque：除开头或结尾之外的任何元素的插入或删除都会使所有引用 deque 元素的指针、引用和迭代器无效。
• List：插入和删除元素不会使指向其他元素的指针、引用和迭代器失效。

---

---

Complexity

复杂

             Insert/erase at the beginning       in middle        at the end

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

回答by Reed Copsey

std::listis basically a doubly linked list.

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

std::deque, on the other hand, is implemented more like std::vector. It has constant access time by index, as well as insertion and removal at the beginning and end, which provides dramatically different performance characteristics than a list.

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

回答by jose.angel.jimenez

Another important guarantee is the way each different container stores its data in memory:

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

• A vector is a single contiguous memory block.
• A deque is a set of linked memory blocks, where more than one element is stored in each memory block.
• A list is a set of elements dispersed in memory, i.e.: only one element is stored per memory "block".

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

Note that the deque was designed to try tobalance the advantages of both vector and list without their respective drawbacks. It is a specially interesting container in memory limited platforms, for example, microcontrollers.

请注意，deque 旨在尝试平衡 vector 和 list 的优点，而没有各自的缺点。它是内存受限平台（例如微控制器）中的一个特别有趣的容器。

The memory storage strategy is often overlooked, however, it is frequently one of the most important reasons to select the most suitable container for a certain application.

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

回答by Jonathan Graehl

No. A deque only supports O(1) insertion and deletion at the front and back. It may, for example, be implemented in a vector with wrap-around. Since it also guarantees O(1) random access, you can be sure it's not using (just) a doubly linked list.

不可以。deque 只支持前后 O(1) 的插入和删除。例如，它可以在带有环绕的向量中实现。由于它还保证 O(1) 随机访问，因此您可以确定它没有使用（仅）双向链表。

回答by Lee B

The performance differences have been explained well by others. I just wanted to add that similar or even identical interfaces are common in object-oriented programming -- part of the general methodology of writing object-oriented software. You should IN NO WAY assume that two classes work the same way simply because they implement the same interface, any more than you should assume that a horse works like a dog because they both implement attack() and make_noise().

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

回答by Peter Boyle

Here's a proof-of-concept code use of list, unorded map that gives O(1) lookup and O(1) exact LRU maintenance. Needs the (non-erased) iterators to survive erase operations. Plan to use in a O(1) arbitrarily large software managed cache for CPU pointers on GPU memory. Nods to the Linux O(1) scheduler (LRU <-> run queue per processor). The unordered_map has constant time access via hash table.

这是列表的概念验证代码使用，无序映射提供 O(1) 查找和 O(1) 精确 LRU 维护。需要（未擦除的）迭代器才能在擦除操作中存活下来。计划在 O(1) 任意大的软件管理缓存中使用 GPU 内存上的 CPU 指针。向 Linux O(1) 调度程序致敬（LRU <-> 每个处理器运行队列）。unordered_map 可以通过哈希表进行恒定时间访问。

#include <iostream> 
#include <list> 
#include <unordered_map>  
using namespace std; 

struct MapEntry {
  list<uint64_t>::iterator LRU_entry;
  uint64_t CpuPtr;
};
typedef unordered_map<uint64_t,MapEntry> Table;
typedef list<uint64_t> FIFO;
FIFO  LRU;        // LRU list at a given priority 
Table DeviceBuffer; // Table of device buffers

void Print(void){
  for (FIFO::iterator l = LRU.begin(); l != LRU.end(); l++) {
    std::cout<< "LRU    entry "<< *l << "   :    " ;
    std::cout<< "Buffer entry "<< DeviceBuffer[*l].CpuPtr <<endl;
  }  
}
int main() 
{ 

  LRU.push_back(0);
  LRU.push_back(1);
  LRU.push_back(2);
  LRU.push_back(3);
  LRU.push_back(4);

  for (FIFO::iterator i = LRU.begin(); i != LRU.end(); i++) {
    MapEntry ME = { i, *i}; 
    DeviceBuffer[*i] = ME;
  }

  std::cout<< "************ Initial set of CpuPtrs" <<endl;
  Print();

  {
    // Suppose evict an entry - find it via "key - memory address uin64_t" and remove from 
    // cache "tag" table AND LRU list with O(1) operations
    uint64_t key=2;
    LRU.erase(DeviceBuffer[2].LRU_entry);
    DeviceBuffer.erase(2);
  }

  std::cout<< "************ Remove item 2 " <<endl;
  Print();

  { 
    // Insert a new allocation in both tag table, and LRU ordering wiith O(1) operations
    uint64_t key=9;
    LRU.push_front(key); 
    MapEntry ME = { LRU.begin(), key };
    DeviceBuffer[key]=ME;
  }

  std::cout<< "************ Add item 9  " <<endl;
  Print();

  std::cout << "Victim "<<LRU.back()<<endl;
} 

回答by rekkalmd

Among eminent differences between dequeand list

在deque和之间的显着差异中list

• For deque:

  Items stored side by side;

  Optimized for adding datas from two sides (front, back);

  Elements indexed by numbers (integers).

  Can be browsed by iterators and even by element's index.

  Time access to data is faster.

• For list

  Items stored "randomly" in the memory;

  Can be browsed only by iterators;

  Optimized for insertion and removal in the middle.

  Time access to data is slower, slow to iterate, due to its very poor spatial locality.

  Handles very well large elements

• 对于deque：

  并排存放的物品；

  为从两侧（正面，背面）添加数据进行了优化；

  由数字（整数）索引的元素。

  可以通过迭代器甚至元素的索引进行浏览。

  时间访问数据更快。

• 为了 list

  “随机”存储在内存中的项目；

  只能被迭代器浏览；

  针对中间的插入和移除进行了优化。

  由于其空间局部性非常差，对数据的时间访问较慢，迭代较慢。

  处理非常大的元素

You can check also the following Link, which compares the performance between the two STL containers (with std::vector)

您还可以检查以下Link，它比较了两个 STL 容器之间的性能（使用 std::vector）

Hope i shared some useful informations.

希望我分享了一些有用的信息。