#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");
}
I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8aXRlcmF0b3I+CiNpbmNsdWRlIDxtYXA+CiNpbmNsdWRlIDxzZXQ+CiNpbmNsdWRlIDxzdHJpbmc+Cgp0eXBlZGVmIHN0ZDo6bXVsdGltYXA8c3RkOjpzdHJpbmcsIHN0ZDo6c3RyaW5nPiBtYXBfdHlwZTsKCnZvaWQgZGlzcGxheShjb25zdCBtYXBfdHlwZSYgbSwgY29uc3Qgc3RkOjpzdHJpbmcmIHRpdGxlKQp7CiAgICBzdGQ6OmNvdXQgPDwgdGl0bGUgPDwgc3RkOjplbmRsOwogICAgc3RkOjpjb3V0IDw8ICItLS0tLS0tLS0tLS0tIiA8PCBzdGQ6OmVuZGw7CiAgICBmb3IgKG1hcF90eXBlOjpjb25zdF9pdGVyYXRvciBpID0gbS5iZWdpbigpLCBlbmQgPSBtLmVuZCgpOyBpICE9IGVuZDsgKytpKQogICAgewogICAgICAgIHN0ZDo6Y291dCA8PCBpLT5maXJzdCA8PCAiICIgPDwgaS0+c2Vjb25kIDw8IHN0ZDo6ZW5kbDsKICAgIH0KICAgIHN0ZDo6Y291dCA8PCAiLS0tLS0tLS0tLS0tLSIgPDwgc3RkOjplbmRsOwp9CgppbnQgbWFpbiAoKQp7CiAgICBtYXBfdHlwZSBtLCBuLCBtX2ludGVyc2VjdF9uOwoKICAgIG0uaW5zZXJ0KHN0ZDo6bWFrZV9wYWlyKCIxLTIiLCAiMS0xIikpOwogICAgbS5pbnNlcnQoc3RkOjptYWtlX3BhaXIoIjEtMiIsICIxLTIiKSk7CiAgICBtLmluc2VydChzdGQ6Om1ha2VfcGFpcigiMS0yIiwgIjEtMyIpKTsKICAgIG0uaW5zZXJ0KHN0ZDo6bWFrZV9wYWlyKCIxLTIiLCAiMS00IikpOwogICAgbS5pbnNlcnQoc3RkOjptYWtlX3BhaXIoIjEtMyIsICIyLTEiKSk7CiAgICBtLmluc2VydChzdGQ6Om1ha2VfcGFpcigiMS0zIiwgIjIxLTEiKSk7CiAgICBtLmluc2VydChzdGQ6Om1ha2VfcGFpcigiMS0zIiwgIjIxLTIiKSk7CgogICAgZGlzcGxheShtLCAibXVsdGltYXAgb2YgbSIpOwoKICAgIG4uaW5zZXJ0KHN0ZDo6bWFrZV9wYWlyKCIxLTIiLCAiMS0xIikpOwogICAgbi5pbnNlcnQoc3RkOjptYWtlX3BhaXIoIjEtMiIsICIxLTIiKSk7CiAgICBuLmluc2VydChzdGQ6Om1ha2VfcGFpcigiMS0yIiwgIjEtNSIpKTsKICAgIG4uaW5zZXJ0KHN0ZDo6bWFrZV9wYWlyKCIxLTIiLCAiMS03IikpOwogICAgbi5pbnNlcnQoc3RkOjptYWtlX3BhaXIoIjEtMyIsICIyLTEiKSk7CiAgICBuLmluc2VydChzdGQ6Om1ha2VfcGFpcigiMS0zIiwgIjIxLTQiKSk7CiAgICBuLmluc2VydChzdGQ6Om1ha2VfcGFpcigiMS0zIiwgIjIxLTIiKSk7CgogICAgZGlzcGxheShuLCAibXVsdGltYXAgb2YgbiIpOwoKICAgIHN0ZDo6c2V0PG1hcF90eXBlOjp2YWx1ZV90eXBlPiBzb3J0ZWRfbShtLmJlZ2luKCksIG0uZW5kKCkpOwogICAgc3RkOjpzZXQ8bWFwX3R5cGU6OnZhbHVlX3R5cGU+IHNvcnRlZF9uKG4uYmVnaW4oKSwgbi5lbmQoKSk7CgogICAgc3RkOjpzZXRfaW50ZXJzZWN0aW9uKHNvcnRlZF9tLmJlZ2luKCksIHNvcnRlZF9tLmVuZCgpLCAKICAgICAgICAgICAgICAgICAgICAgICAgICBzb3J0ZWRfbi5iZWdpbigpLCBzb3J0ZWRfbi5lbmQoKSwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgc3RkOjppbnNlcnRlcihtX2ludGVyc2VjdF9uLCBtX2ludGVyc2VjdF9uLmVuZCgpKSk7CgogICAgZGlzcGxheShtX2ludGVyc2VjdF9uLCAiaW50ZXJzZWN0aW9uIik7CgogICAgbS5jbGVhcigpOwogICAgc3RkOjpzZXRfZGlmZmVyZW5jZShzb3J0ZWRfbS5iZWdpbigpLCBzb3J0ZWRfbS5lbmQoKSwgCiAgICAgICAgICAgICAgICAgICAgICAgIHNvcnRlZF9uLmJlZ2luKCksIHNvcnRlZF9uLmVuZCgpLCAKICAgICAgICAgICAgICAgICAgICAgICAgc3RkOjppbnNlcnRlcihtLCBtLmVuZCgpKSk7CgogICAgZGlzcGxheShtLCAiaW4gbSBvbmx5Iik7CgogICAgbi5jbGVhcigpOwogICAgc3RkOjpzZXRfZGlmZmVyZW5jZShzb3J0ZWRfbi5iZWdpbigpLCBzb3J0ZWRfbi5lbmQoKSwgCiAgICAgICAgICAgICAgICAgICAgICAgIHNvcnRlZF9tLmJlZ2luKCksIHNvcnRlZF9tLmVuZCgpLCAKICAgICAgICAgICAgICAgICAgICAgICAgc3RkOjppbnNlcnRlcihuLCBuLmVuZCgpKSk7CgogICAgZGlzcGxheShuLCAiaW4gbiBvbmx5Iik7Cn0K