How To Find Symmetric Difference Of Two Multimaps In C++

In this article, we will discuss how to find symmetric differences of two multimaps in C++. Before going to its implementation, we must know about multimaps.

What is the Multimap in C++?

In C++ , a 'std::multimap' is an associative container that stores pairs of keys and values, where multiple elements can share the same key. In contrast to std::map, the std::multimap permits duplicate keys, which saves each key-value pair uniquely depending on the key. It implies that the same key may be used for more than one element in the multimap.

Std::multimap offers effective insertion, deletion, and searching functions . It is built as a balanced binary search tree, such as a red-black tree. It keeps the components arranged according to the keys.

Example:

Let us take an example to illustrate the std::multimap in C++.

#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 called std::setsymmetricdifference calculates the symmetric difference between two sorted ranges and puts the result in a different range. It is specified in the header 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.

Important details regarding std::set_symmetric_difference:

• ✅ 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.

Program 1:

Example
Copy
#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;
}
Try it Yourself

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)