C++ Vector 何时push_back深度复制对象?

c++ when do vector push_back deep copy objects?

提问人:qwert789812 提问时间:9/23/2023 最后编辑:qwert789812 更新时间:9/23/2023 访问量:122

问:

我创建了一个向量,并使用 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```
C++ 析构函数 复制构造 移动构造函数

评论

2赞 user17732522 9/23/2023
复制/移动之间的区别与复制是否深无关。对于设计正确的类型,当向量使用一个而不是另一个时,不应有任何语义差异(移出对象的状态除外)。 在可能的情况下,将在内部使用更便宜的举动,同时保持例外安全保证。std::vector

答:

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),因为它复制了一个对象。它并不是说所有对象的复制成本都一样高。