CKTIS / C++
std::merge — stabiel samenvoegen van gesorteerde bereiken
std::merge uit <algorithm> kopieert twee gesorteerde bereiken naar een afzonderlijk uitvoerbereik. Het behoudt duplicaten en stabiliteit en retourneert een iterator één positie na het laatst geschreven element.
Versie: 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 voegt [first1, last1) en [first2, last2) samen en schrijft alle elementen vanaf result. Beide invoerbereiken moeten al volgens dezelfde volgorde zijn gesorteerd: standaard oplopend, of volgens de door comp opgegeven volgorde. De comparator moet een strikte zwakke ordening definiëren. Ongesorteerde invoer voldoet niet aan de voorwaarden van het algoritme; de functie sorteert de invoer niet eerst.
Het samenvoegen is stabiel: de volgorde van elementen binnen elke invoer blijft behouden, en elementen met equivalente sleutels uit het eerste bereik komen vóór die uit het tweede. Equivalentie betekent dat noch comp(a, b) noch comp(b, a) waar is. Duplicaten blijven in de uitvoer staan.
Het uitvoerbereik mag geen van beide invoerbereiken overlappen. Zorg voor ruimte ter grootte van de som van hun lengtes, of gebruik een geschikte invoegiterator. Alleen reserve() aanroepen op een vector maakt geen elementen aan waarnaar via begin() kan worden geschreven. De geretourneerde iterator wijst naar de positie direct na het laatst geschreven element.
Voor de hier besproken overloads zonder uitvoeringsbeleid is de hoeveelheid werk lineair in het totale aantal elementen N, met hoogstens N - 1 vergelijkingen wanneer N > 0. Verwar deze functie niet met std::inplace_merge, dat twee aangrenzende gesorteerde deelbereiken binnen hetzelfde bereik samenvoegt. Het voorbeeld gebruikt C++23-compatibele syntaxis; het genoemde werkdocument wordt bijgewerkt en kan ook latere uitbreidingen bevatten.
Voorbeelden
#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';
}
Resultaat
1 2 3 3 5 6
De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.