c++ - std::deque 的内存开销是怎么回事？

Question

我正在研究一种使用 std::queue 的外部排序算法，并且必须仔细限制其内存使用量。我注意到在合并阶段(使用几个固定长度的 std::queues)，我的内存使用量增加到我预期的大约 2.5 倍。由于 std::queue 默认使用 std::deque 作为其底层容器，我在 std::deque 上运行了一些测试以确定它的内存开销。以下是在 VC++ 9 上运行的结果，在 Release模式下，使用 64 位进程:

当向 std::deque 添加 100,000,000 个 char 时，内存使用量增长到 252,216K。请注意，100M chars(1 字节)应该占用 97,656K，所以这是 154,560K 的开销。

我用 doubles(8 字节)重复测试，发现内存增长到 1,976,676K，而 100M doubles 应该占用 781,250K，开销为 1,195,426克!!

现在我了解到 std::deque 通常实现为“ block ”的链表。如果这是真的，那么为什么开销与元素大小成正比(因为指针大小当然应该固定为 8 个字节)？为什么它这么大？

谁能解释一下为什么 std::deque 使用了这么多危险的内存？我想我应该将我的 std::queue 底层容器切换到 std::vector 因为没有开销(假设适当的大小是 reserve编辑)。我认为 std::deque 的好处在很大程度上被它具有如此巨大的开销(导致缓存未命中、页面错误等)以及复制成本所抵消。 std::vector 元素可能会更少，因为整体内存使用量要低得多。这只是微软对 std::deque 的错误实现吗？

Answer 1

查看 _DEQUESIZ(每个 block 的元素数)的代码:

#define _DEQUESIZ   (sizeof (_Ty) <= 1 ? 16 \
    : sizeof (_Ty) <= 2 ? 8 \
    : sizeof (_Ty) <= 4 ? 4 \
    : sizeof (_Ty) <= 8 ? 2 : 1)    /* elements per block (a power of 2) */

如果元素更大，它会变得更小。只有大于 8 字节的元素才会获得预期的行为(开销随着元素大小的增加而减少百分比)。