问题描述
我正在查看STL容器,并试图确定他们真正是什么(即使用的数据结构),并且deque 阻止了我:我认为,它是一个双链表,这将允许从两端插入和删除在固定的时间,但我困扰的。
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 ("blocks" in the graphic below) 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)
).
这篇关于什么是STL的deque?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!