C++中的高效数组重新分配

Question

如何有效地调整使用符合标准的C++分配器分配的数组的大小？我知道在C++ alloctor界面中没有提供重新分配的工具,但是C++ 11版本是否使我们能够更容易地使用它们？假设我有一个定义vec了复制赋值运算符的类foo& operator=(const foo& x).如果x.size() > this->size(),我被迫

1. 在内部存储的所有元素上调用allocator.destroy()foo.
2. 在内部存储上调用allocator.deallocate() foo.
3. 重新分配一个具有足够空间的新缓冲区x.size().
4. 使用std :: uninitialized_copy填充存储.

有没有什么方法可以让我更轻松地重新分配内部存储而foo无需经历所有这些？如果您认为它有用,我可以提供一个实际的代码示例,但我觉得这里没有必要.

Answer 1

基于前面的问题，我处理可以以合理效率增长和收缩的大型数组的方法是编写一个类似于双端队列的容器，将数组分解为多个较小数组的页面。例如，假设我们有一个包含 n 个元素的数组，我们选择页面大小 p，并创建 p 个元素的 1 + n/p 数组（页面）。当我们想要重新分配和增长时，我们只需将现有页面保留在原处，然后分配新页面即可。当我们想要缩小时，我们释放完全空白的页面。

缺点是数组访问稍慢，在给定索引 i 的情况下，您需要 page = i / p 以及页 i % p 的偏移量才能获取元素。我发现这仍然非常快，并且提供了一个很好的解决方案。从理论上讲， std::deque 应该做一些非常相似的事情，但对于我尝试使用大型数组的情况来说，它非常慢。有关更多详细信息，请参阅链接问题的评论和注释。

给定 n 个元素，我们总是保留 p - n % p 个元素作为保留，这也存在内存效率低下的问题。即我们只分配或释放完整的页面。这是我在需要重新调整大小和快速访问的大型数组的背景下提出的最佳解决方案，同时我毫不怀疑有更好的解决方案，我希望看到它们。