CKTIS / C++
std::merge — стабилно сливане на сортирани диапазони
std::merge от <algorithm> копира два сортирани диапазона в отделен изходен диапазон. Запазва дубликатите и стабилността и връща итератор след последния записан елемент.
Версия: C++23; repository compiler flag, production runtime not attested
Синтаксис
#include <algorithm>
std::merge(first1, last1, first2, last2, result);
std::merge(first1, last1, first2, last2, result, comp);std::merge слива [first1, last1) и [first2, last2), като записва всички елементи от result нататък. И двата входа вече трябва да са сортирани по един и същ ред: по подразбиране във възходящ ред или според реда, зададен от comp. Компараторът трябва да задава строга слаба наредба. Несортираните входове нарушават предусловията на алгоритъма; функцията не сортира входовете предварително.
Сливането е стабилно: запазва реда на елементите във всеки вход, а елементите с еквивалентни ключове от първия диапазон се поставят преди тези от втория. Еквивалентност означава, че нито comp(a, b), нито comp(b, a) е истина. Дубликатите остават в изхода.
Изходният диапазон не трябва да се припокрива с нито един от входните диапазони. Осигурете място за сбора от дължините им или използвайте подходящ итератор за вмъкване. Самото извикване на reserve() за вектор не създава елементи, в които може да се записва чрез begin(). Върнатият итератор сочи позицията след последния записан елемент.
За разглежданите тук претоварвания без политика за изпълнение работата е линейна спрямо общия брой елементи N, с най-много N - 1 сравнения, когато N > 0. Не бъркайте тази функция с std::inplace_merge, която слива два съседни сортирани поддиапазона в рамките на същия диапазон. Примерът използва синтаксис, съвместим с C++23; цитираният работен проект се актуализира и може да включва и по-късни разширения.
Примери
#include <algorithm>
#include <array>
#include <iostream>
int main() {
const std::array<int, 3> a{1, 3, 5};
const std::array<int, 3> b{2, 3, 6};
std::array<int, 6> result{};
const auto end = std::merge(a.begin(), a.end(),
b.begin(), b.end(), result.begin());
for (auto it = result.begin(); it != end; ++it) {
if (it != result.begin()) {
std::cout << ' ';
}
std::cout << *it;
}
std::cout << '\n';
}
Резултат
1 2 3 3 5 6
Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.