Преимущества использования резерва () в векторе - C ++

Question

В чем преимущество использования резерва при работе с векторами. Когда я должен их использовать? Не смог найти однозначного ответа на этот вопрос, но я предполагаю, что он быстрее, если вы забронировали заранее, прежде чем их использовать.

Что вы, люди, умнее меня?

Answer 1

Полезно, если у вас есть представление о том, сколько элементов в конечном итоге будет содержать вектор - это может помочь вектору избежать повторного выделения памяти (и необходимости перемещать данные в новую память).

В общем, этовозможно, это потенциальная оптимизация, о которой вам не нужно беспокоиться, но она также не вредна (в худшем случае вы теряете память, если переоцениваете ее).

Одна область, в которой может быть больше, чем оптимизация,когда вы хотите убедиться, что существующие итераторы не будут аннулированы путем добавления новых элементов.

Например, вызов push_back() может сделать недействительными существующие итераторы для вектора (если происходит перераспределение).Однако, если вы зарезервировали достаточно элементов, вы можете быть уверены, что перераспределение не произойдет.Это техника, которую не нужно использовать очень часто.

Answer 2

В этой превосходной статье подробно объясняются различия между deque и vector контейнерами.Раздел «Эксперимент 2» показывает преимущества vector::reserve().

Answer 3

Это может быть ... особенно, если вы собираетесь со временем добавлять много элементов в свой вектор и хотите избежать автоматического расширения памяти, которое будет выполнять контейнер, когда у него кончаются доступные слоты.

Например, обратные вставки (то есть std::vector::push_back) считаются амортизированными O (1) или процессом с постоянным временем, но это потому, что если вставка в концевектор сделан, и вектору не хватает места, он должен затем перераспределить память для нового массива элементов, скопировать старые элементы в новый массив, а затем он может скопировать элемент, который вы пытались вставить в контейнер.Этот процесс является O (N), или сложностью линейного времени, и для большого вектора, может занять довольно много времени.Использование метода reserve() позволяет предварительно выделить память для вектора, если вы знаете, что он будет по крайней мере определенного размера, и избежать перераспределения памяти каждый раз, когда заканчивается пространство, особенно если вы собираетесь делать обратные вставкивнутри некоторого критичного к производительности кода, где вы хотите убедиться, что время выполнения вставки остается фактическим процессом сложности O (1) и не влечет за собой некоторое перераспределение скрытой памяти для массива.Конечно, ваш конструктор копирования должен был бы иметь сложность O (1), чтобы получить истинную сложность O (1) для всего процесса обратной вставки, но в отношении фактического алгоритма обратной вставки в вектор самим контейнером., вы можете сохранить известную сложность, если память для слота уже предварительно выделена.

Answer 4

Если вы знаете конечный размер вектора, тогда резервный код стоит использовать.

В противном случае, когда вектору не хватит внутренней комнаты, он изменит размер буфера.Обычно это включает удвоение (или 1,5 * текущий размер) размера внутреннего буфера (может быть дорого, если вы делаете это много).

Действительно дорогой бит - вызов конструктора копирования для каждого элемента для его копирования.из старого буфера в новый, с последующим вызовом деструктора для каждого элемента в старом буфере.

Если конструктор копирования дорогой, то это может быть проблемой.

Answer 5

Не знаю о людях, которые умнее вас, но я бы сказал, что вам следует позвонить reserve заранее, если вы собираетесь выполнять много операций вставки, и вы уже знаете или можете оценить общее количество элементов, в минимум на порядок. Это может сэкономить вам много перераспределения при хороших обстоятельствах.

Answer 6

Быстрее и экономит память

Если вы push_back другого элемента, то полный вектор обычно выделяет вдвое больше памяти, которую он использует в настоящее время - так как allocate + copy стоит дорого

Answer 7

Хотя это старый вопрос, вот моя реализация различий.

#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.

Кажется, что некоторыеулучшение с запасом, но не слишком большое улучшение.Я думаю, что это будет больше улучшений для сложных объектов, я не уверен.Любые предложения, изменения и комментарии приветствуются.