Home » C++ STL

C++ STL | Sort a map based on values instead of keys

Learn - how to sort a given map based on values instead of keys in C++ STL with example?
Submitted by Radib Kar, on July 07, 2020

What is a Map in C++ STL?

A map in C++ STL is normally sorted based on its keys. But there may be instances when we require to sort the map based on the values. In this article, we are going to discuss how to sort a map based on the values instead of keys.

Before going in detail let's take an example problem to understand when do we require sorting based on value, not the keys.

A very popular problem is sorting an array or list based on frequency. What we do there we create the map to store the frequency. Now the map is sorted based on the keys, but we require the map to be sorted based on value. So what we can do?

Sorting a map based on values instead of keys

We can use the priority queue and own comparator function to sort the map. Before reading this article please go through our article on how to define your comparator for priority queue in C++ STL.

What is an element of the map?

Say the map is <T,T> where T can be any data type
Each element of the map is a pair<T,T>

Syntax

Syntax for priority queue using STL:

priority_queue<T,vector<T>,decltype(comp)> pq(comp);

Where T is the generic type of the elements and comp is the comparator function
So in the case of map, it would be,

priority_queue<pair<T,T>,vector< pair<T,T>>,decltype(comp)> pq(comp);

as pair<T,T> is the map element

Now, we can define our comparator function as per logic needed.

Let's discuss the problem now that we started which is sorting based on value. If the value for two keys is the same sort based on key.

Say the map is map<int, int> mymap.

Key	value
1	6
2	8
6	3
9	8

Check the below code to see the detailed implementation and output to see the sorted map.

C++ program to sort a map based on values instead of keys

#include <bits/stdc++.h>
using namespace std;

void sort_map_on_value(map<int, int> mymap) {
  // comparator lambda function
  auto comp = [](pair<int, int> a, pair<int, int> b) {
    // comparison logic
    // if value is greater for the first element
    // no need to swap
    if (a.second > b.second) return false;
    // if value is less for the first element
    // need to swap
    else if (a.second < b.second)
      return true;
    else {  // when values are same
      if (a.first < b.first) {
        return false;
      } else
        return true;
    }
  };

  priority_queue<pair<int, int>, vector<pair<int, int> >, decltype(comp)> pq(
      comp);

  for (auto& ij : mymap) {
    pq.push(ij);
  }
  // printing the sorted map
  cout << "key value\n";
  while (!pq.empty()) {
    cout << pq.top().first << " " << pq.top().second << endl;
    pq.pop();
  }
}

void print(map<int, int> mymap) {
  cout << "key value\n";
  for (auto& [key, value] : mymap) cout << key << " " << value << endl;
}

int main() {
  map<int, int> mymap;

  mymap[1] = 6;
  mymap[2] = 8;
  mymap[6] = 3;
  mymap[8] = 2;

  cout << "before sorting map is:\n";
  print(mymap);

  cout << "after sorting based on value map is: \n";
  sort_map_on_value(mymap);

  return 0;
}

Output

before sorting map is:
key value
1 6
2 8
6 3
8 2
after sorting based on value map is:
key value
2 8
1 6
6 3
8 2