STL 中的双端队列到底是什么?

我正在查看 STL 容器并试图弄清楚它们到底是什么(即使用的数据结构)，deque 阻止了我:我一开始以为它是一个双链表，这将允许在恒定时间内从两端插入和删除，但我对

在 vector 的比较进行了很好的分析Depth-Study-of-the-STL-Deque-Container" rel="noreferrer">CodeProject.

GCC 标准库实现内部使用一个 T** 来表示地图.每个数据块都是一个T*，它被分配了一些固定大小的__deque_buf_size(取决于sizeof(T)).

I was looking at STL containers and trying to figure what they really are (i.e. the data structure used), and the deque stopped me: I thought at first that it was a double linked list, which would allow insertion and deletion from both ends in constant time, but I am troubled by the promise made by the operator [] to be done in constant time. In a linked list, arbitrary access should be O(n), right?

And if it's a dynamic array, how can it add elements in constant time? It should be mentioned that reallocation may happen, and that O(1) is an amortized cost, like for a vector.

So I wonder what is this structure that allows arbitrary access in constant time, and at the same time never needs to be moved to a new bigger place.

解决方案

A deque is somewhat recursively defined: internally it maintains a double-ended queue of chunks of fixed size. Each chunk is a vector, and the queue ("map" in the graphic below) of chunks itself is also a vector.

There’s a great analysis of the performance characteristics and how it compares to the vector over at CodeProject.

The GCC standard library implementation internally uses a T** to represent the map. Each data block is a T* which is allocated with some fixed size __deque_buf_size (which depends on sizeof(T)).