Я создал вектор и использовал 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```
Правила очень просты.
std::vector::push_back
имеет две перегрузки.
Первая перегрузка принимает параметр const T &
. Вызов этой перегрузки использует конструктор копирования объекта.
Вторая перегрузка принимает параметр T &&
. Вызов этой перегрузки использует конструктор перемещения объекта.
Обратите внимание, что обе перегрузки могут в конечном итоге перераспределить вектор, что вызовет целую кучу ходов, но это не имеет значения. Я не наметил все диагностические выходные данные вашего кода, но также возможно, что вы регистрируете ходы из-за перераспределения, и это еще больше запутывает проблему (хотя я вижу, что вы использовали reserve()
, чтобы избавиться от этого, reserve()
включен непустой вектор, поэтому его единственное существующее значение перемещается, и это тоже может вас смутить).
И все это предполагает, что T
реализует семантику перемещения. Если нет, то это полностью копии.
Итак, вам нужно просто определить, передает ли данный конкретный вызов push_back()
lvalue или rvalue.
a.push_back(tmp);
tmp
, очевидно, является lvalue. В конечном итоге это вызовет конструктор копирования.
a.push_back(Node(14));
Этот параметр является значением r. В конечном итоге это вызовет конструктор перемещения.
Остальные вызовы можно выполнить по тому же принципу.
Если это так и push_back глубоко копирует каждое отдельное значение lvalue, не делает ли это временную сложность очень-очень плохой? Скажем, у меня есть вектор<vector<int>>, временная сложность добавления нескольких векторов будет равна O(n*m), где n — номер вектора, m — максимально допустимая длина векторов?
Я просто слышал, что люди говорят: «Временная сложность для push_back равна O (1)», но я думаю, что это обманчиво.
@qwert — push_back равен O (1), потому что он копирует один объект. Здесь не говорится, что копирование всех объектов одинаково затратно.
Разница между копированием и перемещением не связана с тем, является ли копия глубокой или нет. Для правильно спроектированных типов не должно быть никаких семантических различий (кроме состояния перемещенного объекта), когда вектор использует один вместо другого.
std::vector
будет использовать более дешевый вариант, когда это возможно, сохраняя при этом гарантии безопасности исключений.