Q1 副本(在 push_back 中制作)是否有 capacity() == size() (我想要的),或者保留 tmp 的任何内容,或者这个实现是否依赖/未定义?
该标准从不设置容量的最大值,只设置最小值。也就是说,大多数实现将具有capacity() == size()
新的向量副本或容量,略微向上舍入到分配器实现的块大小。
Q2 我想知道省略变量 tmp 有什么不同,从而使代码看起来更优雅。
结果是移动table
而不是复制。
Q3 编译器是否有可能将我以前的代码“优化”为后一种形式,从而使用移动而不是复制(导致浪费内存)?
这是可能的,但可能性很小。编译器必须证明移动与复制没有明显不同,这具有足够的挑战性,据我所知,当前的编译器没有尝试过。
Q4 如果我是正确的,在我看来,所有这些都意味着为临时对象自动移动数据是一件喜忧参半的事情(因为它可以防止压缩)。
移动是速度优化,不一定是空间优化。复制可能会减少空间,但肯定会增加处理时间。
如果您想优化空间,最好的办法是使用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>
从 s 返回make_vector
、临时存储在 s 中tmp
、最后在s 中的 s 的分配和释放table
。
- 的返回值
make_vector(i)
可能有也可能没有capacity == size
。此分析视为make_vector
不透明并忽略构建返回向量所需的任何分配。
- 默认构造的向量的容量为 0。
reserve(n)
将容量准确设置为n
当且仅当n > capacity()
.
shrink_to_fit()
套capacity == size
。它可能会或可能不会被实现为需要整个矢量内容的副本。
- 向量复制构造函数设置
capacity == size
.
std::vector
可能会或可能不会为复制分配提供强有力的例外保证。
我将对两个正整数的分析进行参数化:算法结束时N
将出现的向量数(OP 中为 4242),以及:在过程中产生的所有向量中包含的对象总数算法。table
K
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
所需的内容。在#3tmp
大概离开范围并且它的存储被释放。
总分配/解除分配:N
。#2 处的所有分配,# N - 1
1 处的释放,以及#3 处的一个。
big_data_type
(对象的)总副本: K
.
对于 C++11 之前的版本
在#1,由于tmp
已经构建,RVO/复制省略不会发生。每次通过循环时,返回值都分配给tmp
. tmp
如果 (a) 实现提供了强保证,或者 (b)太小而无法包含返回向量中的所有元素,则此分配需要分配和解除分配。在任何情况下,元素都必须单独复制。在完整表达式的末尾,保存返回值的临时对象make_vector
被销毁,导致释放。
在 #2 处,tmp
被复制到table
. 新构建的副本table
具有
capacity == size
所需的内容。在#3tmp
大概离开范围并且它的存储被释放。
总分配/解除分配:N
+ 1 到 2 * N
。1 到N
#1、#2 的分配N
;
N
2 * N
- 1 次在 #1 处释放,1 次在 #3 处。
总份数:2 * K
. K
在#1 和K
#2。
我的技术(仅限 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
}
在 #1tmp
是从 的返回值新构建的make_vector
,因此 RVO/复制省略是可能的。即使实施make_vector
阻碍了 RVO,tmp
也将被移动构造,导致没有分配、释放或复制。
在 #2shrink_to_fit
可能需要也可能不需要单个分配和解除分配,这取决于来自的返回值是否make_vector
已经具有该capacity == size
属性。如果发生分配/解除分配,则可能会或可能不会复制元素,具体取决于实现的质量。
在 #3 的内容tmp
被移动到新构建的向量中
table
。不执行分配/解除分配/复制。
总分配/解除分配:0 或N
, 全部在 #2 当且仅当make_vector
不返回带有 的向量capacity == size
。副本总数:0 或K
,当且仅当shrink_to_fit
被实现为副本时,全部位于 #2。
如果实现者make_vector
生成具有该属性的向量capacity == size
并且标准库以shrink_to_fit
最佳方式实现,则没有新闻/删除和副本。
结论
My Technique 的最坏情况表现与 Your Technique 的预期情况表现相同。我的技术有条件地是最优的。