提问人:qwert789812 提问时间:9/23/2023 最后编辑:qwert789812 更新时间:9/23/2023 访问量:122
C++ Vector 何时push_back深度复制对象?
c++ when do vector push_back deep copy objects?
问:
我创建了一个向量,并使用 push_back 将多个节点对象放入其中。但是,我无法预测它何时会使用移动构造函数或复制构造函数。
push_back使用复制构造函数或移动构造函数时有什么模式吗?C++ 参考资料说它有时会复制,有时会移动,但从未详细说明他们何时做什么。
#include <iostream>
#include <vector>
#include <unordered_set>
#include <set>
#include <unordered_map>
#include <map>
#include <queue>
using namespace std;
struct Node {
int val;
Node(int val) : val(val) {
cout<<"created object" << val<<endl;
}
Node(const Node& m) : val(m.val) {
cout<<"copy constructor is called on value " << m.val << endl;
}
~Node() {
cout<<"destroyed val" << val<<endl;
}
Node(Node&& other) noexcept
: val(other.val) {
cout<<"moved val " << other.val << endl;
}
};
void f(vector<Node>& a) {
cout<<"______________________"<<endl;
Node tmp(12);
cout<<"12 established"<<endl;
a.push_back(tmp);
cout<<"a pushed back 12"<<endl;
a.push_back(Node(14));
cout<<"a pushed back tmp obj 14"<<endl;
tmp.val+=5;
cout<<"increased tmp.val"<<endl;
cout<<tmp.val<<endl;
cout<<a[1].val<<endl;
cout<<"two prints"<<endl;
cout<<"_______________"<<endl;
cout<<"end of f"<<endl;
// return a;
}
int main() {
vector<Node> a = {Node(125)}; //copied since initialized temp var.
a.reserve(4000);
cout<<"start of f"<<endl;
f(a);
cout<<"program ended"<<endl;
//noteiced: Copy constructor called upon local variable (12) that the vector knows will not stay with it --- and belongs to local scope.
//copy constructor not called upon temporary variable that soon belonged to vector (14).
//same thing with std::queue, std::stack, and many others.
//but it this a pattern or a coincidence?
}
输出:
copy constructor is called on value 125
destroyed val125
moved val 125
destroyed val125
start of f
______________________
created object12
12 established
copy constructor is called on value 12
a pushed back 12
created object14
moved val 14
destroyed val14
a pushed back tmp obj 14
increased tmp.val
17
12
two prints
_______________
end of f
destroyed val17
program ended
destroyed val125
destroyed val12
destroyed val14```
答:
5赞
Sam Varshavchik
9/23/2023
#1
规则非常简单。
std::vector::push_back
有两个重载。
第一个重载采用一个参数。调用该重载使用对象的复制构造函数。const T &
第二个重载采用一个参数。调用该重载使用对象的 move 构造函数。T &&
请注意,这两个重载最终都可能重新分配向量,这将触发一大堆移动,这与重点无关。我还没有映射出您代码的所有诊断输出,但您也有可能由于重新分配而记录移动,这进一步混淆了问题(尽管我看到您曾经摆脱了这一点,它位于非空向量上,因此它的唯一现有值被移动,您可能会对此感到困惑, 太)。reserve()
reserve()
所有这些都假设实现了移动语义。如果没有,它就会一直复制。T
因此,您所要做的就是简单地确定给定的特定调用传递是左值还是右值。push_back()
a.push_back(tmp);
tmp
显然是一个 lvalue。这最终将调用复制构造函数。
a.push_back(Node(14));
此参数是右值。这最终将调用移动构造函数。
您可以使用相同的原理计算其余的调用。
评论
0赞
qwert789812
9/23/2023
如果是这样的话,并且push_back深度复制每一个价值值,这难道不会使时间复杂度变得非常非常糟糕吗?假设我有 vector<vector<int>>,附加多个向量的时间复杂度为 O(n*m),其中 n 是向量数,m 是向量的最大允许长度?
0赞
qwert789812
9/23/2023
我只是听说人们说“push_back的时间复杂度是 O(1)”,但我认为这是欺骗性的
2赞
BoP
9/23/2023
@qwert - push_back 是 O(1),因为它复制了一个对象。它并不是说所有对象的复制成本都一样高。
评论
std::vector