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

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

是这样吗？

90885 次浏览
小开

没有。Deque 只支持前后端的 O (1)插入和删除。例如，它可以在带环绕的向量中实现。由于它还保证了 O (1)随机访问，所以你可以确定它没有(仅仅)使用一个双向链表。

小开
最佳答案

摘自 deque的 SGI STL摘要(虽然有些过时，但仍然很有用) :

Deque 非常像一个向量: 像向量一样，它是一个序列，支持随机访问元素，在序列的末尾定时插入和删除元素，以及在中间线性时间插入和删除元素。

Deque 与矢量的主要区别在于 deque 还支持在序列的开始处定时插入和删除元素。另外，deque 不具有任何类似于 Vector ()和 reserve ()的成员函数，也不提供与这些成员函数相关联的迭代器有效性的任何保证。

下面是来自同一个网站的 list的摘要:

名单就是双向链表。也就是说，它是一个序列，支持向前和向后遍历，以及(分摊)常量插入和删除元素的时间在开始或结束，或在中间。列表有一个重要特性，即插入和拼接不会使列表元素的迭代器失效，即使删除列表元素，也只会使指向被删除元素的迭代器失效。迭代器的顺序可能会改变(也就是说，list: : 迭代器在列表操作之后可能会有一个不同于以前的前辈或后继者) ，但是迭代器本身不会失效或者指向不同的元素，除非这种失效或变异是明确的。

总之，容器可能有共享的例程，但 这些例程的时间保证因容器而异。在考虑使用哪个容器执行任务时，这一点非常重要: 考虑到 怎么做，容器将是最常用的容器(例如，更多用于搜索而不是插入/删除) ，这对于指导您找到正确的容器有很大帮助。

小开

基本上是一个双向链表。

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

小开

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

小开

让我列举一下不同之处:

  • Deque 使用 动态数组 ，提供 < em > 随机 访问 ，并且具有几乎相同的 作为矢量的接口。
  • List 将其元素作为 双向链表 提供 随机访问。
  • Deque 提供快速插入和删除 中插入和删除元素 中间是相对缓慢的，因为 所有元素达到两者之一 两端可以移动以腾出空间或 填补空白。
  • 在 名单中，插入和移除元件在每个位置都很快, 包括两端。
  • Deque : 任何元素的插入或删除 除了在开始或结束时 使所有指针、引用无效, 以及引用元素的迭代器 女王之名。
  • List : 插入和删除元素 不使指针、引用无效, 以及其他元素的迭代器。

复杂性

             Insert/erase at the beginning       in middle        at the end


Deque:       Amortized constant                  Linear           Amortized constant
List:        Constant                            Constant         Constant
小开

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

  • 向量是一个单独的连续内存块。
  • Deque 是一组链接的内存块，其中有多个元素存储在每个内存块中。
  • 列表是分散在内存中的一组元素，即: 每个内存“块”只存储一个元素。

请注意，deque 的设计是为了平衡 尽力而为两个向量和列表的优点，没有各自的缺点。在内存有限的平台上，它是一个特别有趣的容器，例如微控制器。

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

小开

这里是一个概念验证代码使用的列表，无序映射，给予 O (1)查找和 O (1)确切的 LRU 维护。需要(非擦除的)迭代器来保存擦除操作。计划使用在一个 O (1)任意大的软件管理缓存的 CPU 指针的 GPU 内存。向 Linux O (1)调度程序点头(LRU <-> 每个处理器运行队列)。Unorder _ 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;
}
小开

deque和 list之间的显著差异

  • 对于 deque:

    并排存放的物品;

    优化添加数据从两个方面(前，后) ;

    按数字(整数)索引的元素。

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

    访问数据的时间更快。

  • 对于 list

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

    只能由迭代器浏览;

    优化了中间的插入和移除。

    对数据的时间访问较慢，迭代较慢，因为它的空间局部性非常差。

    可以很好地处理大型元素

您还可以检查以下 林克，它比较两个 STL 容器(使用 std: : Vector)的性能

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

小开

我已经为我的 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)

双端队列

Illustration of std::deque

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

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

双向链表

Illustration of a std::list

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


提交答案