CKTIS / C++
std::merge — stabilné zlučovanie zoradených rozsahov
std::merge z hlavičky <algorithm> kopíruje dva zoradené rozsahy do samostatného výstupného rozsahu. Zachováva duplicity aj stabilitu a vracia iterátor za posledným zapísaným prvkom.
Verzia: C++23; repository compiler flag, production runtime not attested
Syntax
#include <algorithm>
std::merge(first1, last1, first2, last2, result);
std::merge(first1, last1, first2, last2, result, comp);std::merge zlučuje [first1, last1) a [first2, last2) a zapisuje všetky prvky od result. Oba vstupy už musia byť zoradené podľa rovnakého usporiadania: predvolene vzostupne alebo podľa usporiadania určeného pomocou comp. Komparátor musí definovať striktné slabé usporiadanie. Nezoradené vstupy porušujú predpoklady algoritmu; funkcia vstupy najprv netriedi.
Zlučovanie je stabilné: zachováva poradie prvkov v každom vstupe a prvky s ekvivalentnými kľúčmi z prvého rozsahu zaraďuje pred prvky z druhého. Ekvivalencia znamená, že ani comp(a, b), ani comp(b, a) nie je pravdivé. Duplicity vo výstupe zostávajú.
Výstupný rozsah sa nesmie prekrývať so žiadnym vstupným rozsahom. Zabezpečte miesto vo veľkosti súčtu ich dĺžok alebo použite vhodný vkladací iterátor. Samotné zavolanie reserve() na vektore nevytvorí prvky, do ktorých možno zapisovať cez begin(). Vrátený iterátor ukazuje na pozíciu za posledným zapísaným prvkom.
Pri tu opísaných preťaženiach bez politiky vykonávania je práca lineárna vzhľadom na celkový počet prvkov N; pri N > 0 sa vykoná najviac N - 1 porovnaní. Nezamieňajte túto funkciu s std::inplace_merge, ktorá zlučuje dva susedné zoradené podrozsahy v rámci toho istého rozsahu. Príklad používa syntax kompatibilnú s C++23; citovaný pracovný návrh sa aktualizuje a môže zahŕňať aj neskoršie rozšírenia.
Príklady
#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';
}
Výsledok
1 2 3 3 5 6
Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.