STL 内核：双端队列实现

Question

我正在使用一个std::deque来存储大量的元素。
我知道deques是以向量列表的形式实现的。这些向量的大小无法设置，但我想知道选择该大小的算法。

- cprogrammer

---

哪个实现？STL和C++标准库规定接口，而不是实现。 - Lightness Races in Orbit

在GNU库的情况下（至少到gcc 4.4.5），大小为512字节，没有算法：“'512'是可调的，但自从继承SGI代码以来还没有进行过任何调查。” - Mike Seymour

Answer 1

deque被实现为向量的向量（列表会妨碍常数时间的随机访问）。辅助向量的大小取决于实现，一种常见的算法是使用固定大小的字节。

- AProgrammer

---

那个常量大小有多大？（例如在Visual Studio实现中） - cprogrammer

原始的 SGI 实现使用了 512。根据 Mike 对你问题的评论，G++ 仍在使用它。关于 VC++ 我不是一个可靠的消息来源——我所知道的一切都是从像这个公共论坛这样的地方说出来的，我不记得有人提到过那个琐事。 - AProgrammer

上次我深入研究 VC++（2010）时，它的一个小细节是分配内存块的大小为8或16字节（或者如果更大，则为单个对象）。然后我明白了为什么在 VC++ 中 deque 的性能表现如此糟糕... - Matthieu M.

这些向量的向量如何保证在开头插入时具有恒定的时间复杂度？ - Calmarius

@Calmarius：在容器前面插入元素所需的工作量仅取决于第一个子向量的大小，而不是容器中元素的总数。因此，它相对于 N 是恒定的。如果 N 是十亿，第一个容器仍然只有大约50或100个元素（或者实现选择的任何数量）。如果 N 是5万亿，则不需要花费5000倍的时间。此外，如果通过将其分割为过大时保持第一个子向量的大小“更或多或少恒定”，则相对于该子向量的 N 也是“平摊常数”。 - Damon

Answer 2

我的deque实现是来自GNU的，它源于HP/SGI版本，不是std::list的std::vector列表。注释中说明：

*  In previous HP/SGI versions of deque, there was an extra template
*  parameter so users could control the node size.  This extension turned
*  out to violate the C++ standard (it can be detected using template
*  template parameters), and it was removed.
*
*  Here's how a deque<Tp> manages memory.  Each deque has 4 members:
*
*  - Tp**        _M_map
*  - size_t      _M_map_size
*  - iterator    _M_start, _M_finish
*
*  map_size is at least 8.  %map is an array of map_size
*  pointers-to-"nodes".  (The name %map has nothing to do with the
*  std::map class, and "nodes" should not be confused with
*  std::list's usage of "node".)

- Fred Foo

---

它调整大小（按照标准要求），并指向节点而不是在内联中保存它们-因此它根本不像数组的数组-相反，它类似于指向数组分配的向量。 - Karl Knechtel

系统头文件需要使用保留名称来表示其实现细节，以避免与在包含该头文件之前定义的任何宏发生冲突。 - Mike Seymour

@MikeSeymour 当然，仅仅因为名称需要被“丑化”，并不意味着它们也需要毫无意义或具有误导性。我对MS STL也有同样的抱怨。“_Eep_Ds”？真的吗？ - Sebastian Redl