Почему std::insertter такой медленный?

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*,

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