What really is a deque in STL?(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)
).
这篇关于STL 中的双端队列到底是什么?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持编程学习网!
本文标题为:STL 中的双端队列到底是什么?
基础教程推荐
- 为 C/C++ 中的项目的 makefile 生成依赖项 2022-01-01
- 在 C++ 中循环遍历所有 Lua 全局变量 2021-01-01
- 使用从字符串中提取的参数调用函数 2022-01-01
- 从 std::cin 读取密码 2021-01-01
- 如何“在 Finder 中显示"或“在资源管理器中显 2021-01-01
- 管理共享内存应该分配多少内存?(助推) 2022-12-07
- Windows Media Foundation 录制音频 2021-01-01
- 如何在不破坏 vtbl 的情况下做相当于 memset(this, ...) 的操作? 2022-01-01
- 为什么语句不能出现在命名空间范围内? 2021-01-01
- 如何使图像调整大小以在 Qt 中缩放? 2021-01-01