stl: временные затраты для добавления элементов в вектор

Объясните пожалуйста откуда могут расти ноги во временных затратах при работе с добавлением в вектор:

есть следующие типы данных:

// элемент и совокупность элементов
using element_t = std::pair<int, int>;
using elements_t = std::vector<element_t>;

// ветка элементов
struct fork_t {
    elements_t sequence;
    int        weight;

    fork_t () {
         sequence.reserve(c_elements_count);
    }
};

// цепочка элементов
struct chain_t {
    fork_t     forks[2];
    int        weight;
};

// совокупность цепочек элементов
using chains_t = std::vector<chain_t>;

т.е. в общем то не очень сложные данные

в основном алгоритме происходит формирование цепочек (их меньше, чем элементов, которые входя в цепочки)

chains_t chains;
chains.reverse(c_chains_count);

for (...)
{
    // сразу добавляем цепочку, чтобы избежать лишнего копирования элементов
    chains.push_back(chain_t());
    auto& it = chains.back();

    // добавляем элементы
    add_elements(it);
}

внутри add_elements в цикле происходит добавление элементов

chain.fork[index].sequence.emplace_back(value1, value2);

Так вот когда посмотрел в профайлере, то оказалось, что на chains.push_back(chain_t()); тратится в несколько раз больше времени, чем на все emplace_back внутри add_elements

При этом кол-во цепочек гораздо (в разы) меньше, чем кол-во элементов добавляемых в цепочки.

У меня по этому возник вопрос - а с чем такое поведение может быть связано? Типы простые, каких-то сложных манипуляций с ними в конструкторах или где-то еще не происходит, тогда почему добавления пустых !!! цепочек для которых вызываются лишь 2 reserve() для каждой тратится так много времени?


Ответы (0 шт):