Вектор слияния в существующий вектор

В С++, данный 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, но каждый вектор содержит миллионы элементов, поэтому общий объем памяти в игре составляет от десятков до сотен мегабайт.

Ответ 1

Я бы хотя бы попытался:

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, и почему мы должны оптимизировать.

Ответ 2

Это можно сделать более эффективно, если T тяжело копировать, а ваш компилятор поддерживает С++ 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 вместо копирования.

Update:

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

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

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

Ответ 3

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