CKTIS / C++
std::set_difference — differenza di intervalli ordinati
std::set_difference copia la differenza di due intervalli ordinati in una destinazione separata. Tiene conto dei duplicati: ogni occorrenza equivalente nel secondo intervallo annulla un’occorrenza del risultato del primo.
Versione: C++23; repository compiler flag, production runtime not attested
Sintassi
std::set_difference(first1, last1, first2, last2, result)
std::set_difference(first1, last1, first2, last2, result, comp)std::set_difference, dichiarato in <algorithm>, calcola la differenza direzionale A − B, non la differenza simmetrica. Accetta due intervalli semiaperti di iteratori e un iteratore di output; non richiede contenitori std::set. Le chiamate descritte qui non usano una policy di esecuzione.
Entrambi gli intervalli devono essere ordinati secondo lo stesso criterio: std::less{} per impostazione predefinita, oppure comp nella seconda forma. Il comparatore deve definire un ordinamento stretto debole. Equivalenza significa !comp(a, b) && !comp(b, a), non necessariamente a == b. La violazione della precondizione di ordinamento causa un comportamento indefinito.
L’algoritmo conserva i duplicati: con m elementi equivalenti nel primo intervallo e n nel secondo, copia gli ultimi max(m - n, 0) elementi del primo, nel loro ordine originale. Il risultato è ordinato; gli input restano invariati.
La destinazione non deve sovrapporsi a nessuno degli intervalli di input. Se l’iteratore di output sovrascrive gli elementi di un intervallo, quest’ultimo deve contenere un numero sufficiente di elementi già presenti e modificabili. Un iteratore di output, però, non deve necessariamente riferirsi a elementi esistenti: std::back_inserter aggiunge elementi in coda a un contenitore e std::ostream_iterator scrive su un flusso. L’iteratore restituito punta subito dopo il risultato scritto. La complessità è lineare rispetto alla lunghezza complessiva degli input, senza considerare un eventuale ordinamento precedente.
Esempi
#include <algorithm>
#include <cstddef>
#include <iostream>
#include <iterator>
#include <vector>
int main() {
const std::vector<int> a{1, 2, 2, 2, 4, 7};
const std::vector<int> b{2, 2, 3, 7};
std::vector<int> difference;
std::set_difference(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(difference));
for (std::size_t i = 0; i < difference.size(); ++i) {
if (i != 0) std::cout << ' ';
std::cout << difference[i];
}
std::cout << '\n';
}
Risultato
1 2 4
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.