В С++, данный 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, но каждый вектор содержит миллионы элементов, поэтому общий объем памяти в игре составляет от десятков до сотен мегабайт.
Я бы хотя бы попытался:
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, и почему мы должны оптимизировать.
Это можно сделать более эффективно, если 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), поэтому гарантируется, что он будет как минимум быстрым, потенциально намного быстрее. Он также имеет встроенную оптимизацию движения.
Если инициализация ваших элементов по умолчанию намного дешевле, чем копирование, вы можете удалить вызов insert и изменить размер вашего целевого вектора. Затем выполните свое собственное слияние, идите назад - сохраните итераторы до конца источника и старого конца адресата, и переместите или скопируйте на новый конец адресата. Когда вы достигнете начала источника, все готово.