为什么交换(这个技巧)会缩小向量的容量?

why swap (this trick) shrink the capacity of vector?

如果我想缩小向量的容量,一种绑定方式,也是老办法:

std::vector<T>(v).swap(v);

为什么?为什么容量不也被简单地复制呢?标准中是否保证复制初始化将构造一个容量小于被复制向量的向量?我倾向于认为这只是指定的实现。

(在标准中,向量对 swap 的特化将交换元素和容量,这是 保证 。但我找不到任何关于复制初始化容量的保证. 可能的话请引用标准, 谢谢!)

Link 类似问题:What is the value of the capacity of std::vector when the copy constructor is used?

你是对的。 根本不能保证一定能用。它只是碰巧能用。

但人们可能会问另一个问题:为什么库程序员应该实现一个分配比需要的存储空间多得多的复制构造函数?可能存在舍入问题或一些备用问题,但是例如不太可能分配了两倍的存储空间。


不过,我强烈建议更喜欢新的shrink_to_fit函数。尽管它也没有存储保证,但实现可能会使用优化的分配函数来避免复制整个元素(例如,基于 realloc)。由此产生的内存碎片是否弊大于利是另一个问题。但应该留给实施来决定。

我喜欢让我重新评估我认为真实的问题。谢谢!

首先,我以为"capacity"是所有容器都有的东西。事实证明这是我的第一个错误。它仅适用于 std::vectorstd::string(以及 std::string_view)。

现在,查看您指定的表达式:

std::vector<T>(v).swap(v);

一方面,我们有 std::vector<T>(v),它正在复制 v,另一方面,我们有 v 的交换(大概是一个std::vector<T>) 与该副本。

让我们看看每一步。

复制构造函数

因为std::vector是一个容器,它必须满足"container"的要求。这就是它的复制构造函数的来源。 std::vector 的复制构造函数在 table 64 的 container.requirements 部分中定义,在表达式 X(a) 的行中。该行还指定复杂性必须是线性的。它还说副本的post条件“确保a == X(a)”。

要确定“a == X(a)”的含义,我们进一步查看 same table,然后看到:

== is an equivalence relation. equal(​a.begin(), a.end(), b.begin(), b.end())

如果我们将以上所有内容放在一起,它可以很好地近似于复制构造函数的工作:使用另一个 std::vector 的等效值填充一个 std::vector,在相同的顺序。

但是迂腐一点,除了满足std::vector<T>(v) == v.

之外,没有要求分配多少内存,或者调用分配多少次。

话虽这么说,但如果有任何实施者分配的资源超过最低要求,我会感到很惊讶。在 C++ 中,我们喜欢性能,而不是为我们不使用的东西付费。因此,除非有一个真正充分的理由要求容量更大,否则复制向量的容量将恰好是复制到它的元素数。因此,它是实现特定的

交换

same table中,表达式a.swap(b)的行指的是"Note A"。那张纸条说:

Those entries marked “(Note A)” [...] have constant complexity for [...] standard containers.

同样在 container.requirements 21.2.1.9 中有交换不使任何迭代器无效的要求:

The expression a.swap(b), for containers a and b of a standard container type [...] shall exchange the values of a and b without invoking any move, copy, or swap operations on the individual container elements. [...] Every iterator referring to an element in one container before the swap shall refer to the same element in the other container after the swap. It is unspecified whether an iterator with value a.end() before the swap will have value b.end() after the swap.

这是非常有趣的好东西!毕竟没有人喜欢让迭代器失效。 (与 shrink_to_fit 相比,如果必须重新分配,它可能会使迭代器无效。)

它也塑造了我们对 swap 容器的理解。由于元素上不允许 move/copy/swap,并且迭代器仍然有效,这对实现者来说在很大程度上意味着 swap 的目标将从源向量接管内存。 (是的,我知道这看起来很明显,但是该标准付出了巨大而奇妙的努力,通过拼写所有内容来确保显而易见的东西对每个人都是显而易见的。)

正如您所提到的,std::vector 具有 swap 的特化,这也需要交换 capacity。特别是,请参阅 "vector" 部分 21.3.11.3.12,其中显示:

Effects: Exchanges the contents and capacity() of *this with that of x.

这意味着标准保证 std::vector<T>(v)capacity 将被换成 v,当你这样做时:

std::vector<T>(v).swap(v);

TL;DR 交换目标的容量被强制与交换源相同。但是,由于复制构造的 std::vector 的容量 没有被标准明确规定 为任何特定值,因此它是特定于实现的。