C++ push_back vs Insert vs emplace

Question

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

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

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

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

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

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

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

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

Answer 1

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

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

Answer 2

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

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

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

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

Answer 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 элементов, используя эти различные методы «значений копирования ...«:

1. Резервирование места для„Ъ“, то для цикла с использованием b.push_back(a[i]);: 0,808 сек
2. Resize„б“, то для цикла с помощью присвоения индексов 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. Resize «б», то 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 :: копия: 0.422 sec с резервацией в первую очередь. Получил bad_alloc без него.
5. тетср: 0,329 сек

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