Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

CKTIS / C++

std::inplace_merge: stabilno združevanje sosednjih zaporedij

std::inplace_merge stabilno združi dve zaporedni že urejeni podobmočji v istem območju.

Različica: 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) združi [first,middle) in [middle,last) s std::less; preobremenitev sprejme comp. Obe morata biti veljavni in urejeni po istem redu. Rezultat zasede [first,last) in je stabilen: enakovredni elementi prvega dela ostanejo pred drugim.

Primer vsebuje 1,4,7 in 2,3,8; nato izpiše 1 2 3 4 7 8. middle označuje vhodno mejo, ne ohranjene pozicije.

Kršitev predpogoja urejenosti je nedoločeno vedenje. Potrebni so dvosmerni iteratorji in premakljive, zamenljive vrednosti. Brez policy dovolj pomožnega pomnilnika pomeni natanko N−1 primerjav; brez medpomnilnika uporabi brezpomnilniški algoritem do O(N log N), druge izjeme pa se razširijo. S standardno policy neujeta izjema elementa pokliče std::terminate; pomanjkanje začasnega pomnilnika za vzporedno izvedbo lahko vrže std::bad_alloc.

Primeri

#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

Viri