Trouver l'intersection des ensembles en C++
-
Utilisez la méthode
std::set_intersectionpour trouver l’intersection des ensembles en C++ -
Utiliser la méthode
std::set_symmetric_differencepour trouver la différence symétrique en C++
Cet article explique plusieurs méthodes pour trouver l’intersection de l’ensemble en C++.
Utilisez la méthode std::set_intersection pour trouver l’intersection des ensembles en C++
La méthode std::set_intersection fait partie de la bibliothèque d’algorithmes C++, qui est incluse avec l’en-tête <algorithme>. L’algorithme set_intersection n’est pas limité aux objets std::set, mais il peut traiter n’importe quel objet basé sur une plage, par exemple std::vector. Notez que les deux plages d’entrée doivent être triées avant d’être passées à un algorithme set_intersection.
Dans l’exemple suivant, nous déclarons deux variables std::set et les initialisons avec des éléments arbitraires de type string. Les quatre premiers paramètres de la fonction set_intersection sont des itérateurs de plage à partir des objets correspondants, et le cinquième argument est le début de la plage où l’intersection calculée est stockée. Dans ce cas, nous déclarons un std::vector pour contenir ces éléments.
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
using std::cout; using std::endl;
using std::cin; using std::string;
using std::set; using std::vector;
template<typename T>
void printVectorElements(vector<T> &vec)
{
cout << "{ ";
for (const auto &item : vec) {
cout << item << ", ";
}
cout << "\b\b }" << endl;
}
int main() {
set<string> s1 {"array", "vector",
"deque", "list",
"set", "map",
"multimap", "span"};
set<string> s2(s1);
s2.insert("stack");
s2.insert("queue");
vector<string> s1s2_intsec;
std::set_intersection(s1.begin(), s1.end(),
s2.begin(), s2.end(),
std::back_inserter(s1s2_intsec));
cout << "s1 ∩ s2: ";
printVectorElements(s1s2_intsec);
exit(EXIT_SUCCESS);
}
Production :
s1 ∩ s2: ( array, deque, list, map, multimap, set, span, vector )
Même si std::set_intersection stocke les éléments d’intersection comme spécifié par l’utilisateur, cela ne doit pas être la plage qui chevauche l’une ou l’autre des plages d’entrée. Un autre point important à prendre en compte est de spécifier la plage de destination, qui a suffisamment d’espace pour stocker les éléments d’intersection. La méthode flexible pour cela serait d’utiliser un tableau dynamique std::vector et d’utiliser la méthode std::back_inserter pour pousser les éléments vers l’objet. Si vous spécifiez l’itérateur vector.begin() sans réserver la mémoire comme paramètre de destination, l’algorithme peut lancer une erreur de segmentation. L’exemple suivant montre la méthode set_intersection sur des objets vector.
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
using std::cout; using std::endl;
using std::cin; using std::string;
using std::set; using std::vector;
template<typename T>
void printVectorElements(vector<T> &vec)
{
cout << "{ ";
for (const auto &item : vec) {
cout << item << ", ";
}
cout << "\b\b }" << endl;
}
int main() {
vector<int> v1v2_intsec;
vector<int> v1 {9,7,5,1,2};
vector<int> v2 {4,3,2,1,7,8};
std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());
std::set_intersection(v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter(v1v2_intsec));
cout << "v1 ∩ v2: ";
printVectorElements(v1v2_intsec);
exit(EXIT_SUCCESS);
}
Production :
v1 ∩ v2: ( 1, 2, 7 )
Utiliser la méthode std::set_symmetric_difference pour trouver la différence symétrique en C++
Un autre algorithme de la bibliothèque standard C++ est le std::set_symmetric_difference, qui recherche les éléments trouvés seulement dans une des plages d’entrée. Les paramètres de la fonction sont similaires à la méthode std::set_intersection. Les deux algorithmes prennent des plages triées et stockent les éléments trouvés également de manière triée. Notez que le conteneur std::set contient par défaut des éléments triés. Il peut donc être directement passé comme plage d’entrée. Alors que le contenu de std::vector doit être explicitement trié avant d’être traité par std::set_symmetric_difference.
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
using std::cout; using std::endl;
using std::cin; using std::string;
using std::set; using std::vector;
template<typename T>
void printVectorElements(vector<T> &vec)
{
cout << "{ ";
for (const auto &item : vec) {
cout << item << ", ";
}
cout << "\b\b }" << endl;
}
int main() {
vector<int> v1 {9,7,5,1,2};
vector<int> v2 {4,3,2,1,7,8};
std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());
vector<int> v1v2_symdif;
std::set_symmetric_difference(v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter(v1v2_symdif));
cout << "v1 △ v2: ";
printVectorElements(v1v2_symdif);
exit(EXIT_SUCCESS);
}
Production :
v1 △ v2: ( 3, 4, 5, 8, 9 )
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook