Эффективность при заполнении вектора

Question

Что будет эффективнее и почему?

vector<int> numbers;

for (int i = 0; i < 10; ++i)
    numbers.push_back(1);

или

vector<int> numbers(10,0);

for (int i = 0; i < 10; ++i)
    numbers[i] = 1;

Спасибо

Answer 1

Самый быстрый будет:

vector <int> numbers(10, 1);

Что касается ваших двух методов, обычно второго; хотя первый избегает первого обнуления вектора в конструкторе, он выделяет достаточно памяти с самого начала, избегая перераспределения.

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

Обратите внимание, что это верно для примитивных типов. Если вы начинаете иметь объекты со сложными конструкторами копирования, как правило, самое эффективное решение - reserve + push_back, поскольку вы избегаете всех бесполезных вызовов конструктора по умолчанию, которые обычно тяжелее, чем стоимость push_back.

Answer 2

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

vector<int> numbers;
numbers.reserve(10);

for (int i = 0; i < 10; ++i)
    numbers.push_back(1);

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

Answer 3

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

Answer 4

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

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

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

Так что это случай N инициализаций против N сравнений. Когда тип имеет тип int, вполне может быть оптимизация с инициализацией (memset или чем-то еще), позволяющая это сделать быстрее, но с объектами я бы сказал, что сравнения (reserve и push_back) почти наверняка будут быстрее.

Answer 5

Используйте второе, и, если у вас есть йота (у C ++ 11 есть), используйте это вместо цикла for.

Answer 6

Второй быстрее из-за предварительного выделения памяти. В первом варианте кода вы также можете использовать numbers.reserve(10);, который будет выделять вам память сразу, а не на каждой итерации (возможно, некоторая реализация делает более громоздкое резервирование, но не полагайтесь на это).

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

#include <algorithm>
#include <vector>
using namespace std;

staitc const size_t N_ELEMS = 10;

void some_func() {
  vector<int> numbers(N_ELEMS);

  // Verbose variant
  vector<int>::iterator it = numbers.begin();
  while(it != numbers.end())
    *it++ = 1;


  // Or more tight (using C++11 lambdas)
  // assuming vector size is adjusted
  generate(numbers.begin(), numbers.end(), []{ return 1; });
}


//