c++ - 双端队列 - 为什么“储备”不存在？

Question

标准的 STL 向量容器有一个“保留”功能来保留未初始化的内存，以后可以使用它来防止重新分配。

为什么另一个双端队列容器没有呢？

Answer 1

增加 a 的大小std::vector可能代价高昂。当 avector超出其保留空间时，必须将向量的全部内容复制（或移动）到更大的保留空间。

特别是因为std::vector 调整大小的成本可能vector::reserve()很高。 reserve()可以准备一个std::vector预期达到一定大小而不超出其容量。

相反，adeque总是可以添加更多内存而无需重新定位现有元素。如果std::deque 可以 reserve()记忆，那么几乎没有明显的好处。

Answer 2

对于vectorand string，保留空间通过确保不需要复制/移动元素来防止后面的插入（直到容量）使迭代器和对早期元素的引用无效。这种搬迁也可能代价高昂。

使用dequeand list，早期的引用永远不会因末尾的插入而无效，并且元素不会移动，因此不会出现保留容量的需要。

您可能认为使用vectorand string，保留空间还可以保证以后的插入不会抛出异常（除非构造函数抛出），因为不需要分配内存。您可能认为相同的保证对其他序列有用，因此deque::reserve可能会有用处。实际上并没有这样的保证and vector，string尽管在大多数（全部？）实现中它是正确的。所以这不是reserve.

Answer 3

引用C++ 参考

与 std::vector 不同，双端队列的元素不是连续存储的：典型的实现使用一系列单独分配的固定大小数组。
双端队列的存储会根据需要自动扩展和收缩。deque 的扩展比 std::vector 的扩展便宜，因为它不涉及将现有元素复制到新的内存位置。

Deque 可以在任何它想要的地方分配新内存并指向它，这与需要连续内存块来保存所有元素的向量不同。

Answer 4

只vector拥有。双端队列不需要保留功能，因为元素不是连续存储的，并且在添加或删除元素时不需要重新分配和移动元素。

Answer 5

保留意味着分配大块连续数据（如向量）。出队中没有任何内容意味着连续存储 - 它通常更像是一个列表（您会注意到它也没有“保留”功能）。

因此，“储备”功能毫无意义。

Answer 6

有两种主要类型的内存：分配单个块的内存，如数组和向量，以及成员抓取任何空位置来填充的分布式内存。队列和链接列表结构属于第二种类型，它们具有一些特殊的实际优势，例如与数组和向量相反，删除特定元素不会导致大量内存移动。因此他们不需要事先保留任何空间，如果他们需要它，他们只需连接到小费即可

Answer 7

如果你的目标是对齐内存容器，你可以考虑实现这样的东西：

std::deque<std::vector> dv; //deque with dynamic size memory aligned vectors.

typedef size_t[N] Mem;
std::deque<Mem> dvf //deque with fixed size memory aligned vectors. Here you can store the raw bytes adding a header to loop through and cast using header information and typeid... 
//templates and polymorphism can help storing raw bytes, checking the type where a pointer points for example, and creating an interface to access the partial aligned memory.

或者，您可以使用地图而不是双端队列来访问向量...