This post will discuss how to sort a map by values in C++.
We know that the std::map container sorts its elements by keys by default and not by values. This post provides an overview of some of the available alternatives to accomplish this.
1. Using std::vector function
The idea is to convert the std::map into a std::vector of key-value pairs and sort that vector according to the increasing order of its pair’s second value.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include <iostream> #include <map> #include <vector> #include <algorithm> typedef std::pair<std::string, int> pair; int main() { // input map std::map<std::string, int> map = { {"two", 2}, {"one", 1}, {"four", 4}, {"three", 3} }; // create an empty vector of pairs std::vector<pair> vec; // copy key-value pairs from the map to the vector std::copy(map.begin(), map.end(), std::back_inserter<std::vector<pair>>(vec)); // sort the vector by increasing the order of its pair's second value // if the second value is equal, order by the pair's first value std::sort(vec.begin(), vec.end(), [](const pair &l, const pair &r) { if (l.second != r.second) { return l.second < r.second; } return l.first < r.first; }); // print the vector for (auto const &pair: vec) { std::cout << '{' << pair.first << "," << pair.second << '}' << std::endl; } return 0; } |
Output:
{one,1}
{two,2}
{three,3}
{four,4}
2. Using std::set function
We can also use std::set instead of std::map. The idea is to insert all the key-value pairs into a std::set constructed using a comparator that orders the pairs by their second value.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
#include <iostream> #include <map> #include <set> // The comparison function for sorting the set by increasing order of its pair's // second value. If the second value is equal, order by the pair's first value struct comp { template<typename T> bool operator()(const T &l, const T &r) const { if (l.second != r.second) { return l.second < r.second; } return l.first < r.first; } }; int main() { // input map std::map<std::string, int> map = { {"two", 2}, {"one", 1}, {"four", 4}, {"three", 3} }; // create an empty vector of pairs std::set<std::pair<std::string, int>, comp> set(map.begin(), map.end()); // print the vector for (auto const &pair: set) { std::cout << '{' << pair.first << "," << pair.second << '}' << std::endl; } return 0; } |
Output:
{one,1}
{two,2}
{three,3}
{four,4}
3. Using std::multimap function
Finally, we can also build another map that uses the original map’s values as keys and the original map’s keys as values. Of course, this will only work if all values in the original map are distinct. If values are not distinct, consider using a std::multimap instead.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <iostream> #include <map> #include <set> #include <algorithm> // Function to convert a `std::map<K, V>` to `std::multimap<V, K>` template<typename K, typename V> std::multimap<V, K> invertMap(std::map<K, V> const &map) { std::multimap<V, K> multimap; for (auto const &pair: map) { multimap.insert(std::make_pair(pair.second, pair.first)); } return multimap; } int main() { // input map std::map<std::string, int> map = { {"two", 2}, {"one", 1}, {"four", 4}, {"three", 3} }; // invert the map std::multimap<int, std::string> multimap = invertMap(map); // print the multimap for (auto const &pair: multimap) { std::cout << '{' << pair.second << "," << pair.first << '}' << std::endl; } return 0; } |
Output:
{one,1}
{two,2}
{three,3}
{four,4}
That’s all about sorting a map by values in C++.