Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

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

Źródła