std::deque将元素存储在固定大小的“存储桶”(数组)中。不同的编译器使用不同的存储桶大小:
element_size < 256 ? 4096 : element_size * 16对于MSVC(尤其是MSVC)和GCC,如果双端队列元素的大小大于硬编码的大小,std::deque则std::list在大多数情况下会导致性能下降。
我认为Clang的效果更好,无论双端队列元素的大小如何,存储桶至少应包含16个元素。尽管在某些情况下,对于小元素,最小的bucket大小4096字节可能不是最佳的。
为什么没有std::deque用于存储桶大小的附加模板参数,其默认值是供应商认为合理的值?这不会破坏向后兼容性,但可以优化性能。
L. *_* F. 10
deque就像一个黑匣子。没有指定如何实现。该实现可以自由使用它喜欢的任何符合性能要求的技术。因此,它不能将存储桶大小作为模板参数。
当然,这种数据结构是有用的。该标准可以选择提供(以名称deque或作为新容器提供),但没有提供。相反,unordered_*保证容器使用桶。根据[unord.req] / 9:
无序关联容器的元素被组织到 存储桶中。具有相同哈希码的键将出现在同一存储桶中。当将元素添加到无序关联容器中时,存储桶的数量会自动增加,从而使每个存储桶的平均元素数量保持在界限以下。重新散列会使迭代器无效,更改元素之间的顺序以及更改出现在存储桶中的元素,但不会使对元素的指针或引用无效。对于
unordered_multiset和unordered_multimap,重新哈希保留了等效元素的相对顺序。
deque 没有类似的措词。