Deque - 为什么“reserve”不存在？

Question

标准 STL 向量容器具有“保留”功能，用于保留未初始化的内存，以便稍后使用以防止重新分配。

为什么其他双端队列容器没有？

Answer 1

增加

std::vector

的容量可能成本高昂。当

vector

超出其保留空间时，必须将向量的全部内容复制（或移动）到更大的保留空间。

正是因为 std::vector 调整大小的成本可能很高，所以存在

vector::reserve()

。

reserve()

可以准备一个

std::vector

来预期达到一定的大小而不超过其容量。

相反，

deque

始终可以添加更多内存，无需重新定位现有元素。如果有 std::deque可以 reserve()

 记忆，那么几乎没有任何明显的好处。

Answer 2

对于

vector

 和 

string

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

使用

deque

 和 

list

，较早的引用永远不会因末尾的插入而失效，并且元素不会移动，因此不会出现预留容量的需要。

您可能会认为，使用

vector

 和 

string

 ，保留空间还可以保证以后的插入不会抛出异常（除非构造函数抛出），因为不需要分配内存。您可能认为相同的保证对于其他序列也有用，因此 

deque::reserve

 会有可能的用途。 

事实上，vector和

string

没有这样的保证

，尽管在大多数（所有？）实现中这是正确的。所以这不是

reserve

的预期目的。

Answer 3

引自

C++参考

与 std::vector 不同，双端队列的元素不是连续存储的：典型的实现使用一系列单独分配的固定大小数组。

双端队列的存储会根据需要自动扩展和收缩。
双端队列的扩展比 std::vector 的扩展更便宜，因为它不涉及将现有元素复制到新的内存位置。

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

Answer 4

只有

vector

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

Answer 5

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

因此，“储备”功能没有任何意义。

Answer 6

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

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.

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