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

Question

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

这是正确的吗？

Answer 1

让我列出差异：

• 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

Answer 2

来自（已过时但仍然非常有用）SGI STL 双端队列：

双端队列非常像向量：与向量一样，它是一个序列，支持随机访问元素、在序列末尾以恒定时间插入和移除元素，以及在序列中线性时间插入和移除元素。中。

双端队列与向量的主要区别在于双端队列还支持在序列开头恒定时间插入和删除元素。此外，deque 没有任何类似于向量的capacity() 和reserve() 的成员函数，并且不提供与这些成员函数关联的迭代器有效性的任何保证。

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

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

总之，容器可能具有共享例程，但是这些例程的时间保证因容器而异。当考虑使用这些容器中的哪一个来执行任务时，这一点非常重要：考虑容器的最频繁使用方式（例如，更多地用于搜索而不是插入/删除）会大有帮助引导您到正确的容器。

Answer 3

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

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

Answer 4

我为 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 实现中称为映射）。所有内存块都已满，除了第一个内存块（可能在开头有空间）和最后一个内存块（可能在末尾有空间）。地图本身是从中心向外填充的。与 std::vector 相反，这就是可以在恒定时间内完成两端插入的方式。与 std:::vector 类似，可以在恒定时间内进行随机访问，但需要两个间接而不是一个。与 std::vector 类似，与 std::list 相反，在中间删除或插入元素的成本很高，因为您必须重新组织大部分数据结构。

双向链表

双向链表可能更为常见。每个元素都存储在自己的内存块中，独立于其他元素进行分配。在每个块中，您都有元素的值和两个指针：一个指向前一个元素，一个指向下一个元素。它使得在列表中的任何位置插入元素变得非常容易，甚至将元素的子链从一个列表移动到另一个列表（称为拼接的操作）：您只需更新以下位置的指针：插入点的开头和结尾。缺点是要通过索引找到一个元素，您必须遍历指针链，因此随机访问在列表中的元素数量方面具有线性成本。

Answer 5

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

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

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

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

Answer 6

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

Answer 7

deque 和 list 之间的显着差异

• 对于 deque ：

  并排存储的项目；

  针对从两侧（正面、背面）添加数据进行了优化；

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

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

  访问数据的时间更快。

• 对于列表

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

  只能通过迭代器浏览；

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

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

  可以很好地处理大元素

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

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

Answer 8

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

Answer 9

下面是使用列表、无序映射的概念验证代码，它提供 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;
}