什么是STL的deque？ [英] What really is a deque in STL?

问题描述

我正在查看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？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！