12

我将如何有效地调整使用某些符合标准的 C++ 分配器分配的数组的大小？我知道 C++ 分配器接口中没有提供重新分配的工具，但是 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而不必经历所有这些？如果您认为它有用，我可以提供一个实际的代码示例，但我觉得这里没有必要。

4

6 回答 6

4

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

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

还有一个内存效率低下的问题，即给定 n 个元素，我们总是保留 p - n % p 个元素。即我们只分配或取消分配完整的页面。这是我在需要重新调整大小和快速访问的大型阵列的情况下能想到的最佳解决方案，但我不怀疑有更好的解决方案我很乐意看到它们。

于 2012-01-12T08:34:11.310 回答
1

x.size() > this->size()如果在 中也会出现类似的问题foo& operator=(foo&& x)。

不，它没有。你只是swap。

于 2012-01-12T03:02:02.350 回答
1

没有函数可以就地调整大小或0在失败时返回（调整大小）。除了告诉您特定分配的实际大小之外，我不知道有任何操作系统支持这种功能。

然而，所有操作系统都支持实现realloc，但是，如果它不能适当地调整大小，它会执行一个副本。

所以，你不能拥有它，因为如果你必须添加一个标准函数来实现它，C++ 语言将无法在大多数当前操作系统上实现。

于 2012-01-12T21:44:03.330 回答
0

有C++11 右值引用和移动构造函数。

有一个关于他们的精彩视频谈话。

于 2012-01-12T03:36:38.277 回答
0

实际上，即使存在重新分配，您也只能避免在复制构造函数中的问题中提到的#2。但是在内部缓冲区增长的情况下，重新分配可以节省这四个操作。

  1. 您的阵列的内部缓冲区是否连续？如果是这样，请参阅您的链接的答案
  2. 如果没有，散列数组树或数组列表可能是您避免重新分配的选择。
于 2012-01-12T09:18:39.270 回答
0

有趣的是，g++ 的默认分配器足够聪明，只要在最初分配的缓冲区结束后有足够的未使用空间，就可以将相同的地址用于连续释放和更大尺寸的分配。虽然我还没有测试我要声明的内容，但我怀疑 malloc/realloc 和 allocate/deallocate/allocate 之间存在很大的时间差异。

这会导致一个潜在的非常危险的非标准快捷方式，如果您知道当前缓冲区之后有足够的空间以便重新分配不会导致新地址，则该快捷方式可能会起作用。(1) 不调用 alloc.destroy() 释放当前缓冲区 (2) 分配一个新的更大的缓冲区并检查返回的地址 (3) 如果新地址等于旧地址，则愉快地继续；否则，您将丢失数据 (4) 为新分配空间中的元素调用 allocator.construct()。

除了满足您自己的好奇心之外，我不提倡将它用于任何其他用途，但它确实适用于 g++ 4.6。

于 2012-01-12T10:00:11.147 回答