CKTIS / C++
std::inplace_merge: stabilne scalanie sąsiednich serii
std::inplace_merge stabilnie scala dwa kolejno położone, już posortowane podzakresy w tym samym zakresie.
Wersja: C++23
Składnia
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) scala [first,middle) i [middle,last) według std::less; przeciążenie przyjmuje comp. Oba podzakresy muszą być poprawne i osobno posortowane tym samym porządkiem. Wynik zajmuje [first,last) i jest stabilny: równoważne elementy z pierwszej serii pozostają przed równoważnymi z drugiej.
Przykład ma serie 1,4,7 i 2,3,8; po scaleniu wypisuje 1 2 3 4 7 8. Iterator middle wyznacza granicę wejściową, nie pozycję zachowaną w wyniku.
Naruszenie warunku posortowania jest naruszeniem precondition i daje undefined behavior. Algorytm wymaga iteratorów dwukierunkowych oraz przenoszalnych i zamienialnych wartości. Bez policy, gdy pamięć pomocnicza jest dostępna, wykonuje dokładnie N−1 porównań; brak bufora uruchamia algorytm bez pamięci o złożoności do O(N log N), a inne wyjątki propagują się. Przy standardowej execution policy nieprzechwycony wyjątek operacji elementu prowadzi do std::terminate, natomiast brak pamięci tymczasowej dla wykonania równoległego może rzucić std::bad_alloc.
Przykłady
#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';
}
Wynik
1 2 3 4 7 8
std::inplace_merge → 1 2 3 4 7 8