Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

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

Zdroje