Sorting multimap with both keys and values

Question

I am tryin to sort a multimap that have set of pairs in it using standard sort function by writing a compare function for it, but I am getting some error in it. I am trying to sort the map with values and then again sort it with keys. Compare function is causing some error. Can you point out where I am going wrong with this.

#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

bool cmp(const pair<int,int>& a, const pair<int,int>& b)
{
    return a.second < b.second;
}

int main() {
    // multimap of int ssId, int phone numbers
    multimap <int, int> m;
    m.insert(make_pair(1, 8));
    m.insert(make_pair(1, 5));
    m.insert(make_pair(2, 4));
    m.insert(make_pair(2, 3));
    m.insert(make_pair(3, 1));

    sort(m.begin(), m.end(), cmp);
    return 0;
}

Output should be like:

1 5
1 8
2 3 
2 4
3 1

Answer 1

There is no direct way to do that in C++ as multimap is ordered whose order cannot be changed but there is a workaround using an extra multimap. It will output exactly what you want. Similar approach works for string to integer and vice versa multimaps.

#include<bits/stdc++.h>
using namespace std;
int main()
{
    multimap <int, int> m;
    m.insert(make_pair(1, 8));
    m.insert(make_pair(1, 5));
    m.insert(make_pair(2, 4));
    m.insert(make_pair(2, 3));
    m.insert(make_pair(3, 1));
    multimap<int, int> R;
    for (auto i=m.begin(); i!=m.end(); i++)
        R.insert({i->second,i->first});
    m.clear();
    for (auto i=R.begin(); i!=R.end(); i++)
        m.insert({i->second,i->first});
    R.clear();
    for (auto i=m.begin(); i!=m.end(); i++)
        cout<<i->first<<"\t"<<i->second<<endl;
    return 0;
}

Answer 2

You are trying to sort strict ordered container. It is impossible, because swap of two elements in a whole multimap will violate its weak ordering in general. For example, with cmp you provided (just imagine) "sorted" m would be:

3 1
2 3
2 4
1 5
1 8

As you can see, ordering of m is violated.

Associative containers don't care about value's ordering. If you need order them then

• use another ordered container as value (e.g. std::map<int, std::set<int>>)

• use std::set<std::pair<int, int>, cmp> with custom cmp ordering. But note it is not map:

  1. you will not be able to access elements only by ssId, but you might access ranges by lower_bound() and upper_bound()
  2. elements of std::set are immutable. It means that to change element of std::set you have to remove them from set and then insert updated value.

std::set< std::pair<int, int> > m;

m.insert(make_pair(1, 8));
m.insert(make_pair(1, 5));
m.insert(make_pair(2, 4));
m.insert(make_pair(2, 3));
m.insert(make_pair(2, 1));
m.insert(make_pair(2, 5));
m.insert(make_pair(2, 2));
m.insert(make_pair(2, 0));
m.insert(make_pair(3, 1));

for(auto&& x : m) {
    std::cout << x.first << ' ' << x.second << std::endl;
}

auto b = m.lower_bound(std::make_pair(2, 2));
auto e = m.lower_bound(std::make_pair(2, 4));

std::cout << std::endl;

for(auto i = b; i != e; ++i) {
    std::cout << i->first << ' ' << i->second << std::endl;
}

will produce

1 5
1 8
2 0
2 1
2 2
2 3
2 4
2 5
3 1

2 2
2 3

Note, std::pair as well as std::tuple already have lexicographical compare operators.