Является ли более эффективным предубеждение вектора?

В четвертом выпуске С++ Primer, Стэнли Б. Липпман, Хозе Ладжой и Барбара Э. Му, говорится:

Поскольку векторы растут эффективно, обычно лучше всего разрешить вектор расти, добавляя к нему элементы динамически, поскольку значения элементов известно.

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

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

Предполагая, что это правильно (авторы так же авторитетны, как и они, один является соавтором самого С++), то может ли кто-нибудь дать мне случай, подтверждающий это утверждение, и объяснить, почему?

Ответ 1

Это зависит.

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

std::vector<int> v;

// good:
for (/* populate v */) // unknown number of iterations
{
    v.push_back(i); // possible reallocation, but not often
}

// bad:
for (/* populate v */) // unknown number of iterations
{
    v.reserve(v.size() + 1); // definite reallocation, every time
    v.push_back(i); // (no reallocation)
}

Но если вы знаете заранее, вы не будете перераспределять, тогда предопределите:

std::vector<int> v;

// good:
v.reserve(10); 
for (/* populate v */) // only 10 iterations (for example)
{
    v.push_back(i); // no reallocations
}

// not bad, but not the best:
for (/* populate v */) // only 10 iterations (for example)
{
    v.push_back(i); // possible reallocation, but not often (but more than needed!)
}

Ответ 2

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

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

Ответ 3

Я приурочил этот простой пример:

#include<iostream>
#include<vector>

int main() {

    int limit = 100 * 1000 * 1000;
    std::vector<long> my_vec;
    my_vec.reserve(limit); // comment out this line to not preallocate

    for (int i=0; i < limit; i++) {
        my_vec.push_back(i);
    }

    long my_sum = 0;
    for (int i=0; i < limit; i++) {
        my_sum += my_vec[i];
    }

    std::cout << my_sum << std::endl;
    return 0;
}

Соответствует:

g++ -std=c++11 -O2 my_file.cpp -o my_exec

И нашел, что разница существенна:

Без предварительного использования:

real    0m3.366s
user    0m1.656s
sys     0m1.660s

С preallocation:

real    0m1.688s
user    0m0.732s
sys     0m0.936s

Мое заключение здесь: если создание вектора является большой частью программы, то предварительное распределение для эффективности имеет смысл. Однако создание большого вектора снова и снова маловероятно, и, следовательно, оно редко является горлом бутылки. Однако использование reserve() имеет другие преимущества помимо предварительного распределения.

Bjarne Stroustrup на языке программирования С++ (4-е дополнение) имеет в виду следующее:

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