C++ push_back против вставки против emplace

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

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

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

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

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

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

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

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

Источник

3 ответа

Решение

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

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

Источник

Я предполагаю, что это действительно зависит от компилятора (реализация библиотеки), параметров компиляции и архитектуры. Выполнение быстрого теста в 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 элементов, используя эти разные методы "копирования значений...":

  1. Зарезервируйте место для 'b', затем используйте цикл b.push_back(a[i]);: 0,808 с
  2. Измените размер 'b', затем цикл for с помощью назначения индексов b[i] = a[i];: 0,264 сек
  3. Без изменения размера "б", просто b.insert(b.end(), a.begin(), a.end());: 0,021 с (без существенной разницы с резервом первым)
  4. std::copy(a.begin(), a.end(), std::back_inserter(b));: 0,944 с (0,871 с резервом первым)
  5. Измените размер 'b', затем memcopy на базовых указателях memcpy(&(b[0]), &(a[0]), 10000000*sizeof(int));: 0,061 сек

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

  1. цикл push_back: 0,659 сек
  2. Цикл индекса: 0,482 с
  3. вставка: 0,210 с (без существенной разницы с резервом первым)
  4. std:: copy: 0,422 сек с резервированием первым. Получил bad_alloc без него.
  5. memcpy: 0,329 с

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

Источник

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

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

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

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

Источник
Другие вопросы по тегам