122

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

那是对的吗？？

4

9 回答 9

152

让我列出差异：

  • Deque使用动态数组管理其元素 ，提供随机访问，并且具有与向量几乎相同的接口。
  • List将其元素作为 双向链表进行管理，并且不提供随机访问。
  • 双端队列在结尾和开头都提供了快速插入和删除。在中间插入和删除元素相对较慢，因为可能会移动直到两端任一端的所有元素以腾出空间或填充间隙。
  • 在List中，在每个位置插入和删除元素都很快，包括两端。
  • 双端队列：除开头或结尾之外的任何元素的插入或删除都会使引用双端队列元素的所有指针、引用和迭代器无效。
  • List：插入和删除元素不会使指向其他元素的指针、引用和迭代器无效。

复杂

             Insert/erase at the beginning       in middle        at the end

Deque:       Amortized constant                  Linear           Amortized constant
List:        Constant                            Constant         Constant
于 2009-09-17T02:20:47.330 回答
67

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

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

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

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

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

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

于 2009-09-16T23:34:58.880 回答
14

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

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

于 2009-09-16T23:36:52.040 回答
8

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

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

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

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

于 2014-10-26T22:28:31.310 回答
4

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

于 2009-09-16T23:25:27.100 回答
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）

双端队列

std::deque 的插图

集合中的元素存储在内存块中。每个块的元素数量取决于元素的大小：元素越大，每个块越少。潜在的希望是，如果无论元素的类型如何，块的大小都相似，那在大多数情况下都会对分配器有所帮助。

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

双向链表

std::list 的插图

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

于 2020-12-28T09:34:09.320 回答
2

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

  • 对于deque：

    并排存放的物品；

    优化从两侧（前、后）添加数据；

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

    可以被迭代器甚至元素的索引浏览。

    时间访问数据更快。

  • 为了list

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

    只能被迭代器浏览；

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

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

    很好地处理大型元素

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

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

于 2020-05-22T03:51:22.010 回答
1

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

于 2009-09-17T00:05:45.630 回答
1

这是一个使用列表的概念验证代码，无序映射提供 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;
}
于 2020-05-22T00:49:16.720 回答