CKTIS / C++
std::merge — stabilno združevanje urejenih obsegov
std::merge iz <algorithm> kopira dva urejena obsega v ločen izhodni obseg. Ohranita se podvajanje in stabilnost, funkcija pa vrne iterator za zadnjim zapisanim elementom.
Različica: 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 združi [first1, last1) in [first2, last2) ter zapiše vse elemente od result naprej. Oba vhoda morata biti že urejena po istem vrstnem redu: privzeto naraščajoče ali po vrstnem redu, ki ga določa comp. Primerjalnik mora določati strogo šibko urejenost. Neurejena vhoda kršita predpogoje algoritma; funkcija vhodov ne uredi najprej.
Združevanje je stabilno: ohrani vrstni red elementov znotraj vsakega vhoda, elementi z enakovrednimi ključi iz prvega obsega pa so pred elementi iz drugega. Enakovrednost pomeni, da ne comp(a, b) ne comp(b, a) ni resničen. Podvojene vrednosti ostanejo v izhodu.
Izhodni obseg se ne sme prekrivati z nobenim vhodnim obsegom. Zagotovite prostor za vsoto njunih dolžin ali uporabite ustrezen vstavljalni iterator. Sam klic reserve() za vektor ne ustvari elementov, v katere bi bilo mogoče pisati prek begin(). Vrnjeni iterator kaže na mesto za zadnjim zapisanim elementom.
Pri tukaj obravnavanih preobremenitvah brez pravilnika izvajanja je delo linearno glede na skupno število elementov N; pri N > 0 je potrebnih največ N - 1 primerjav. Te funkcije ne zamenjujte s std::inplace_merge, ki združi dva sosednja urejena podobsega znotraj istega obsega. Primer uporablja skladnjo, združljivo s C++23; navedeni delovni osnutek se posodablja in lahko vključuje tudi poznejše razširitve.
Primeri
#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
Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.