С++ push_back vs Вставить vs emplace

В настоящее время я делаю приложение с использованием векторов с С++.

Я знаю, как предварительная оптимизация является корнем всего зла.

Но я действительно не могу не быть любопытным.

Я добавляю части других векторов в другой вектор.
Будем говорить, что вектор будет иметь размер, который никогда не изменится на 300.

Так как я всегда добавляю к концу векторного

Быстрее ли это сделать:
a.reserve(300);
a.insert(a.end(), b.begin(), b.end());

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

Кто-нибудь может мне помочь?

Ответы

Ответ 1

Вот общий принцип: когда библиотека предоставляет как do_x_once, так и do_x_in_batch, последняя должна быть как минимум быстрее, чем вызов do_x_once в простой цикл. Если это не так, то библиотека очень плохо реализована, поскольку простой цикл достаточно для получения более быстрой версии. Часто такие пакетные функции/методы могут выполнять дополнительные оптимизации, поскольку они имеют знания о внутренних структурах данных.

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

Ответ 2

Как говорит larsmans, чем больше вы делаете в одном вызове библиотеки, тем больше более вероятно, что он будет более эффективным. В случае insert в вектор, библиотека, как правило, делает не более одного перераспределение и скопировать каждый сдвинутый элемент не более одного раза. Если вы используете цикл и push_back, он может перераспределить несколько раз, что может быть значительно медленнее (например, порядок величина).

В зависимости от типа, однако, это может быть и быстрее сделать что-то вроде:

a.resize( 300 );
std::copy( b.begin(), b.end(), a.end() - 300 );

Я нашел, что это быстрее для простых скалярных типов (например, int), используя g++ на машине Intel.

Ответ 3

Я думаю, это действительно зависит от компилятора (реализация библиотеки), компиляции параметров и архитектуры. Выполнение быстрого теста в VS2005 без оптимизации (/Od) на Intel Xeon:

std::vector<int> a;
std::vector<int> b;

// fill 'a' with random values for giggles

timer.start()
// copy values from 'a' to 'b'
timer.stop()

Я получаю эти результаты за 10 000 000 элементов, используя эти разные методы "значений копирования...":

  • Запасное пространство для 'b', затем для цикла с использованием b.push_back(a[i]);: 0,808 с
  • Resize 'b', затем for-loop с использованием назначения индексов b[i] = a[i];: 0.264 sec
  • Нет повторной калибровки 'b', просто b.insert(b.end(), a.begin(), a.end());: 0,021 сек (без существенной разницы с запасом)
  • std::copy(a.begin(), a.end(), std::back_inserter(b));: 0,944 с (0,871 с запасом).
  • Измените размер 'b', затем memcopy на базовых указателях memcpy(&(b[0]), &(a[0]), 10000000*sizeof(int));: 0,061 сек

Однако, если оптимизация включена (/Ox), это другая история. Я должен был увеличить размер до 100 000 000, чтобы получить большую дифференциацию:

  • push_back loop: 0.659 сек
  • индексный цикл: 0.482 сек
  • вставка: 0.210 с (без существенной разницы с запасом)
  • std:: копия: 0.422 с с резервом в первую очередь. Получил bad_alloc без него.
  • memcpy: 0.329 sec

Интересно отметить, что с оптимизацией или без нее метод вставки масштабируется линейно. Другие методы были явно неэффективны без оптимизаций, но все же не могли с ними справиться. Как отметил Джеймс Канзе, он отличается от g++. Запустите тест с собственной платформой для проверки.