Самый быстрый способ преобразования из вектора пар в два независимых вектора в C ++

Question

Допустим, у меня есть vector из pair<int,int>.Теперь я хочу извлечь pair.first и pair.second как независимые векторы.Я могу перебрать вектор и сделать это, но есть ли лучший / более быстрый способ?

Answer 1

В C ++ 11, если вам больше не нужен старый вектор, возможно, вы могли бы получить небольшую дополнительную эффективность от семантики перемещения:

for (auto it = std::make_move_iterator(v.begin()),
         end = std::make_move_iterator(v.end()); it != end; ++it)
{
    v1.push_back(std::move(it->first));
    v2.push_back(std::move(it->second));
}

Кроме этого, вы, конечно, не можетесделать лучше, чем один цикл.Вам нужно будет дотронуться до каждого элемента хотя бы один раз, так что это настолько эффективно, насколько это возможно.

Обратите внимание, что перемещение может иметь значение только в том случае, если сами типы элементов имеют семантику перемещения, которая лучше копирования.Это не относится к int с или любым POD.Но это не помешает написать ваш код в общем, чтобы вы могли воспользоваться этим в будущих ситуациях.

Если копирование / перемещение является проблемой, тем не менее, вы должны подумать, есть ли какой-либо адаптер представления для вашего исходного вектораможет быть, лучший подход.

Answer 2

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

Answer 3

Вы не сможете избежать итерации.Что касается самого быстрого решения, оно зависит от того, что находится в паре, и от фактической реализации.В зависимости от них может быть лучше создать целевые векторы с правильным размером и назначить их;или чтобы создать их пустыми, используйте reserve, а затем push_back.Вы также можете сравнить индексирование с использованием итераторов;если вы используете предварительно заданные размеры, лучше всего использовать только одну переменную управления вместо трех.(При использовании g ++, в прошлый раз, когда я измерял, создание векторов правильного размера и присваивание выполнялось быстрее, чем при использовании reserve и push_back, по крайней мере, при double. Несмотря на то, что это означало повторение цикла внутри себя и инициализациязначения 0.0.)

Вы также можете попробовать создать функциональные объекты для извлечения первого и второго элементов пары (предположим, что у вас их еще нет) и использовать два вызова для * 1009.*.Опять же, либо с предразмерным вектором, либо с использованием задней вставки в качестве цели.Я бы не ожидал, что это обеспечит лучшую производительность, но вы никогда не узнаете.

Answer 4

В любом случае вам придется перебирать вектор, так что с точки зрения сложности это настолько хорошо, насколько вы можете получить.