deque和list STL容器之间有什么区别?

让我列出不同之处:

• 使用 动态数组 ,提供 通道 ,而且几乎相同
• 列表 双链表 提供

• 德克 在以下位置提供快速插入和删除: 端部可移动以腾出空间或 填补空白。
• 列表 ,在每个位置快速插入和移除元件,

• 德克 :元素的任何插入或删除 不是在开头或结尾 使所有指针、引用无效, 以及引用元素的迭代器 德克的。
• :插入和删除元素不起作用 不使指针、引用无效, 和其他元素的迭代器。

             Insert/erase at the beginning       in middle        at the end

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

来自(已过时但仍然非常有用) SGI STL 总结 deque

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

deque不同于vector的主要方式是,deque还支持在序列开始时对元素进行恒定时间的插入和移除。此外,deque没有任何类似于vector的capacity()和reserve()的成员函数,也没有提供与这些成员函数相关联的迭代器有效性的任何保证。

下面是关于这个问题的总结 list 来自同一站点:

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

std::list

std::deque std::vector

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

• 数据块是一组链接的内存块,其中每个内存块中存储一个以上的元素。

请注意,deque的设计目的是 尝试

否。deque仅支持在前后插入和删除O(1)。例如,它可以在具有环绕的向量中实现。因为它还保证了O(1)随机访问,所以可以确定它没有(仅仅)使用双链接列表。

两者之间的显著差异 deque list

• 对于 德克 :

  并排存放的物品;

  优化用于从两侧(正面、背面)添加数据;

  访问数据的时间更快。

• 对于

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

  只能由迭代器浏览;

  优化插入和去除在中间。

  数据的时间访问速度较慢,迭代速度较慢,因为它的空间位置非常差。

  可以很好地处理大型元素

Link

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

我为我的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实现中称为map)。所有内存块都已满,但第一个内存块开头可能有空间,最后一个内存块结尾可能有空间。地图本身是从中心向外填充的。这就是为什么,与 std::vector ,可在固定时间内完成两端插入。类似于 std:::vector 向量 std::list 在中间删除或插入元素是非常昂贵的,因为必须重新组织数据结构的大部分。

双链表

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

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

这里是一个概念验证代码,使用列表、无序映射,提供O(1)查找和O(1)精确的LRU维护。需要(非擦除的)迭代器才能在擦除操作中生存。计划在一个O(1)任意大的软件管理缓存中使用GPU内存上的CPU指针。向Linux O(1)调度程序点头(每个处理器的LRU<->运行队列)。无序的_映射通过哈希表具有恒定的时间访问。

#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;
}