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

Solution 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;
}

Solution 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.

Solution 3

This is an old question, but may be useful for others if they are looking.

For this kind of scenario where we want values to be sorted for same key, Instead of using

multimap <int, int> m;

use

map<int,vector<int>> and then sort the individual vector.
or even better, just:
vector<pair<int,int>> and then sort the vector

vector<pair<int, int>> vec{{1,8}, {1,5},{2,4} ,{2,3}, {3,1}};
sort(begin(vec), end(vec));

the internal ordering of pair<int,int> will take care of ordering by first and when first element is same, it orders those pairs by second element.

Comments

[ivanw]

Please look at stackoverflow.com/questions/21215214/…

[Blastfurnace]

1) A std::multimap is only ordered by its keys and you can't reorder it after it's built. 2) You couldn't use std::sort for this anyway because it requires random access iterators and std::multimap only provides bidirectional iterators.

[Blastfurnace]

C++ standard library maps and sets are typically implemented as self-balancing binary trees (red–black trees).

[Ely]

@user2407394 Would you be so kind and elaborate ? I am not sure what is meant.

[cosmos]

Sure, although OP is not very clear in the explanation of his problem. His problem is to have entries sorted by values for same key. For example (1,5) and (1,3) should be sorted to (1,3) and (1,5).. Your answer just mentions sorting the keys in different order..

[Ely]

I see. My answer starts with "You cannot do that" and goes on to explain how multimap is expected to be used in the STL. I believe it is a useful answer. You are right in saying that I did not offer a solution to the OP; this doesn't make an answer less useful IMO. At least I tried to give a hint...

[psybrg]

Keep in mind to switch key value datatypes in declaration of multimap m and multimap R.