我正在研究 STL 容器并试图弄清楚它们到底是什么（即使用的数据结构），以及deque阻止了我：我一开始以为这是一个双链表，可以在常数时间内从两端插入和删除，但我很困扰做出的承诺 http://en.cppreference.com/w/cpp/container/deque/operator_at由运算符 [] 在常数时间内完成。在链表中，任意访问应该是O(n)，对吧？
如果是动态数组，那又如何呢？添加元素 http://en.cppreference.com/w/cpp/container/deque/push_back在恒定时间内？需要提到的是，可能会发生重新分配，并且 O(1) 是摊余成本，就像向量一样 http://en.cppreference.com/w/cpp/container/vector/push_back.
所以我想知道这个结构是什么，它允许在恒定时间内任意访问，同时永远不需要移动到新的更大的地方。
双端队列在某种程度上是递归定义的：在内部它维护一个双端队列chunks固定大小的。每个块都是一个向量，块的队列（下图中的“映射”）本身也是一个向量。
对性能特征及其与其他产品的比较进行了深入分析vector于代码项目 https://www.codeproject.com/Articles/5425/An-In-Depth-Study-of-the-STL-Deque-Container.
GCC 标准库实现内部使用T**来表示地图。每个数据块是一个T*分配了一些固定大小__deque_buf_size（这取决于sizeof(T)).
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
