为什么std :: deque不允许指定存储桶大小?

And*_*hko 18 c++ stddeque

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

  • MSVC:16个字节或元素大小(如果更大)
  • GCC:512字节或元素大小(如果更大)
  • 铛: element_size < 256 ? 4096 : element_size * 16

对于MSVC(尤其是MSVC)和GCC,如果双端队列元素的大小大于硬编码的大小,std::dequestd::list在大多数情况下会导致性能下降。

我认为Clang的效果更好,无论双端队列元素的大小如何,存储桶至少应包含16个元素。尽管在某些情况下,对于小元素,最小的bucket大小4096字节可能不是最佳的。

为什么没有std::deque用于存储桶大小的附加模板参数,其默认值是供应商认为合理的值?这不会破坏向后兼容性,但可以优化性能。

L. *_* F. 10

deque就像一个黑匣子。没有指定如何实现。该实现可以自由使用它喜欢的任何符合性能要求的技术。因此,它不能将存储桶大小作为模板参数。

当然,这种数据结构是有用的。该标准可以选择提供(以名称deque或作为新容器提供),但没有提供。相反,unordered_*保证容器使用桶。根据[unord.req] / 9

无序关联容器的元素被组织到 存储桶中。具有相同哈希码的键将出现在同一存储桶中。当将元素添加到无序关联容器中时,存储桶的数量会自动增加,从而使每个存储桶的平均元素数量保持在界限以下。重新散列会使迭代器无效,更改元素之间的顺序以及更改出现在存储桶中的元素,但不会使对元素的指针或引用无效。对于unordered_­multisetunordered_­multimap,重新哈希保留了等效元素的相对顺序。

deque 没有类似的措词。

  • 因此,换句话说,因为“std::deque”不是在缓存一致性成为实际性能中压倒性最大因素的时候编写的。:( (2认同)