CKTIS / C++
std::inplace_merge: stabilné zlúčenie susedných behov
std::inplace_merge stabilne zlúči dva po sebe idúce už zoradené podrozsahy v tom istom rozsahu.
Verzia: 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) zlučuje [first,middle) a [middle,last) cez std::less; preťaženie prijíma comp. Oba musia byť platné a zoradené rovnakým poradím. Výsledok zaberie [first,last) a je stabilný: ekvivalentné prvky prvého behu zostanú pred druhým.
Príklad má 1,4,7 a 2,3,8; po zlúčení vypíše 1 2 3 4 7 8. middle označuje vstupnú hranicu, nie zachovanú pozíciu.
Porušenie predpokladu zoradenia je nedefinované správanie. Nutné sú obojsmerné iterátory a presúvateľné, zameniteľné hodnoty. Bez policy dá dosť pomocnej pamäte presne N−1 porovnaní; chýbajúci buffer zvolí bezbufferový algoritmus až O(N log N), iné výnimky sa šíria. So štandardnou policy nezachytená výnimka prvku volá std::terminate; nedostatok dočasnej pamäte na paralelný beh môže vyhodiť std::bad_alloc.
Prí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ýsledok
1 2 3 4 7 8
std::inplace_merge → 1 2 3 4 7 8