В чем преимущество использования резерва при работе с векторами. Когда я должен их использовать? Не удалось найти четкий ответ на это, но я предполагаю, что это быстрее, когда вы забронируете заранее, прежде чем использовать их.
Что скажешь, что ты умнее меня?
Полезно, если у вас есть представление о том, сколько элементов вектор в конечном счете будет удерживать - он может помочь вектору избежать многократного выделения памяти (и переместить данные в новую память).
В целом это, вероятно, потенциальная оптимизация, о которой вам не нужно беспокоиться, но она не вредна (в худшем случае вы теряете память, если вы оцениваете ее).
Одна область, где это может быть больше, чем оптимизация, - это то, что вы хотите, чтобы существующие итераторы не становились недействительными, добавляя новые элементы.
Например, вызов push_back() может аннулировать существующие итераторы к вектору (если происходит перераспределение). Однако, если вы зарезервировали достаточно элементов, вы можете убедиться, что перераспределение не произойдет. Это метод, который не нужно использовать очень часто, хотя.
Это может быть... особенно если вы собираетесь добавлять много элементов в вектор с течением времени, и вы хотите избежать автоматического расширения памяти, которое контейнер будет делать, когда закончится доступный слот.
Например, обратные вставки (т.е. std::vector::push_back) считаются амуртированным процессом O (1) или постоянным временем, но это потому, что если выполняется вставка в конце вектора, а вектор вне пространства, он должен перераспределить память для нового массива элементов, скопировать старые элементы в новый массив и затем скопировать элемент, который вы пытались вставить в контейнер. Этот процесс представляет собой O (N) или сложность линейного времени, а для большого вектора может занимать довольно много времени. Использование метода reserve() позволяет предварительно выделить память для вектора, если вы знаете, что он будет как минимум определенного размера, и избегать перераспределения памяти каждый раз, когда пробег заканчивается, особенно если вы собираетесь делать обратные вставки внутри некоторого критически важного кода, где вы хотите убедиться, что время выполнения вставки остается фактическим процессом сложности O (1) и не вызывает некоторого скрытого перераспределения памяти для массива. Разумеется, ваш конструктор копий должен также быть сложностью O (1), чтобы получить истинную сложность O (1) для всего процесса обратной вставки, но в отношении фактического алгоритма обратной вставки в вектор самим контейнером, вы можете сохранить его известной сложностью, если память для слота уже предварительно выделена.
Эта отличная статья глубоко объясняет различия между контейнерами deque и vector. Раздел "Эксперимент 2" показывает преимущества vector::reserve().
Если вы знаете конечный размер вектора, то резерв стоит использовать.
В противном случае, когда вектор заканчивается из внутренней комнаты, он будет изменять размер буфера. Обычно это предполагает удвоение (или 1,5 * текущий размер) размера внутреннего буфера (может быть дорого, если вы это сделаете).
Настоящий дорогой бит вызывает конструктор копирования для каждого элемента, чтобы скопировать его из старого буфера в новый буфер, а затем вызвать деструктор для каждого элемента в старом буфере.
Если конструктор копирования дорог, это может быть проблемой.
Быстрее и экономит память
Если вы нажмете push_back на другой элемент, тогда полный вектор будет обычно выделять двойную память, которую он использует в настоящее время, так как выделение + копия дорого
Не знаю о людях умнее вас, но я бы сказал, что вы должны называть reserve заранее, если вы собираетесь выполнять партии в операциях ввода, и вы уже знаете или можете оценить общее количество элементов, на на порядок меньше. Это может сэкономить вам много перераспределений в хороших условиях.
Хотя это старый вопрос, вот моя реализация для различий.
#include <iostream>
#include <chrono>
#include <vector>
using namespace std;
int main(){
vector<int> v1;
chrono::steady_clock::time_point t1 = chrono::steady_clock::now();
for(int i = 0; i < 1000000; ++i){
v1.push_back(1);
}
chrono::steady_clock::time_point t2 = chrono::steady_clock::now();
chrono::duration<double> time_first = chrono::duration_cast<chrono::duration<double>>(t2-t1);
cout << "Time for 1000000 insertion without reserve: " << time_first.count() * 1000 << " miliseconds." << endl;
vector<int> v2;
v2.reserve(1000000);
chrono::steady_clock::time_point t3 = chrono::steady_clock::now();
for(int i = 0; i < 1000000; ++i){
v2.push_back(1);
}
chrono::steady_clock::time_point t4 = chrono::steady_clock::now();
chrono::duration<double> time_second = chrono::duration_cast<chrono::duration<double>>(t4-t3);
cout << "Time for 1000000 insertion with reserve: " << time_second.count() * 1000 << " miliseconds." << endl;
return 0;
}
Когда вы компилируете и запускаете эту программу, она выдает:
Time for 1000000 insertion without reserve: 24.5573 miliseconds.
Time for 1000000 insertion with reserve: 17.1771 miliseconds.
Кажется, что некоторые улучшения с запасом, но не слишком большие улучшения. Я думаю, что это будет больше улучшения для сложных объектов, я не уверен. Любые предложения, изменения и комментарии приветствуются.