In this guide, we will explore the process of determining the symmetric variances between two multimaps in C++. Prior to delving into its application, it is essential to have a clear understanding of multimaps.
What is the Multimap in C++?
In C++, a 'std::multimap' serves as an associative container that holds key-value pairs, allowing multiple elements to have the same key. Unlike std::map, std::multimap allows for duplicate keys, ensuring each key-value pair is stored uniquely based on the key. This feature enables the utilization of the same key for multiple elements within the multimap.
Std::multimap provides efficient functions for adding, removing, and searching elements. It is implemented using a balanced binary search tree, like a red-black tree, to maintain the elements sorted based on their keys.
Example:
Let's consider an example to demonstrate the std::multimap container in the C++ programming language.
#include <iostream>
#include <map>
int main() {
std::multimap<int, std::string> multimap;
// Inserting elements
multimap.insert({1, "apple"});
multimap.insert({2, "banana"});
multimap.insert({1, "orange"});
// Iterating over elements
for(const auto& pair:multimap)
{
std::cout<<pair.first<<":"<<pair.second<<std::endl;
}
return 0;
}
Output:
What is the std::set_symmetric_difference?
A C++ function named std::setsymmetricdifference computes the symmetric variance between two arranged ranges and stores the outcome in a separate range. This function is declared in the header file of the <algorithm>.
Syntax:
It has the following syntax:
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
- The range of the first sorted sequence is defined by the input iterators first1, last1.
- The input iterators first2 and last2 provide the range of the second sorted sequence.
- An iterator for the output that stores the symmetric difference.
- An output iterator pointing to the element after the last element copied to the output range is returned by the function.
- A set that contains every member in either set A or B but not in their intersection is said to be the symmetric difference between sets A and B.
- Functionality: It puts the result in another sorted range after computing the symmetric difference between two sorted ranges.
- Setting parameters four input iterators (first1, last1, first2, and last2) that define the two sorted ranges are required, and the result is saved in an output iterator called result.
- O(n + m) is the time complexity, where n is the first range's size and m is the second range's size.
- The result's space complexity is O(n + m), where n and m represent the sizes of the input ranges.
Important details regarding std::set_symmetric_difference:
Program 1:
#include <iostream>
#include <map>
#include <vector>
#include <iterator>
using namespace std;
int main() {
// Define two multimap containers
multimap<string, int> map1 = { { "apple", 1 },
{ "banana", 2 },
{ "cherry", 3 } };
multimap<string, int> map2 = { { "banana", 3 },
{ "cherry", 3 },
{ "date", 4 } };
vector<pair<string, int>> sym_diff;
for (auto& elem1 : map1) {
if (map2.find(elem1.first) == map2.end() || map2.count(elem1.first) != map1.count(elem1.first)) {
sym_diff.push_back(elem1);
}
}
// Iterate through map2 and check for elements not in map1
for (auto& elem2 : map2) {
if (map1.find(elem2.first) == map1.end() || map1.count(elem2.first) != map2.count(elem2.first)) {
sym_diff.push_back(elem2);
}
}
// Print the symmetric difference
cout << "Symmetric Difference:" << endl;
for (auto& elem : sym_diff) {
cour<<elem.first<<" '<<elem.second<<endl;
}
return 0;
}
Output:
Complexity Analysis:
Time Complexity: O(n*(logm))
Space Complexity: O(n+m)
Program 2:
#include <iostream>
#include <map>
#include <algorithm>
int main() {
std::multimap<int, std::string> map1 = {{1, "apple"}, {2, "banana"}, {3, "orange"}};
std::multimap<int, std::string> map2 = {{2, "banana"}, {4, "grape"}, {5, "peach"}};
std::multimap<int, std::string> symmetricDifference;
std::set_symmetric_difference(map1.begin(), map1.end(),
map2.begin(), map2.end(),
std::inserter(symmetricDifference, symmetricDifference.end()));
// Print the symmetric difference
for (auto& pair : symmetricDifference) {
std::cout<<pair.first<<":"<<pair.second<<std::endl;
}
return 0;
}
Output:
Complexity Analysis:
Time Complexity: O(n+m)
Space Complexity: O(n+m)
Program 3:
#include <iostream>
#include <map>
#include <algorithm>
#include <iterator>
int main() {
// Define two multimaps representing student grades
std::multimap<std::string, int> grades1 = {
{"Alice".85},{"Bob",92},{"Charlie",78},{"Alice",90},{"David",80}
};
std::multimap<std::string, int> grades2 = {
{"Alice",90},{"Bob",92},{"Charlie",78},{"Eve",88},{"Frank",95}
};
// Create a multimap to store the symmetric difference in grades
std::multimap<std::string, int>SymDiff;
// Compute the symmetric difference using std::set_symmetric_diff
std::set_symmetric_diff(grades1.begin(), grades1.end(),
grades2.begin(), grades2.end(),
std::inserter(symDiff, symDiff.end()));
// Print the symmetric difference
std::cout << "Symmetric Difference of Grades:" << std::endl;
for (const auto& pair : symDiff) {
std::cout << pair.first<< ": " << pair.second << std::endl;
}
return 0;
}
Output:
Complexity Analysis:
Time Complexity: O(n+m)
Space Complexity: O(n+m)
