CKTIS / C++
std::inplace_merge: fusione stabile di sequenze adiacenti
std::inplace_merge fonde stabilmente due sottorange consecutivi già ordinati nello stesso range.
Versione: C++23
Sintassi
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) fonde [first,middle) e [middle,last) con std::less; un overload accetta comp. Entrambi devono essere validi e ordinati con lo stesso criterio. Il risultato occupa [first,last) ed è stabile: gli equivalenti del primo gruppo precedono quelli del secondo.
L’esempio contiene 1,4,7 e 2,3,8; dopo la fusione stampa 1 2 3 4 7 8. middle segna il confine di input, non una posizione preservata.
Violare la precondizione di ordinamento è comportamento indefinito. Servono iteratori bidirezionali e valori spostabili e scambiabili. Senza policy, memoria sufficiente dà esattamente N−1 confronti; se il buffer manca usa l’algoritmo senza buffer fino a O(N log N), mentre le altre eccezioni si propagano. Con policy standard, un’eccezione di elemento non catturata chiama std::terminate; memoria temporanea indisponibile per l’esecuzione parallela può lanciare std::bad_alloc.
Esempi
#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';
}
Risultato
1 2 3 4 7 8
std::inplace_merge → 1 2 3 4 7 8