c++ - 如何最好地填充 vector (避免浪费内存以及不必要的分配和取消分配)？

Question

我想在单个 vector 可以具有不同的size()时填充 vector 的 vector ，例如

std::vector<std::vector<big_data_type> > table;
std::vector<big_data_type> tmp;
for(auto i=0; i!=4242; ++i) {
  tmp = make_vector(i);              // copy elison; calls new[] only for i=0
  table.push_back(tmp);              // copy         calls new[] each time
}

我的主要问题是避免在未使用的容量上浪费内存。所以我的第一个问题是:

Q1 拷贝(在 push_back内部制作)会包含 capacity() == size()(我想要什么)，还是保留 tmp拥有的内容，或者此实现依赖于/未定义？

我正在考虑将单个 vector移到 table中

  table.push_back(std::move(tmp));   // move

但这肯定会保留 capacity并因此浪费内存。而且，这不会避免分配每个单独的 vector ，只会将其移动到另一个位置(在 make_vector内部，而不是 push_back内部)。

第2季度，我想知道省略变量 tmp会产生什么区别，从而使代码看起来更优雅(2行而不是5行):

for(auto i=0; i!=4242; ++i)
  table.push_back(make_vector(i));   // move!

我最初的想法是，这将在每次迭代时构造和破坏另一个临时对象，并因此生成对 new[]和 delete[]的多次调用(它们实际上将重用相同的内存)。但是，此外，这将调用 push_back的移动版本，从而浪费内存(请参见上文)。正确的？

Q3 编译器是否有可能将我之前的代码“优化”为后一种形式，从而使用移动而不是复制(导致浪费内存)？

Q4 如果我是对的，在我看来，这一切都意味着自动为临时对象移动数据是一种混杂的祝福(因为它阻止了压缩)。是否有任何方法可以明确禁止在最后的代码片段中移动，例如

for(auto i=0; i!=4242; ++i)
  table.push_back(std::copy(make_vector(i)));   // don't move!

Answer 1

Q1 Will the copy (made inside push_back) have capacity() == size() (what I want), or preserve whatever tmp had, or is this implementation dependent / undefined?

该标准从不为容量设置最大值，而仅设置最小值。就是说，大多数实现都将 capacity() == size()用作新的 vector 拷贝，或者将容量略微舍入到分配器实现的块大小。

Q2 I was wondering what difference it makes to omit the variable tmp, resulting in the more elegant looking code.

结果是移入 table而不是复制。

Q3 Is it possible that the compiler "optimizes" my former code into this latter form and thus uses moving instead of copying (resulting in wasting memory)?

有可能，但可能性很小。编译器必须证明移动与复制没有明显的区别，这具有很大的挑战性，据我所知，当前没有编译器尝试。

Q4 If I'm correct, it seems to me that all this implies that moving data automatically for temporary objects is a mixed blessing (as it prevents compacting).

移动是速度优化，不一定是空间优化。复制可以减少空间，但是肯定会增加处理时间。

如果要优化空间，最好的选择是使用 shrink_to_fit:

std::vector<std::vector<big_data_type> > table;
for(auto i=0; i!=4242; ++i) {
  std::vector<big_data_type> tmp = make_vector(i); // copy elison
  tmp.shrink_to_fit();                             // shrink
  table.push_back(std::move(tmp));                 // move
}

编辑:深入分析。

假设:

table将事先保留其空间，因为它的大小已知，我们
因此专注于vector<big_data_type>的分配和释放
从make_vector返回的结果，暂时存储在tmp中，
最后是table。

make_vector(i)的返回值可能具有capacity == size，也可能没有。
此分析将make_vector视为不透明，并忽略了任何分配
建立返回的 vector 所必需的。

默认构造的 vector 的容量为0。

且仅当 reserve(n)时，

n才将容量完全设置为n > capacity()。

shrink_to_fit()设置capacity == size。它可能会或可能不会实现
需要完整的 vector 内容的拷贝。

vector 复制构造函数设置capacity == size。

std::vector可能会或可能不会为以下情况提供强大的异常保证:
复制作业。

我将对两个正整数进行参数化分析: N，
在算法结尾(运算符中为4242)将为 table的 vector ，
和 K:所有 vector 中包含的 big_data_type对象总数
在算法过程中由 make_vector生成。

您的技术

std::vector<std::vector<big_data_type> > table;
table.reserve(N);
std::vector<big_data_type> tmp;
for(auto i=0; i!=N; ++i) {
  tmp = make_vector(i); // #1
  table.push_back(tmp); // #2
}
// #3

对于C++ 11

在＃1，由于已经构造了 tmp，因此不会发生RVO/复制省略。在
每次循环都将返回值分配给 tmp。这
分配是一个步骤: tmp中的旧数据将被销毁( tmp为空时的第一次迭代)，返回值的内容来自 make_vector已移入 tmp，没有进行任何复制。 tmp有 capacity == size当且仅当 make_vector的返回值具有该属性。

在＃2， tmp被复制到 table。 table中新构建的拷贝具有
所需的 capacity == size。在＃3处 tmp可能会离开范围及其
存储空间被释放。

总分配/解除分配: N。所有分配在＃2， N - 1释放在＃1，一个在＃3。

( big_data_type对象的总拷贝): K。

对于C++ 11之前的版本

在＃1，由于已经构造了 tmp，因此不会发生RVO/复制省略。在
每次循环都将返回值分配给 tmp。这
分配需要分配和解除分配，前提是(a)
实现提供了有力的保证，或者(b) tmp太小而无法
包含返回 vector 中的所有元素。无论如何，这些元素必须
单独复制。在完整表达式的末尾，临时对象
保留了 make_vector返回值的文件，导致
释放。

在＃2， tmp被复制到 table。 table中新构建的拷贝具有
所需的 capacity == size。在＃3处 tmp可能会离开范围及其
存储空间被释放。

总分配/解除分配: N +1至2 * N。 1到＃1的 N分配，＃2的 N分配；
N转换为2 * N-在＃1处分配1个，在＃3处分配一个。

总份数:2 * K。排名第一的 K和排名第二的 K。

我的技术(仅C++ 11)

std::vector<std::vector<big_data_type> > table;
table.reserve(N);
for(auto i=0; i!=N; ++i) {
  auto tmp = make_vector(i);          // #1
  tmp.shrink_to_fit();                // #2
  table.emplace_back(std::move(tmp)); // #3
}

在＃1处， tmp是根据 make_vector的返回值重新构建的，因此
RVO/复制省略是可能的。即使执行 make_vector阻碍了RVO， tmp将被移动构造，从而导致没有分配，
解除分配或拷贝。

在＃2处， shrink_to_fit可能需要或可能不需要一次分配，并且
释放，取决于 make_vector的返回值是否已经
具有 capacity == size属性。如果发生分配/取消分配，则
元素可以复制也可以不复制，具体取决于实现的质量。

在＃3， tmp的内容被移入一个新构造的 vector 中 table。不执行分配/取消分配/拷贝。

总分配/取消分配:0或 N，仅当 make_vector不返回带有 capacity == size的 vector 时，才排在＃2处。
总拷贝数:0或 K，当且仅当 shrink_to_fit实现为拷贝时，全部在＃2处。

如果 make_vector的实现者使用 capacity == size产生 vector
属性和标准库以最佳方式实现 shrink_to_fit，
没有新闻/删除，也没有拷贝。

结论

我的技术的最坏案例性能与预期的案例性能相同
您的技术。我的技术是有条件的。