How to Find Set Intersection in C++
-
Use the
std::set_intersectionMethod to Find Set Intersection in C++ -
Use the
std::set_symmetric_differenceMethod to Find Set Symmetric Difference in C++
This article will explain several methods of how to find the set intersection in C++.
Use the std::set_intersection Method to Find Set Intersection in C++
The std::set_intersection method is part of the C++ algorithms library, which is included with the <algorithm> header. set_intersection algorithm operation is not restricted to std::set objects, but rather it can process any range based object, e.g. std::vector. Note that both input ranges must be sorted before passed to a set_intersection algorithm.
In the following example, we declare two std::set variables and initialize them with arbitrary string type elements. The first four parameters of the set_intersection function are range iterators from corresponding objects, and the fifth argument is the beginning of the range where the calculated intersection is stored. In this case, we declare a std::vector to hold these elements.
#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);
}
Output:
s1 ∩ s2: ( array, deque, list, map, multimap, set, span, vector )
Even though std::set_intersection stores the intersection elements as specified by the user, it must not be the range that overlaps with either of the input ranges. Another important point to be aware of is to specify the destination range, which has enough space to store the intersection elements. The flexible method for this would be to use a dynamic array std::vector and use the std::back_inserter method to push elements to the object. If you specify the vector.begin() iterator without reserving the memory as the destination parameter, the algorithm may throw a segmentation fault. Next example demonstrates set_intersection method on vector objects.
#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);
}
Output:
v1 ∩ v2: ( 1, 2, 7 )
Use the std::set_symmetric_difference Method to Find Set Symmetric Difference in C++
Another algorithm from the C++ standard library is the std::set_symmetric_difference, which searches for the elements found only in one of the input ranges. The function parameters are similar to the std::set_intersection method. Both algorithms take sorted ranges and store the found elements also in a sorted manner. Note that the std::set container is by default contains sorted elements. Thus it can be directly passed as the input range. Whereas, std::vector contents must be explicitly sorted before they are processed by 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);
}
Output:
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