本文介绍了什么是STL的deque?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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

08-18 14:49