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() для каждой тратится так много времени?