STL内部:deque实现

Question

我使用std :: deque来存储大量的项目.
我知道deques是作为矢量列表实现的.这些矢量的大小无法设置,但我喜欢选择该大小的算法.

Answer 1

deque被实现为向量向量(向量列表将阻碍恒定时间随机访问).辅助向量的大小取决于实现,常见的算法是使用以字节为单位的常量大小.

原始SGI实现使用了512.根据Mike对您的问题的评论,G ++仍在使用它.我不是一个关于VC++的可靠来源 - 关于我所知道的一切都是在像这样的公共论坛上说的,我不记得有人提到这个琐事. (4认同)
这个恒定大小有多大？(例如在视觉工作室实施中) (3认同)
上次我在VC++(2010)中钻研时,它有点像8或16字节(如果更大则是单个对象).然后我理解了`deque`在VC++中的表现如此糟糕...... (3认同)
这些载体向量如何保证开始时的恒定时间插入？ (3认同)
@Calmarius：在前面进行插入所需的工作量仅取决于第一个子向量的大小，而不取决于容器中元素的总数。就“N”而言，它是恒定的。如果“N”是 10 亿，第一个容器仍然只有 50 或 100 个元素（或实现选择的任何一个）。如果“N”是 5 万亿，那么_不会_花费 5,000 倍的时间。另外，如果第一个子向量的大小在它变得太大时通过分割来保持“或多或少恒定”，那么它对于该子向量的“N”也是“摊销常数”。 (2认同)