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.