CKTIS / C++
std::merge — stabilno spajanje sortiranih raspona
std::merge iz <algorithm> kopira dva sortirana raspona u zaseban izlazni raspon. Čuva duplikate i stabilnost te vraća iterator iza posljednjeg zapisanog elementa.
Verzija: C++23; repository compiler flag, production runtime not attested
Sintaksa
#include <algorithm>
std::merge(first1, last1, first2, last2, result);
std::merge(first1, last1, first2, last2, result, comp);std::merge spaja [first1, last1) i [first2, last2) te zapisuje sve elemente počevši od result. Oba ulaza već moraju biti sortirana prema istom poretku: uzlazno prema zadanim postavkama ili prema poretku koji određuje comp. Usporednik mora definirati strogi slabi poredak. Nesortirani ulazi krše preduvjete algoritma; funkcija ih ne sortira prije spajanja.
Spajanje je stabilno: čuva redoslijed elemenata unutar svakog ulaza, a elementi s ekvivalentnim ključevima iz prvog raspona dolaze prije onih iz drugog. Ekvivalentnost znači da ni comp(a, b) ni comp(b, a) nije istinito. Duplikati ostaju u izlazu.
Izlazni raspon ne smije se preklapati ni s jednim ulaznim rasponom. Osigurajte prostor za zbroj njihovih duljina ili upotrijebite odgovarajući iterator za umetanje. Sam poziv reserve() nad vektorom ne stvara elemente u koje se može pisati putem begin(). Vraćeni iterator pokazuje na mjesto iza posljednjeg zapisanog elementa.
Za ovdje opisane preopterećene funkcije bez pravila izvođenja, rad je linearan u odnosu na ukupan broj elemenata N, uz najviše N - 1 usporedbi kada je N > 0. Nemojte ovu funkciju zamijeniti s std::inplace_merge, koja spaja dva susjedna sortirana podraspona unutar istog raspona. Primjer upotrebljava sintaksu kompatibilnu s C++23; navedeni radni nacrt ažurira se i može sadržavati i kasnija proširenja.
Primjeri
#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';
}
Rezultat
1 2 3 3 5 6
Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.