55

一个不同的问题激发了以下想法：

增加容量时是否std::vector<T> 必须移动所有元素？

据我了解，标准行为是底层分配器请求新大小的整个块，然后移动所有旧元素，然后销毁旧元素，然后释放旧内存。

考虑到标准分配器接口，这种行为似乎是唯一可能的正确解决方案。但我想知道，修改分配器以提供一个reallocate(std::size_t)返回 apair<pointer, bool>并可以映射到底层的函数是否有意义realloc()？这样做的好处是，如果操作系统实际上可以扩展分配的内存，那么根本不需要移动。布尔值将指示内存是否已移动。

(std::realloc()可能不是最好的选择，因为如果我们不能扩展，我们不需要复制数据。所以实际上我们宁愿想要类似的东西extend_or_malloc_new()。编辑：也许基于is_pod-trait 的专业化可以让我们使用实际的realloc,包括它的按位复制。只是一般情况下。）

这似乎是一个错失的机会。最坏的情况，你总是可以实现reallocate(size_t n)as return make_pair(allocate(n), true);，所以不会有任何惩罚。

是否有任何问题使此功能不适合或不适合 C++？

也许唯一可以利用这一点的容器是std::vector，但话又说回来，这是一个相当有用的容器。

更新：一个小例子来澄清。当前resize()：

pointer p = alloc.allocate(new_size);

for (size_t i = 0; i != old_size; ++i)
{
  alloc.construct(p + i, T(std::move(buf[i])))
  alloc.destroy(buf[i]);
}
for (size_t i = old_size; i < new_size; ++i)
{
  alloc.construct(p + i, T());
}

alloc.deallocate(buf);
buf = p;

新实现：

pair<pointer, bool> pp = alloc.reallocate(buf, new_size);

if (pp.second) { /* as before */ }
else           { /* only construct new elements */ }
4

3 回答 3

45

当std::vector<T>容量用完时，它必须分配一个新块。你已经正确地解释了原因。

IMO增加分配器接口是有意义的。我们中的两个人尝试使用 C++11，但我们无法获得对它的支持： [1] [2]

我开始确信，为了完成这项工作，需要一个额外的 C 级 API。我也未能获得对此的支持： [3]

于 2011-11-03T23:49:22.043 回答
10

在大多数情况下，realloc不会扩展内存，而是分配一个单独的块并移动内容。最初定义 C++ 时考虑到了这一点，并决定当前接口更简单，并且在常见情况下效率不低。

realloc在现实生活中，能够成长的案例其实很少。在malloc具有不同池大小的任何实现中，新大小（请记住，vector大小必须以几何方式增长）很可能会落入不同的池中。即使在没有从任何内存池分配的大块的情况下，它也只能在更大大小的虚拟地址空闲时才能增长。

请注意，虽然realloc有时可以在不移动的情况下增加内存，但到完成时它可能已经移动（按位移动）内存，并且二进制移动将导致所有非 POD 类型的未定义行为。我不知道任何分配器实现（POSIX、*NIX、Windows），您可以在其中询问系统是否能够增长，但如果它需要移动，那将失败。realloc

于 2011-11-03T23:36:43.647 回答
0

是的，你是对的，标准分配器接口没有为 memcpy'able 类型提供优化。

可以使用 boost 类型特征库来确定一个类型是否可以被 memcpy 使用（不确定他们是开箱即用地提供它，还是必须基于 boost 构建一个复合类型鉴别器）。

无论如何，利用realloc()一个可能会创建一个可以显式利用此优化的新容器类型。使用当前的标准分配器接口，这似乎是不可能的。

于 2011-11-03T23:42:09.263 回答