vector 的复制/移动分配后底层存储会发生什么变化? [英] What happens to the underlying storage upon vector's copy/move assignment?

问题描述

对于 std::vector 的复制分配，当源的大小小于目标的容量时，是否允许重新分配存储和缩小容量?或者是否保证不会发生重新分配/收缩(即始终尊重之前的 Reserve())?

For std::vector's copy assignment, is reallocation of storage and shrink of capacity allowed when the source's size is smaller than the destination's capacity? Or is it guaranteed that the reallocation/shrink will not happen (i.e. always respect previous reserve())?

另一方面，如果源的大小大于目标的容量并且发生重新分配，是否需要重新分配尊重源的容量(例如，目标的新容量不应小于源的容量，或甚至要求它们相同)?或者重新分配只是完成它的工作(基于新的大小)而不考虑源的容量?

On the other side, if the source's size is bigger than the destination's capacity and a reallocation takes place, is it required that the reallocation respect the source's capacity (e.g. the destination's new capacity should be no smaller than the source's capacity, or even require them to be the same)? Or the reallocation simply does its job (based on the new size) with no regard to the source's capacity?

至于移动分配，我认为不会发生存储重新分配(虽然我没有在标准中找到相关部分)，所以这是否意味着目的地的新容量的值将与源的旧容量完全相同?我可以期望 v = vector{}; 与 vector{}.swap(v); 具有相同的效果吗?

As for move assignment, I suppose no storage reallocation will take place (though I failed to locate relevant part in the standard), so does it mean the value of the destination's new capacity will be exactly the same to the source's old capacity? Can I expect v = vector<T>{}; to have the same effect as vector<T>{}.swap(v);?

我想答案隐藏在标准中的某个地方，但我没能找到它们.(如果 C++11 和 C++03 的情况不同，我想知道两者的各种要求.)

I suppose the answers are buried somewhere in the standard, but I just failed to find them. (In case things are different for C++11 and C++03, I would like to know various requirements from both.)

PS:对于上述问题的任何答案，std::string 是否相同(仅在 C++11 中，这意味着连续存储且没有 COW，C++03 字符串不在雷达范围内)?

PS: For whatever answer of the above questions, is it the same for std::string (only in C++11 which means contiguous storage and no COW, C++03 string is out of the radar)?

推荐答案

std::vector<T,A>( std::vector<T,A>&& )

这保证是恒定时间(N3797 表 99 X u(rv)).

this is guaranteed to be constant time (N3797 Table 99 X u(rv)).

我没有办法在恒定时间内移动任意大小的向量而不只是将指针移动到缓冲区.如果这(不可能)为真，则构造的向量必须具有至少与源缓冲区一样大的缓冲区.标准中没有说明 vector 需要高效，但是:右侧 vector 的容量可以减少到任何大于或等于其容量的值size:后置条件只是元素相同.理论上，如果右侧vector 具有隐藏容量"，编译器会出于任何原因(例如，月相)选择公开该容量，那么理论上它甚至可能具有更大的容量.

There is no way known to myself to move an arbitrary sized vector in constant time without just moving the pointers to the buffer. If this (there is no way) is true, then the constructed vector must have a buffer at least as larger as the source buffer. There is no wording in the standard that states vectors need be efficient, however: the right hand side vector can have its capacity reduced to any value greater than or equal to its size: the postcondition is only that the elements are the same. In theory it could even be larger capacity, if the right hand side vector had "hidden capacity" that the compiler chose to expose for whatever reason (the phase of the moon, say).

