c++ - 双端队列内存分配可以稀疏吗？

Question

标准是否允许双端队列以稀疏方式分配内存？

我的理解是大多数双端队列的实现在内部以一定大小的 block 分配内存。我相信，虽然我不知道这一点，但实现至少分配了足够的 block 来存储当前大小的所有项目。因此，如果一个 block 是 100 个项目，而您这样做

std::deque<int> foo;
foo.resize( 1010 );

您将获得至少 11 个 block 的分配。但是鉴于上面所有 1010 int 都是默认构造的，您真的需要在调整大小调用时分配 block 吗？您能否改为仅在有人以某种方式实际插入项目时才分配给定的 block 。例如，实现可以将一个 block 标记为“所有默认构造”并且在有人使用它之前不分配它。

我问，因为我有一种情况，我可能想要一个非常大的双端队列，就我最终使用的元素而言可能非常稀疏。显然我可以使用其他数据结构，例如 map，但我对双端队列的规则很感兴趣。

给定 resize void resize ( size_type sz, T c = T() ); 签名的一个相关问题是标准是否要求默认构造函数被准确调用 sz次？如果答案是肯定的，那么我猜你至少不能对具有非平凡默认构造函数的类型进行稀疏分配，尽管大概它仍然可能用于 int 或 double 等内置类型。

Answer 1

deque 中的所有元素都必须正确构造。如果你需要 一个稀疏的实现，我会建议一个deque(或一个vector)来 指针或 Maybe 类(你真的应该在你的工具箱中有一个 无论如何)在它有效之前不会构造类型。这不是 deque的作用。