Base di conoscenzaCentro esami
ITItaliano
Scegli la lingua13

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.

Fonti