std :: vector*在增加容量时是否有*移动对象？或者,分配器可以"重新分配"吗？

Question

一个不同的问题启发了以下思想:

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

据我所知,标准行为是底层分配器请求新大小的整个块,然后移动所有旧元素,然后销毁旧元素,然后解除分配旧内存.

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

(std::realloc()也许不是最好的选择,因为如果我们不能扩展,我们不需要复制数据.所以实际上我们更想要类似的东西extend_or_malloc_new().编辑:也许is_pod基于特征的专业化将允许我们使用实际的realloc,包括它的按位副本.只是不一般.)

这似乎错过了机会.最坏的情况下,可以始终贯彻reallocate(size_t n)的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 */ }

Answer 1

当std::vector<T>用完容量时,它必须分配一个新块.你已经正确地说明了原因.

IMO它会是有意义的增加分配器接口.我们两个人试图使用C++ 11而我们无法获得支持: [1] [2]

我开始相信,为了使这项工作,需要一个额外的C级API.我也未能获得支持: [3]

Answer 2

在大多数情况下,realloc不会扩展内存,而是分配一个单独的块并移动内容.在首先定义C++时考虑了这一点,并且在常见情况下确定当前接口更简单且效率不高.

在现实生活中,实际上很少realloc有能够成长的案例.在malloc具有不同池大小的任何实现中,新大小(记住vector大小必须几何增长)可能落在不同的池中.即使在没有从任何内存池分配的大块的情况下,如果较大的虚拟地址是空闲的,它也只能增长.

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