How to Sort a Map by Value in C++

In this article we will discuss how to sort a map by value in both ascending and descending order.

A Map store the elements in the sorted order of keys.

For example, we have a map of words and its frequency count as key – value pair i.e.

std::map<std::string, int> mapOfWordCount ;

Now lets insert following elements in to this map,

{ "aaa", 10 },
{ "ddd", 41 },
{ "bbb", 62 },
{ "ccc", 13 } 

Map internally stores the above elements in sorted order of keys i.e.

{ "aaa", 10 }
{ "bbb", 62 }
{ "ccc", 13 } 
{ "ddd", 41 }

Therefore, iterating over a map will give pair elements in above order. Now what if want to display items of a map in sorted order of keys. For example for above map we want to display the items in descending order of frequency count i.e.

bbb :: 62
ddd :: 41
ccc :: 13
aaa :: 10

For that we need to sort the entries in map by value.

Sorting a Map by Ascending Order of Value

Map contains pairs of key & value. Where first field of std::pair represents the key and second field represents the value.

Therefore, we can sort the pairs by keeping them in a set and using a comparison logic that compares them with their second field instead of first one.

In the below example we will use a comparator as lambda function that compares the 2 pais using teir second field i.e.

[](std::pair<std::string, int> elem1 ,std::pair<std::string, int> elem2)
			{
				return elem1.second < elem2.second;
			};

We will create a set of pair that will use the above lambda function as compare function and keep the added pairs in sorted order of second field of std::pair.

Then we will copy the elements from map to set and it will store them in sorted order of values.

Let’s see complete example,

#include <iostream>
#include <map>
#include <set>
#include <algorithm>
#include <functional>

int main() {

	// Creating & Initializing a map of String & Ints
	std::map<std::string, int> mapOfWordCount = { { "aaa", 10 }, { "ddd", 41 },
			{ "bbb", 62 }, { "ccc", 13 } };

	// Declaring the type of Predicate that accepts 2 pairs and return a bool
	typedef std::function<bool(std::pair<std::string, int>, std::pair<std::string, int>)> Comparator;

	// Defining a lambda function to compare two pairs. It will compare two pairs using second field
	Comparator compFunctor =
			[](std::pair<std::string, int> elem1 ,std::pair<std::string, int> elem2)
			{
				return elem1.second < elem2.second;
			};

	// Declaring a set that will store the pairs using above comparision logic
	std::set<std::pair<std::string, int>, Comparator> setOfWords(
			mapOfWordCount.begin(), mapOfWordCount.end(), compFunctor);

	// Iterate over a set using range base for loop
	// It will display the items in sorted order of values
	for (std::pair<std::string, int> element : setOfWords)
		std::cout << element.first << " :: " << element.second << std::endl;

	return 0;
}

Output:

aaa :: 10
ccc :: 13
ddd :: 41
bbb :: 62

Sorting a Map by Descending Order of Value

In above example we sorted the contents of a map in ascending order of value. If you want to sort the map contents in descending order then use following lambda function in above example i.e.

[](std::pair<std::string, int> elem1 ,std::pair<std::string, int> elem2)
			{
				return elem1.second > elem2.second;
			};

To compile the above code in linux use following command,

g++ -std=c++11 example.cpp