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