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

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.

Sources