在 vector 的复制/移动分配下,底层存储会发生什么情况?



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

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

至于移动分配,我想不会进行存储重新分配(尽管我未能在标准中找到相关部分),那么这是否意味着目标新容量的值将与源的旧容量完全相同? 我可以期望v = vector<T>{};具有与vector<T>{}.swap(v);相同的效果吗?

我想答案埋藏在标准的某个地方,但我只是没有找到它们。 (如果 C++11 和 C++03 的情况不同,我想知道两者的各种要求。

PS:无论上述问题如何回答,std::string(仅在C++11中表示连续存储且没有COW,C++03字符串不在雷达范围内)是否相同?

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

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

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

N3797 标准中没有任何一点是放置在任何容器上的capacity上限。 一个符合标准的实现可以让所有std::vector至少有200万个元素的容量(除非allocator失败 - 这可以用来强制0的容量),没有任何操作能够将该值降低到200万以下。 (shrink_to_fit只是一个建议,std::vector<T,A>().swap(x)可以创建一个 200 万容量的vector并交换它。

由于以上大部分都是否定形式,我只能说搜索每次提到vectorallocatorallocatecapacity的标准。capacity从来没有在任何时候用上限来描述。 对空std::vector构造函数中对allocator的额外调用没有任何限制(异常安全除外)(如果allocator失败,则可能必须保持大小 0 和容量 0,但将该状态提取到不使用相同allocator的任何状态具有挑战性)。

对于拷贝分配

和移动分配,拷贝分配不保证容量超出最基本的(即capacity() >= size())。

对于移动分配,这取决于其应用方式:

23.2.1 [容器.要求.一般]/10

除非另有说明(显式或通过根据其他函数定义函数),否则调用 容器成员函数或将容器作为参数传递给库函数不应使无效 迭代器或更改该容器中对象的值。

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

但是,这并不要求移动缓冲区。 缓冲液要么从 rhs 移动到 lhs,要么在 rhsvector中保持完整。 表 99 隐含地提到了这种情况,因为它说 lhs 项目可以移动到(这是std::array工作的唯一方式)。

由于std::array别无选择,只能移动元素,并且std::vector没有进一步保证移动缓冲区,因此不必移动缓冲区。 但是,移动缓冲区似乎是一种合法的实现。


在实践中,std::vector<T,A>( std::vector<T,A> const& )会将右侧的内容复制到左侧,并且在每次实现中,我都检查了左侧的capacity等于结果vectorsize。 同样,std::vector<T,A>( ForwardIterator, ForwardIterator )将生成一个刚好适合其输入的vector

请注意,std::vector<T,A>::operator=(std::vector<T,A>&&)的复杂性保持线性。

我在标准中找不到任何允许分配的内容 向量到具有足够容量以降低容量的载体。 如果我在作业前完成了reserve,我保证 迭代器不会因重新分配而失效,只要 矢量永远不会大于我保留的容量。

移动分配的问题尤其严重。 没有 似乎是任何允许它使迭代器无效的特殊情况 (除非源大于 目的地),但这违背了移动的目标 分配。 我怀疑这是标准的缺陷。

编辑:

对于它的价值,在表 96 中,对于a = rv(a在哪里) 一个容器,rv是相同类型的非常量 r 值 容器),该标准给出了线性复杂性,并说 "a的所有现有元素要么被移动到,要么 被毁"。 所以显然,该标准的意图容量不减少;执行时的优势 移动仅适用于单个元素,不适用于容器 本身。

要回答你的 PS: 至少对于std::string,你不能假设字符串的处理类似于字符向量的处理。

COW(写入时复制)不是实现字符串的强制性要求,并非所有库实现都这样做。

相关内容

最新更新