我想在单个 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!
最佳答案
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 所必需的。
reserve(n)
时,n
才将容量完全设置为n > capacity()
。 shrink_to_fit()
设置capacity == size
。它可能会或可能不会实现需要完整的 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
,没有新闻/删除,也没有拷贝。
结论
我的技术的最坏案例性能与预期的案例性能相同
您的技术。我的技术是有条件的。
关于c++ - 如何最好地填充 vector (避免浪费内存以及不必要的分配和取消分配)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18189362/