объединить вектор в существующий вектор

Question

В C ++, с учетом vector<T> src, dst, оба уже отсортированы, существует более эффективный способ объединения содержимого src в dst, чем

size_t n = dst.size();
dst.insert(dst.end(), src.begin(), src.end());
std::inplace_merge(dst.begin(), dst.begin() + n, dst.end());

? В случае, который меня волнует, T - это небольшая (12-16 байт, в зависимости от ABI) структура POD, но каждый вектор содержит миллионы элементов, поэтому общий объем используемой памяти составляет от десятков до сотен мегабайт.

Answer 1

Это может быть сделано более эффективно, если T тяжело копировать и ваш компилятор поддерживает C ++ 0x.

#include <iterator> // for make_move_iterator

size_t n = dst.size();

dst.insert(dst.end(),
    std::make_move_iterator(src.begin()),
    std::make_move_iterator(src.end()));

std::inplace_merge(dst.begin(), dst.begin() + n, dst.end());

Использование make_move_iterator() заставит insert() перемещать содержимое src в dst вместо их копирования.

Обновление:

Вы имеете дело с типами POD, и вы уже изменяете размер / копируете все в векторе dst в вероятном случае, когда insert() переполняет резерв, поэтому может быть быстрее просто использовать std::merge() в новый vector. Это позволит избежать того, что исходная копия И будет иметь худшую сложность в худшем случае:

inplace_merge() имеет лучший вариант сложности O ( n ), но ухудшается до O ( n log n ) в зависимости от ваши данные.

merge() имеет наихудший O ( n ), поэтому он гарантированно будет по крайней мере таким же быстрым, потенциально намного быстрее. Он также имеет встроенную оптимизацию перемещения.

Answer 2

Я бы хотя бы попробовал:

std::vector<T> tmp;
tmp.reserve(src.size() + dst.size()); // commenters are probably right about this
std::merge(src.begin(), src.end(), dst.begin(), dst.end(), std::back_inserter(tmp));
src.swap(tmp);

Но я подозреваю, что многое зависит от природы T, размера src и dst и того, почему мы должны оптимизировать.

Answer 3

Если инициализация ваших элементов по умолчанию намного дешевле, чем копирование, вы можете исключить вызов insert и изменить размер вектора назначения.Затем осуществите свое собственное слияние, возвращаясь назад - сохраняйте итераторы до конца источника и старого конца пункта назначения и перемещайте или копируйте в новый конец пункта назначения.Когда вы достигаете начала источника, все готово.