Почему std :: inserter так медленно?

Question

Давайте рассмотрим следующий код

#include <vector> 
using container = std::vector<int>; 
const int size = 1000000; 
const int count = 1000; 
void foo(std::insert_iterator<container> ist) 
{ 
    for(int i=0; i<size; ++i) 
     *ist++ = i; 
} 
void bar(container& cnt) 
{ 
    for(int i=0; i<size; ++i) 
     cnt.push_back(i); 
} 
int main() 
{ 
    container cnt; 
    for (int i=0; i<count; ++i) 
    { 
     cnt.clear(); 
     #ifdef FOO 
     foo(std::inserter(cnt, cnt.begin())); // using cnt.end() gives similar results 
     #else 
     bar(cnt); 
     #endif 
    } 
    return 0; 
} 

я получаю огромные изменения производительности

Использование Foo:

$ g++ -g -pipe -march=native -pedantic -std=c++11 -W -Wall -Wextra -Werror -O3 -o bin/inserter src/inserter.cc -DFOO 
$ time ./bin/inserter 
./bin/inserter 4,96s user 0,01s system 100% cpu 4,961 total 

Использование Бар:

$ g++ -g -pipe -march=native -pedantic -std=c++11 -W -Wall -Wextra -Werror -O3 -o bin/inserter src/inserter.cc 
$ time ./bin/inserter 
./bin/inserter 2,08s user 0,01s system 99% cpu 2,092 total 

Может кто-то объяснить, почему так большое изменение производительности и почему кто-то хочет использовать std::inserter?

Answer 1

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

Вместо этого следует использовать std::back_inserter(cnt), который будет называть cnt.push_back() при каждом вызове его разыменования operator*.

this related Смотрите также (но не совсем дублировать ИМО) Q & А различий между insert и push_back. Основное использование std::inserter предназначено для вставок в середине контейнера или для контейнеров, в которых отсутствует элемент push_back (или элемент push_front, что предотвратит использование std::front_inserter).