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