增加容量时 std::vector *必须* 移动对象吗?或者，分配器可以“重新分配"吗? [英] Does std::vector *have* to move objects when growing capacity? Or, can allocators "reallocate"?

问题描述

A 不同的问题激发了以下想法:

std::vector 是否必须在增加容量时移动所有元素?

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

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

(std::realloc() 可能不是最好的选择，因为如果我们不能扩展，我们不需要复制数据.所以实际上我们更想要像 extend_or_malloc_new().也许基于 is_pod-trait 的特化将允许我们使用实际的 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;

新实现:

pairpp = alloc.reallocate(buf, new_size);if (pp.second) {/* 和以前一样 */}else {/* 只构造新元素 */}

解决方案

当 std::vector 耗尽容量时，它必须分配一个新块.您已经正确地说明了原因.

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

我确信为了使这项工作能够正常工作，需要一个额外的 C 级 API.我也未能获得支持:[3]

A different question inspired the following thought:

Does std::vector<T> have to move all the elements when it increases its capacity?

As far as I understand, the standard behaviour is for the underlying allocator to request an entire chunk of the new size, then move all the old elements over, then destroy the old elements and then deallocate the old memory.

This behaviour appears to be the only possible correct solution given the standard allocator interface. But I was wondering, would it make sense to amend the allocator to offer a reallocate(std::size_t) function which would return a pair<pointer, bool> and could map to the underlying realloc()? The advantage of this would be that in the event that the OS can actually just extend the allocated memory, then no moving would have to happen at all. The boolean would indicate whether the memory has moved.

(std::realloc() is maybe not the best choice, because we don't need do copy data if we cannot extend. So in fact we'd rather want something like extend_or_malloc_new(). Edit: Perhaps a is_pod-trait-based specialization would allow us to use the actual realloc, including its bitwise copy. Just not in general.)

It seems like a missed opportunity. Worst case, you could always implement reallocate(size_t n) as return make_pair(allocate(n), true);, so there wouldn't be any penalty.

Is there any problem that makes this feature inappropriate or undesirable for C++?

Perhaps the only container that could take advantage of this is std::vector, but then again that's a fairly useful container.

---

Update: A little example to clarify. Current 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;

New implementation:

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

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

解决方案

When std::vector<T> runs out of capacity it has to allocate a new block. You have correctly covered the reasons.

IMO it would make sense to augment the allocator interface. Two of us tried to for C++11 and we were unable to gain support for it: [1] [2]

I became convinced that in order to make this work, an additional C-level API would be needed. I failed in gaining support for that as well: [3]

这篇关于增加容量时 std::vector *必须* 移动对象吗?或者，分配器可以“重新分配"吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！