Base de connaissancesCentre d’examen
FRFrançais
Choisir la langue13

CKTIS / C++

std::set_difference — différence de plages triées

std::set_difference copie la différence de deux plages triées vers une destination séparée. L’algorithme tient compte des doublons : chaque occurrence équivalente dans la seconde plage annule une occurrence du résultat de la première.

Version : C++23; repository compiler flag, production runtime not attested

Syntaxe

std::set_difference(first1, last1, first2, last2, result)
std::set_difference(first1, last1, first2, last2, result, comp)

std::set_difference, déclaré dans <algorithm>, calcule la différence orientée A − B, et non la différence symétrique. Il accepte deux plages d’itérateurs semi-ouvertes et un itérateur de sortie ; il ne nécessite pas de conteneurs std::set. Les appels décrits ici n’utilisent pas de politique d’exécution.

Les deux plages doivent être triées selon le même ordre : std::less{} par défaut, ou comp dans la seconde forme. Le comparateur doit définir un ordre strict faible. L’équivalence signifie !comp(a, b) && !comp(b, a), et pas nécessairement a == b. Le non-respect de la précondition de tri entraîne un comportement indéfini.

L’algorithme conserve les doublons : pour m éléments équivalents dans la première plage et n dans la seconde, il copie les derniers max(m - n, 0) éléments de la première, dans leur ordre d’origine. Le résultat est trié ; les entrées restent inchangées.

La destination ne doit chevaucher aucune des plages d’entrée. Si l’itérateur de sortie écrase des éléments dans une plage, celle-ci doit contenir suffisamment d’éléments déjà présents et accessibles en écriture. Un itérateur de sortie ne désigne toutefois pas nécessairement des éléments existants : std::back_inserter ajoute des éléments à la fin d’un conteneur et std::ostream_iterator écrit dans un flux. L’itérateur renvoyé pointe juste après le résultat écrit. La complexité est linéaire par rapport à la longueur totale des entrées, sans compter leur éventuel tri préalable.

Exemples

#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';
}

Résultat

1 2 4

Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.

Sources