CKTIS / C++
std::merge — fusione stabile di intervalli ordinati
std::merge di <algorithm> copia due intervalli ordinati in un intervallo di output separato. Mantiene i duplicati e la stabilità e restituisce un iteratore subito dopo l’ultimo elemento scritto.
Versione: C++23; repository compiler flag, production runtime not attested
Sintassi
#include <algorithm>
std::merge(first1, last1, first2, last2, result);
std::merge(first1, last1, first2, last2, result, comp);std::merge fonde [first1, last1) e [first2, last2), scrivendo tutti gli elementi a partire da result. Entrambi gli input devono essere già ordinati secondo lo stesso ordinamento: crescente per impostazione predefinita oppure quello specificato da comp. Il comparatore deve definire un ordinamento debole stretto. Input non ordinati violano le precondizioni dell’algoritmo; la funzione non ordina prima gli input.
La fusione è stabile: conserva l’ordine degli elementi in ciascun input e gli elementi con chiavi equivalenti del primo intervallo precedono quelli del secondo. Equivalenza significa che né comp(a, b) né comp(b, a) è vero. I duplicati restano nell’output.
L’intervallo di output non deve sovrapporsi a nessuno degli intervalli di input. Predisponi spazio per la somma delle loro lunghezze oppure usa un iteratore di inserimento appropriato. Chiamare solo reserve() su un vettore non crea elementi nei quali sia possibile scrivere tramite begin(). L’iteratore restituito indica la posizione subito dopo l’ultimo elemento scritto.
Per gli overload trattati qui, senza una politica di esecuzione, il lavoro è lineare rispetto al numero totale di elementi N, con al massimo N - 1 confronti quando N > 0. Non confondere questa funzione con std::inplace_merge, che fonde due sottointervalli ordinati adiacenti all’interno dello stesso intervallo. L’esempio usa una sintassi compatibile con C++23; la bozza di lavoro citata viene aggiornata e può includere anche estensioni successive.
Esempi
#include <algorithm>
#include <array>
#include <iostream>
int main() {
const std::array<int, 3> a{1, 3, 5};
const std::array<int, 3> b{2, 3, 6};
std::array<int, 6> result{};
const auto end = std::merge(a.begin(), a.end(),
b.begin(), b.end(), result.begin());
for (auto it = result.begin(); it != end; ++it) {
if (it != result.begin()) {
std::cout << ' ';
}
std::cout << *it;
}
std::cout << '\n';
}
Risultato
1 2 3 3 5 6
Il codice mostrato e il risultato dichiarato sono stati verificati in un ambiente isolato con il metodo registrato nella prova di verifica di questa versione esatta.