Encontrar Intersecção de Conjuntos em C++
-
Utilize o método
std::set_intersectionpara encontrar a intersecção de conjuntos em C++ -
Utilize o método
std::set_symmetric_differencepara encontrar a diferença simétrica set em C++
Este artigo explicará vários métodos de como encontrar a intersecção do conjunto em C++.
Utilize o método std::set_intersection para encontrar a intersecção de conjuntos em C++
O método std::set_intersection faz parte da biblioteca de algoritmos C++, que é incluída com o cabeçalho <algorithm>. A operação do algoritmo set_intersection não se restringe a objectos std::set, mas pode processar qualquer objecto baseado em gama, por exemplo, std::vector. Note-se que ambos os intervalos de entrada devem ser classificados antes de serem passados para um algoritmo set_intersection.
No exemplo seguinte, declaramos duas variáveis std::set e inicializamo-las com elementos do tipo string arbitrários. Os primeiros quatro parâmetros da função set_intersection são iteradores de intervalo de objectos correspondentes, e o quinto argumento é o início do intervalo onde a intersecção calculada é armazenada. Neste caso, declaramos um std::vector para guardar estes elementos.
#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);
}
Resultado:
s1 ∩ s2: ( array, deque, list, map, multimap, set, span, vector )
Ainda que std::set_intersection armazene os elementos de intersecção como especificado pelo utilizador, não deve ser o intervalo que se sobrepõe a qualquer um dos intervalos de entrada. Outro ponto importante a ter em conta é a especificação do intervalo de destino, que tem espaço suficiente para armazenar os elementos de intersecção. O método flexível para isto seria utilizar um array dinâmica std::vector e utilizar o método std::back_inserter para empurrar elementos para o objecto. Se especificar o vector.begin() iterator sem reservar a memória como parâmetro de destino, o algoritmo pode lançar uma falha de segmentação. O exemplo seguinte demonstra o método set_intersection em objectos 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);
}
Resultado:
v1 ∩ v2: ( 1, 2, 7 )
Utilize o método std::set_symmetric_difference para encontrar a diferença simétrica set em C++
Outro algoritmo da biblioteca padrão C++ é o std::set_symmetric_difference, que procura os elementos encontrados apenas numa das gamas de entrada. Os parâmetros da função são semelhantes ao método std::set_intersection. Ambos os algoritmos tomam intervalos ordenados e armazenam os elementos encontrados também de uma forma ordenada. Note-se que o recipiente std::set contém, por defeito, elementos ordenados. Assim, pode ser passado directamente como o intervalo de entrada. Enquanto que, std::vector o conteúdo deve ser explicitamente classificado antes de ser processado por 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);
}
Resultado:
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