STL deque是作为循环链表实现的吗？
我无法找到如何在C ++ STL中实现deque的内部结构。
我之前在某处读过，在C＃中它被实现为循环列表。 它也适用于C ++ STL吗？ 另外，你能解释一下为什么会这样吗？
编辑：由C ++ STL，我的意思是随Visual Studio C ++ 2010一起提供的STL库，以及与gcc一起发布的STL库
不可以 。如何实施它有一些变化，但圆形链表肯定不符合条件。
在大多数实现中（包括VC ++和gcc），它基本上是指向数据块的指针数组。 添加数据时，通常只是将其添加到现有数据块中。 当现有块变满时，它会分配一个新块，将其添加到您要插入的数组的末尾，然后将数据添加到它。 当/如果基本数组空间不足时，它会分配一个新的并在那里复制指针。
C ++标准要求双端队列具有恒定的随机查找时间。 圆形链表不符合要求。
STL是规范，而不是实现。 规范没有要求必须如何实现行为（只要它遵循定义的接口）。
必须提供deque的实现
- 恒定时间随机访问它的元素
- 最后插入和移除恒定时间
- 在开始时插入和移除恒定时间
（1）排除任何类型的链表，包括循环列表
（2）＆（3）排除存储元素的简单内存块。
注意：当前标准（’03）实际上表示恒定时间而不是（2）和（3）的23.2.1/1 常数时间 （见23.2.1/1 ），但我认为这是一个疏忽。 我不知道如何在不变的时间内完成这三项工作。 如果它只是（1）的恒定时间和（2）和（3）的摊销常数时间那么它很容易。
AFAIK MSVC deque使用指向元素页面的指针的环形缓冲区。 将环形缓冲区视为具有偏移量+环绕的数组（ vector ）。 页面包含少量元素（IIRC不超过8个），具体取决于sizeof(element) 。 如果需要更多空间，则环缓冲区就像std::vector一样增长（这是您需要分摊常量时间而不是常量时间 ）。
我认为其他实现（GCC，……）将非常相似。
顺便说一句：标准中还有一个条款，它使得在没有“指针索引”的情况下只能使用一个大的元素环缓冲区。 23.2.1.3/1表示在开头或结尾插入不会使对deque元素的引用无效。 显然，如果保持元素本身的结构在超出保留空间时必须重新分配，则不可能。 普通的环形缓冲区需要这样，因此无法使用。