CKTIS / C++
std::inplace_merge: stabilní sloučení sousedních běhů
std::inplace_merge stabilně sloučí dva po sobě jdoucí již seřazené podrozsahy ve stejném rozsahu.
Verze: C++23
Syntaxe
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) slučuje [first,middle) a [middle,last) pomocí std::less; přetížení přijímá comp. Oba musí být platné a seřazené stejným pořadím. Výsledek zabere [first,last) a je stabilní: ekvivalentní prvky prvního běhu zůstanou před druhým.
Příklad má 1,4,7 a 2,3,8; po sloučení vypíše 1 2 3 4 7 8. middle označuje vstupní hranici, nikoli zachovanou pozici.
Porušení předpokladu seřazení je nedefinované chování. Jsou nutné obousměrné iterátory a přesouvatelné, zaměnitelné hodnoty. Bez policy dá dostatek pomocné paměti přesně N−1 porovnání; chybějící buffer zvolí bezbufferový algoritmus až O(N log N), jiné výjimky se šíří. Se standardní policy nezachycená výjimka prvku volá std::terminate; nedostatek dočasné paměti pro paralelní běh může vyhodit std::bad_alloc.
Příklady
#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';
}
Výsledek
1 2 3 4 7 8
std::inplace_merge → 1 2 3 4 7 8