N3797 标准中的任何一点都没有对放置在任何容器上的容量 设置上限.一个符合要求的实现可以让所有 std::vectors 至少有 200 万个元素容量(除非 allocator 失败——这可以用来强制 的容量0)，没有任何操作能够将该值降低到 200 万以下.(shr​​ink_to_fit 只是一个建议，std::vector().swap(x) 可以创建一个 vector200 万容量并交换.

At no point in the N3797 standard is an upper bound on capacity placed on any container. A conforming implementation can have all std::vectors have a minimum 2 million element capacity (barring allocator failure -- which could be used to force a capacity of 0), with no operation capable of reducing that value below 2 million. (shrink_to_fit is just a suggestion, and std::vector<T,A>().swap(x) could create a vector of 2 million capacity and swap it.

由于上面的大部分内容都是否定形式，我只能说是搜索标准中的每一个提及vector、allocator、allocate和<代码>容量.容量 从来没有在任何时候用上限来描述.在空的 std::vector 构造函数中(如果 allocator失败，您可能必须保持大小为 0 和容量为 0，但是将该状态提取到不使用相同 allocator 的任何内容是具有挑战性的).

As much of the above is of a negative form, all I can say is search the standard for every mention of vector, allocator, allocate, and capacity. capacity is never described with an upper bound at any point. No restrictions (other than exception-safety) are made against extra calls to the allocator in an empty std::vector constructor (if the allocator failed, you might have to stay size 0 and capacity 0, but extracting that state to anything that doesn't use the same allocator is challenging).

对于复制分配和移动分配，复制分配不保证超出最基本的容量(capacity() >= size()).

As for copy assignment and move assignment, the copy assignment places no guarantees on capacity beyond the most basic (that capacity() >= size()).

对于移动分配，这取决于如何应用:

For move-assignment, it depends on how this applies:

23.2.1 [container.requirements.general]/10

除非另有说明(显式或根据其他函数定义一个函数)，调用一个容器成员函数或将容器作为参数传递给库函数不应失效迭代器或更改该容器内对象的值.

Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container.

a = rv(又名 std::vector& operator=(std::vector&&)) 表 96 和表 99 中的案例是我们所关心的.既没有提到 rv 中包含的值被销毁，也没有提到它们的迭代器无效.因此，在 23.2.1/10 下，迭代器不会失效.

a = rv (aka std::vector<T,A>& operator=(std::vector<T,A>&&)) case from Table 96 and Table 99 are what concern us. Neither mention that the values contained in rv are destroyed, nor that iterators to them are invalidated. As such, under 23.2.1/10 the iterators are not invalidated.

然而，这并不要求移动缓冲区.缓冲区要么从rhs 移到lhs，要么在rhs vector 中保持不变.表 99 当它说 lhs 项可以被移动赋值时隐含地提到了这种情况(这是 std::array 可以工作的唯一方式).

This does not, however, demand that the buffer be moved. Either the buffer is moved from the rhs to the lhs, or it remains intact in the rhs vector. Table 99 mentions that case implicitly when it says that the lhs items can be move-assigned to (which is the only way a std::array can work).

由于 std::array 除了移动元素别无选择，而且 std::vector 没有进一步保证移动缓冲区，缓冲区不必被移动.然而，移动缓冲区似乎是一种合法的实现方式.

As std::array has no choice but to move elements, and std::vector gives no further guarantees about moving the buffer, the buffer does not have to be moved. It appears that moving the buffer is a legal implementation, however.

在实践中，std::vector( std::vector const& ) 会将右侧的内容复制到左侧在每个实现中，我都检查了左侧的 capacity 是否等于结果 vector 的 size.类似地，std::vector(ForwardIterator, ForwardIterator) 将产生一个刚好适合其输入的 vector.

In practice, std::vector<T,A>( std::vector<T,A> const& ) will perform a copy of the contents of the right hand side into the left hand side, and in every implementation I have checked the left hand side's capacity is equal to the size of the resulting vector. Similarly, std::vector<T,A>( ForwardIterator, ForwardIterator ) will produce a vector that just-fits its input.

请注意，std::vector::operator=(std::vector&&) 在复杂性上保持线性.

Note that std::vector<T,A>::operator=(std::vector<T,A>&&) remains linear in complexity.

这篇关于vector 的复制/移动分配后底层存储会发生什么变化?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！