How to sort both key and value in a multimap?

Question

Suggest any method to sort a multimap for both key and its values. For example- Input- (5,1), (1,9), (1,1), (5,2), (1,2) And the Output must be- (1,1), (1,2), (1,9), (5,1), (5,2).

Answer 1

The answer is emplace_hint. Pseudo code will look like that:-

insert_with_hint(M mmap, K key, V Value)
{
    auto i1 = mmap.equal_range(Key);
    for (auto i2 = i1.first; i2 != i1.second; ++i2)
    {
     if (i2->second > Key) { // <-- Here add your sorting criteria
           mmap.emplace_hint(i2,Key,Value)
      return
     }
   }
   mmap.emplace(Key,Value)
}

Answer 2

Change the key to include both values. Design a comparator which compares the two pairs of values in the correct order.

Having done this you can use multiset instead of a multimap.

Answer 3

If you really want to use multimap then the ordering of values is always the order in which you insert them and that cannot be changed unfortunately i.e in the example given in the question they are stored as (1,9), (1,1), (1,2), (5, 1), (5,2)

If you can relax a bit on the multimap, then you can use a set and store the above pairs in the set and define the ordering you desire on the pair definition. Since, the set stores it's values in sorted order, it will store your pairs also in the ordering you define.

Answer 4

You just need to copy all its elements to a multiset<pair<int, int>>:

multimap<int, int> a;
a.insert(pair<int, int>(5, 1));
a.insert(pair<int, int>(1, 9));
a.insert(pair<int, int>(1, 1));
a.insert(pair<int, int>(5, 2));
a.insert(pair<int, int>(1, 2));

multiset<pair<int, int>> b;
for (multimap<int, int>::iterator i=a.begin(); i!=a.end(); i++)
    b.insert(pair<int, int>((*i).first, (*i).second));

After this, multiset<pair<int, int>> b is what you want, i.e. {(1,1), (1,2), (1,9), (5,1), (5,2)}.