在STL中真正是一个双层舞台?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (35)

我正在查看STL容器,并试图了解它们的真实情况(即所使用的数据结构),以及德克阻止了我:起初我以为这是一个双链接列表,可以在固定的时间内从两端插入和删除,但我感到不安。由操作员[]在恒定时间内完成。在链接列表中,任意访问应该是O(N),对吗?

如果它是一个动态数组,它怎么能添加元素在固定的时间里?

所以我想知道这个结构是什么,它允许在固定的时间内任意访问,同时也不需要移动到一个新的更大的地方。

提问于
用户回答回答于

deque在某种程度上是递归定义的:在内部,它维护的是(下图中的“块”)固定大小。每个块都是一个向量,块本身的队列(下图中的“map”)也是一个向量。

gcc标准库实现在内部使用T**来代表地图。每个数据块都是T*,它以固定的大小分配。__deque_buf_size(这取决于sizeof(T))。

用户回答回答于

扫码关注云+社区