Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

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

Zdroje