Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

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

Fonti