c++ - 为什么 std::deque 不允许指定桶大小？

Question

std::deque将元素存储在固定大小的“桶”（数组）中。不同的编译器使用不同的桶大小：

• MSVC：16 字节或元素大小（如果更大）
• GCC：512 字节或元素大小（如果更大）
• 铛：element_size < 256 ? 4096 : element_size * 16

对于 MSVC（尤其是）和 GCC，如果双端队列元素大小大于硬编码大小，在大多数情况下std::deque会变成一个复杂的性能损失。std::list

在我看来，Clang 做得更好，无论双端队列元素的大小如何，存储桶都至少有 16 个元素。尽管 4096 字节的最小桶大小在某些情况下对于小元素可能不是最佳的。

为什么没有std::deque额外的存储桶大小模板参数，默认值是供应商认为合理的？这不会破坏向后兼容性，但会允许性能优化。

Answer 1

deque就像一个黑匣子。它没有具体说明它是如何实现的。该实现可以自由使用它喜欢的任何技术来满足性能要求。因此，它不能将桶大小作为模板参数。

当然，这样的数据结构是有用的。标准可以选择提供它（以名称deque或作为新容器），但他们没有。相反，unordered_*容器保证使用桶。根据[unord.req]/9：

无序关联容器的元素被组织成 桶。具有相同哈希码的键出现在同一个桶中。随着元素被添加到无序关联容器中，桶的数量会自动增加，因此每个桶的平均元素数保持在一个界限以下。重新散列使迭代器无效、更改元素之间的顺序以及更改哪些桶元素出现在其中，但不会使指针或对元素的引用无效。对于unordered_­multiset和 unordered_­multimap，重新散列保留等效元素的相对顺序。

deque没有类似的措辞。