什么是双端队列和列表STL容器之间的区别?(What's the difference be

2019-07-18 06:56发布

两者有什么区别? 我的意思是这些方法都是一样的。 因此,对于用户,他们同样工作。

那是对的吗??

Answer 1:

从(过时,但仍然非常有用) SGI STL的总结deque

甲双端队列为非常像一个矢量:像载体,它是支持在中间元件的随机存取的元件,恒定时间插入和在序列的端部去除的元素,和线性时插入和移除的序列。

其中双端队列从矢量不同的主要途径是双端队列还支持恒定时间插入和移除元件中的所述序列的开始。 此外,双端队列不具有任何成员函数类似于向量的容量()和储备(),并且不提供任何与那些部件相关联的功能上的迭代器有效性的保证。

下面是对汇总list从同一网站:

列表是一个双向链表。 即,它是支持向前和向后遍历,和(摊销)恒定时间插入和移除在开始或结束时,或在中间元素的序列。 列出有插入和拼接,不坏迭代器列表元素的重要属性,即使去除无效只指向被删除元素的迭代器。 迭代器的排序可以改变(即目录::迭代器可能会比以前的列表操作后,不同的前置或后续),但自己不会被无效或作出的迭代器指向除非失效不同元素或突变是明确的。

总之,容器可以具有共享例程,但对于那些例程时间保证从容器的不同而不同的容器中 。 考虑到使用的这些容器的一个任务时,这是非常重要的:考虑到容器如何将最常用的(例如,更比的插入/删除搜索)走一段很长的路在指导你正确的容器。



Answer 2:

让我列举下的差异:

  • 双端队列管理其使用动态阵列元件,提供了随机接入 ,并具有几乎相同的接口作为载体。
  • 列表管理其元素作为双向链表并没有提供随机访问

  • 双端队列提供快速的插入和删除在年底和年初两者。 插入和在中间删除元素是比较慢的,因为高达任两端的所有元件可被移动,以腾出空间或填充的间隙。
  • 列表中,插入和删除元素是在每个位置,包括两端快。

  • 双端队列 :任何插入或大于在开始或结束的其他元素的删除无效引用该双端队列的元素的所有指针,引用和迭代器。
  • :插入和删除元素不坏的指针,引用和迭代器等元素。

复杂

             Insert/erase at the beginning       in middle        at the end

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


Answer 3:

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

std::deque ,在另一方面,被实现更象std::vector 。 它具有由索引,以及插入和移除在开始和结束时,它提供了比列表显着不同的性能特性恒定的访问时间。



Answer 4:

编号A双端队列只支持O(1)的插入和删除在正面和背面。 它可以是,例如,可与缠绕的载体来实现。 因为它也保证了O(1)随机访问,你可以确信它不使用(只)双向链表。



Answer 5:

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

  • 一种载体是单个连续存储器块。
  • 甲双端队列是一组链接的存储器块,其中一个以上的元素被存储在每个存储器块的。
  • 列表是一组分散在存储器元件,即:只有一个元素被存储每存储器“块”。

需要注意的是双端队列的目的是要设法平衡矢量和列表的优点,而没有它们各自的缺点。 它是在内存有限的平台特别有趣的容器,例如微控制器。

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



Answer 6:

性能差异已经由他人很好地解释。 我只是想补充一点,相似甚至相同的接口在面向对象的编程是常见的 - 编写的面向对象软件的一般方法的一部分。 你绝不应认为两个类的工作方式相同,只是因为他们实现相同的接口,任何比你更应该假定一匹马就像一只狗,因为它们都实现攻击()和make_noise()。



文章来源: What's the difference between deque and list STL containers?
标签: c++ list stl deque