CKTIS / C++
std::set_intersection — intersection de plages triées
std::set_intersection copie les éléments communs à deux plages triées vers une destination distincte. Les doublons sont conservés selon le nombre d’occurrences le plus faible, au lieu de ne produire que des valeurs uniques.
Version : C++23; repository compiler flag, production runtime not attested
Syntaxe
#include <algorithm>
std::set_intersection(first1, last1, first2, last2, result);
std::set_intersection(first1, last1, first2, last2, result, comp);std::set_intersection, déclaré dans <algorithm>, calcule l’intersection de [first1, last1) et [first2, last2). Il ne nécessite pas de conteneurs std::set. Cette fiche couvre les surcharges classiques à itérateurs, sans politique d’exécution ; elles renvoient un itérateur situé après le dernier élément écrit.
Les deux plages doivent déjà être triées selon le même ordre : std::less{} par défaut, ou le comparateur fourni pour la surcharge comp. Le comparateur doit définir un ordre faible strict. L’équivalence signifie !comp(a, b) && !comp(b, a), et pas nécessairement a == b. Des entrées non triées ne respectent pas une précondition.
Si une valeur équivalente apparaît m fois dans la première plage et n fois dans la seconde, le résultat contient les premiers min(m, n) éléments correspondants de la première plage. Le résultat reste trié. Le nombre de comparaisons est linéaire par rapport à la longueur totale des entrées.
La plage de sortie ne doit chevaucher aucune des plages d’entrée. Un itérateur de sortie ordinaire nécessite un nombre suffisant d’éléments modifiables ; reserve() seul ne les crée pas. L’exemple utilise std::back_inserter(common) pour ajouter les éléments à un vecteur distinct. La source est un brouillon de travail en évolution ; l’exemple se limite à l’API disponible en C++23.
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, 7};
std::vector<int> common;
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(common));
for (std::size_t i = 0; i < common.size(); ++i) {
if (i != 0) std::cout << ' ';
std::cout << common[i];
}
std::cout << '\n';
}
Résultat
2 2 7
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.