#include <algorithm>
#include <iostream>
#include <iterator>
#include <map>
#include <set>
#include <string>

typedef std::multimap<std::string, std::string> map_type;

void display(const map_type& m, const std::string& title)
{
    std::cout << title << std::endl;
    std::cout << "-------------" << std::endl;
    for (map_type::const_iterator i = m.begin(), end = m.end(); i != end; ++i)
    {
        std::cout << i->first << " " << i->second << std::endl;
    }
    std::cout << "-------------" << std::endl;
}

int main ()
{
    map_type m, n, m_intersect_n;

    m.insert(std::make_pair("1-2", "1-1"));
    m.insert(std::make_pair("1-2", "1-2"));
    m.insert(std::make_pair("1-2", "1-3"));
    m.insert(std::make_pair("1-2", "1-4"));
    m.insert(std::make_pair("1-3", "2-1"));
    m.insert(std::make_pair("1-3", "21-1"));
    m.insert(std::make_pair("1-3", "21-2"));

    display(m, "multimap of m");

    n.insert(std::make_pair("1-2", "1-1"));
    n.insert(std::make_pair("1-2", "1-2"));
    n.insert(std::make_pair("1-2", "1-5"));
    n.insert(std::make_pair("1-2", "1-7"));
    n.insert(std::make_pair("1-3", "2-1"));
    n.insert(std::make_pair("1-3", "21-4"));
    n.insert(std::make_pair("1-3", "21-2"));

    display(n, "multimap of n");

    std::set<map_type::value_type> sorted_m(m.begin(), m.end());
    std::set<map_type::value_type> sorted_n(n.begin(), n.end());

    std::set_intersection(sorted_m.begin(), sorted_m.end(), 
                          sorted_n.begin(), sorted_n.end(), 
                          std::inserter(m_intersect_n, m_intersect_n.end()));

    display(m_intersect_n, "intersection");

    m.clear();
    std::set_difference(sorted_m.begin(), sorted_m.end(), 
                        sorted_n.begin(), sorted_n.end(), 
                        std::inserter(m, m.end()));

    display(m, "in m only");

    n.clear();
    std::set_difference(sorted_n.begin(), sorted_n.end(), 
                        sorted_m.begin(), sorted_m.end(), 
                        std::inserter(n, n.end()));

    display(n, "in n only");
}