How to Find the Difference of Two Deques in C++?
In C++, deques containers are sequential containers that allow the insertion and deletion of elements at both the beginning and end. In this article, we will learn how to find the difference between two deques in C++.
Example:
Input: deque1 = {1, 2, 3, 4, 5}; deque2 = {3, 4, 5, 6, 7}; Output: deque1 - deque2; Difference of two Deques: 1
Find the Difference of Two Deques in C++
The difference between two deques means that the list of elements that are present in the first deque but not in the second deque and vice versa.
To find the difference between two deques in C++, we can use the std::set_difference algorithm which finds the difference between two sorted ranges and save it in the given container.
Syntax of std::set_difference()
set_difference(first1, last1, first2, last2, d_first);
where:
- first1, last1: Iterator pointing to the beginning and end of the first deque.
- first2, last2: Iterator pointing to the beginning and end of the second deque.
- result: container to store the result.
C++ Program to Find the Difference of Two Deques
The below program demonstrates how we can find the difference of two deques in C++.
// C++ Program to illustrate how to find the difference
// between two deques
#include <algorithm>
#include <deque>
#include <iostream>
#include <iterator>
using namespace std;
int main()
{
// Initializing two deques
deque<int> deque1 = { 1, 2, 3, 4, 5 };
deque<int> deque2 = { 3, 4, 5, 6, 7 };
// Sorting the deques for set_difference
sort(deque1.begin(), deque1.end());
sort(deque2.begin(), deque2.end());
// Creating a deque to store the difference
deque<int> resultDifference;
// Finding the difference of the deques
set_difference(deque1.begin(), deque1.end(),
deque2.begin(), deque2.end(),
back_inserter(resultDifference));
// Printing the original deques
cout << "Deque 1: ";
for (int num : deque1) {
cout << num << " ";
}
cout << endl;
cout << "Deque 2: ";
for (int num : deque2) {
cout << num << " ";
}
cout << endl;
// Printing the difference of the two dequeues
cout << "Difference of two Deques: ";
for (int num : resultDifference) {
cout << num << " ";
}
cout << endl;
return 0;
}
Output
Deque 1: 1 2 3 4 5 Deque 2: 3 4 5 6 7 Difference of two Deques: 1 2
Time Complexity: O(NlogN + MlogM), where M and N are the size of two deques.
Space Complexity: O(N + M)
Contact Us