Baza znanjaCentar za ispite
HRHrvatski
Odaberi jezik13

CKTIS / C++

std::inplace_merge: stabilno spajanje susjednih nizova

std::inplace_merge stabilno spaja dva uzastopna već sortirana podraspona u istom rasponu.

Verzija: C++23

Sintaksa

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) spaja [first,middle) i [middle,last) s std::less; preopterećenje prima comp. Oba moraju biti valjana i sortirana istim poretkom. Rezultat zauzima [first,last) i stabilan je: ekvivalentni elementi prvog niza ostaju prije drugog.

Primjer sadrži 1,4,7 i 2,3,8; nakon spajanja ispisuje 1 2 3 4 7 8. middle označava ulaznu granicu, ne sačuvanu poziciju.

Kršenje preduvjeta sortiranosti je nedefinirano ponašanje. Traže se dvosmjerni iteratori i premjestive, zamjenjive vrijednosti. Bez policy dovoljno pomoćne memorije daje točno N−1 usporedbi; bez međuspremnika rabi algoritam bez buffera do O(N log N), dok se druge iznimke propagiraju. Uz standardnu policy neuhvaćena iznimka elementa zove std::terminate; manjak privremene memorije za paralelno izvođenje može baciti std::bad_alloc.

Primjeri

#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';
}

Rezultat

1 2 3 4 7 8 

std::inplace_merge → 1 2 3 4 7 8

Izvori