CKTIS / C++
std::merge — stabiles Zusammenführen sortierter Bereiche
std::merge aus <algorithm> kopiert zwei sortierte Bereiche in einen separaten Ausgabebereich. Duplikate und Stabilität bleiben erhalten; zurückgegeben wird ein Iterator hinter dem zuletzt geschriebenen Element.
Version: 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 führt [first1, last1) und [first2, last2) zusammen und schreibt alle Elemente ab result. Beide Eingaben müssen bereits nach derselben Ordnung sortiert sein: standardmäßig aufsteigend oder nach der durch comp festgelegten Ordnung. Der Komparator muss eine strikte schwache Ordnung definieren. Unsortierte Eingaben verletzen die Vorbedingungen des Algorithmus; die Funktion sortiert die Eingaben nicht zuerst.
Das Zusammenführen ist stabil: Die Reihenfolge der Elemente innerhalb jeder Eingabe bleibt erhalten, und Elemente mit äquivalenten Schlüsseln aus dem ersten Bereich kommen vor denen aus dem zweiten. Äquivalenz bedeutet, dass weder comp(a, b) noch comp(b, a) wahr ist. Duplikate bleiben in der Ausgabe erhalten.
Der Ausgabebereich darf sich mit keinem der Eingabebereiche überschneiden. Stelle Platz für die Summe ihrer Längen bereit oder verwende einen geeigneten Einfügeiterator. Nur reserve() für einen Vektor aufzurufen, erzeugt keine Elemente, in die über begin() geschrieben werden kann. Der zurückgegebene Iterator zeigt eine Position hinter das zuletzt geschriebene Element.
Bei den hier behandelten Überladungen ohne Ausführungsrichtlinie ist der Aufwand linear zur Gesamtzahl der Elemente N; für N > 0 sind höchstens N - 1 Vergleiche nötig. Verwechsle diese Funktion nicht mit std::inplace_merge, das zwei benachbarte sortierte Teilbereiche innerhalb desselben Bereichs zusammenführt. Das Beispiel verwendet mit C++23 kompatible Syntax; der zitierte Arbeitsentwurf wird aktualisiert und kann auch spätere Erweiterungen enthalten.
Beispiele
#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';
}
Ergebnis
1 2 3 3 5 6
Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.