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.

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

Answer 4

You cannot do that. Multimap in C++ STL is ordered and the order cannot/must not be changed (I think at the bottom line it is using a balanced binary tree for the keys I think, not sure though).

What you can do is instantiate a new multimap object passing a comparator that fits your needs (research strict weak order).

By default, less is used, which compares to an ascending order. In the example below you can see greater comparator object passed to the template parameter for the comparator, which compares to descending order. The comparator compares only keys, not values.

You can pass your own comparator if you want or define your own < operator for the type (key) you want to store inside the map.

See example below for usage.

// multimap
#include <map>
#include <iostream>
#include <functional>
#include <iomanip>

using namespace std;

template<class T> void print(T start, T end) {
    while (start != end) {
        std::cout << start->first << ":" << start->second << " ";
        start++;
    }
}

template<class T, class U> void fillMap(multimap<T, T> & m, U start, U end) {
    for (; start != end; ++start) {
        m.insert(pair<T, T>(*start, *start));
    }
}

int main() {
    int t[] = {2, 10, 8, 4, 5, 5, 3, 10, 7, 2};
    //1. standard initialization - default constructor
    multimap<int, int > m1;
    fillMap(m1, t, t + 10);
    //2. iterator constructor
    multimap<int, int> m2(m1.begin(), m1.end());
    //2b. iterator constructor - wrong
    //multimap<int, int> m2(t, t+10);
    print(m2.begin(), m2.end());
    cout << endl;
    //3. copy constructor
    multimap<int, int> m3(m2);
    print(m3.begin(), m3.end());
    cout << endl;

    //4. providing different comparator
    multimap<int, int, greater<int> > m4(m1.begin(), m1.end());
    print(m4.begin(), m4.end());
    cout << endl;
    //5. Not allowed - source and target object are not of the same type 
    //multimap<int, greater<int> > s5 (s3);

    //6. assignment
    multimap<int, int> m6;
    m6 = m3;
    print(m6.begin(), m6.end());
    cout << endl;
    //7. Not allowed - assignment of incompatible multimap objects
    //m6 = m4;
    return 0;
}