STL deque是作为循环链表实现的

本文关键字：循环链表 实现 deque STL | 更新日期: 2023-09-27 17:48:59

我无法找到deque在c++ STL中如何实现的内部信息。

我以前在某个地方读到过，在c#中它是作为循环列表实现的。c++ STL也是这样吗?另外，你能解释一下为什么会这样吗?

编辑:这里的c++ STL，我指的是Visual studio c++ 2010附带的STL库，以及gcc附带的STL库

STL deque是作为循环链表实现的

No。它的实现方式有一些变化，但循环链表肯定不符合的条件。

在大多数实现中(包括vc++和可能的gcc)，它基本上是一个指向数据块的指针数组。当您添加数据时，它通常只是将其添加到现有的数据块中。当现有块填满时，它会分配一个新的块，将其添加到您正在插入的数组的末尾，然后将数据添加到其中。

当/如果基本数组的空间用完，它分配一个新的空间，并将指针复制到那里。

c++标准要求deque具有恒定的随机查找时间。循环链表不符合要求。

STL是规范，而不是实现。规范没有要求如何实现行为(只要它遵守定义的接口)。

deque的实现必须提供

  1. 对其元素的常数时间随机访问
  2. 恒时末端插入和移除
  3. 起始恒时插入和移除

(1)排除任何类型的链表，包括循环链表

(2),(3)排除存储元素的简单内存块。

注意:现行标准('03)实际上说的是常数时间而不是平摊常数时间对于(2)&(3)(见23.2.1/1)，但我认为这是一个疏忽。我不知道如何在常数时间中完成这三个。如果(1)只有常数时间，(2)和(3)只有平摊常数时间，那么就很容易了。

MSVC deque使用指向元素页的指针的环缓冲区。可以把环形缓冲区看作一个带有偏移量+环绕的数组(vector)。一个页面包含少量元素(IIRC不超过8个)，这取决于sizeof(element)。如果需要更多的空间，环缓冲区就像std::vector一样增长(这就是您需要平摊常数时间而不是常数时间的地方)。

我认为其他实现(GCC，…)将非常相似。

BTW:在标准中还有一个子句，使得不可能只使用一个大的元素环缓冲区，而不使用"指针索引"。23.2.1.3/1表示在开头或结尾插入不会使对deque中元素的引用无效。显然，如果保存元素本身的结构在超出保留空间时必须重新分配，则这是不可能的。普通的环形缓冲区需要这样做，因此不能使用。

相关文章：