Finding Vector Intersection in C++
To find the intersection of two vectors in C++, we can use std::set_intersection()
function provided in the STL <algorithm> library that is used to find the intersection of two sorted ranges. So, we will first need to sort the two vectors which we can do using std::sort function.
Syntax of std::set_intersection()
set_intersection (first1, last1, first2, last2, result);
where,
- first1: Iterator to the beginning of the first range.
- last1: Iterator to the last of the first range.
- first2: Iterator to the beginning of the second range.
- last1: Iterator to the last of the second range.
- result: Iterator to the beginning of the resulant data container.
C++ Program to Find the Intersection of Two Vectors
C++
// C++ program to find the intersection of two Vectors #include <bits/stdc++.h> using namespace std; // Driver code int main() { // Vectors vector< int > first_vector = { 10, 20, 30, 40, 50, 60 }; vector< int > second_vector = { 10, 30, 50, 40, 60, 80 }; // Sort the vector sort(first_vector.begin(), first_vector.end()); sort(second_vector.begin(), second_vector.end()); // Print the vector cout << "Vector 1: " ; for ( int i = 0; i < first_vector.size(); i++) cout << first_vector[i] << " " ; cout << endl; cout << "Vector 2: " ; for ( int i = 0; i < second_vector.size(); i++) cout << second_vector[i] << " " ; cout << endl; // Initialise a vector to store the common values and an // iterator to traverse this vector vector< int > v(first_vector.size() + second_vector.size()); vector< int >::iterator it, st; it = set_intersection(first_vector.begin(), first_vector.end(), second_vector.begin(), second_vector.end(), v.begin()); cout << "\nIntersection of two vectors:\n" ; for (st = v.begin(); st != it; ++st) cout << *st << ", " ; cout << '\n' ; return 0; } |
Vector 1: 10 20 30 40 50 60 Vector 2: 10 30 40 50 60 80 Intersection of two vectors: 10, 30, 40, 50, 60,
Time Complexity: O(N*logN + MlogM), where M and N is the size of two vectors.
Auxialiary Space: O(N + M)
How to Find the Intersection of Two Vectors in C++?
In C++, vectors are dynamic arrays that can grow and reduce in size as per requirements. The intersection of two datasets includes all the elements that are common in both datasets. In this article, we will see how to find the intersection of two vectors in C++.
Input: first_vector = {10,20,30,40,50,60}, second_vector = {10,30,50,40,60,80} Output: intersection: {10,30,40,50,60}