CKTIS / C++
std::inplace_merge: stabiles Mischen benachbarter Läufe
std::inplace_merge mischt zwei aufeinanderfolgende, bereits sortierte Teilbereiche stabil im selben Bereich.
Version: C++23
Syntax
template<class BidirectionalIt>
void std::inplace_merge(BidirectionalIt first, BidirectionalIt middle, BidirectionalIt last);
template<class BidirectionalIt, class Compare>
void std::inplace_merge(BidirectionalIt first, BidirectionalIt middle, BidirectionalIt last, Compare comp);std::inplace_merge(first,middle,last) mischt [first,middle) und [middle,last) mit std::less; eine Überladung nimmt comp. Beide Teilbereiche müssen gültig und nach derselben Ordnung sortiert sein. Das Ergebnis liegt in [first,last) und ist stabil: äquivalente Elemente des ersten Laufs bleiben vor denen des zweiten.
Das Beispiel enthält 1,4,7 und 2,3,8; danach druckt es 1 2 3 4 7 8. middle markiert nur die Eingabegrenze, keine im Ergebnis erhaltene Position.
Eine verletzte Sortiervoraussetzung ist undefiniertes Verhalten. Nötig sind bidirektionale Iteratoren und verschiebbare, vertauschbare Werte. Ohne Policy gibt es mit genügend Hilfsspeicher genau N−1 Vergleiche; fehlt der Puffer, wird mit bis zu O(N log N) ohne Puffer gearbeitet, andere Ausnahmen werden weitergereicht. Mit Standard-Execution-Policy führt eine unbehandelte Elementausnahme zu std::terminate; fehlt temporärer Speicher für parallele Ausführung, kann std::bad_alloc geworfen werden.
Beispiele
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> values{1, 4, 7, 2, 3, 8};
std::inplace_merge(values.begin(), values.begin() + 3, values.end());
for (int value : values) std::cout << value << ' ';
std::cout << '\n';
}
Ergebnis
1 2 3 4 7 8
std::inplace_merge → 1 2 3 4 7 8