In this post, we will discuss how to sort a map by values in C++.
We know that 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
The idea is to convert the std::map into a std::vector of key-value pairs and sort that vector according to 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 |
#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 a 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 order of its pair's second value // if second value are 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 << '}' << '\n'; } return 0; } |
Output:
{one,1}
{two,2}
{three,3}
{four,4}
2. Using std::set
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 order 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 |
#include <iostream> #include <map> #include <set> // Comparison function for sorting the set by increasing order of its pair's // second value. If second value are 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 a 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 << '}' << '\n'; } return 0; } |
Output:
{one,1}
{two,2}
{three,3}
{four,4}
3. Using std::multimap
Finally, we can also build another map that uses original map’s values as keys and 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 << '}' << '\n'; } return 0; } |
Output:
{one,1}
{two,2}
{three,3}
{four,4}
(4 votes, average: 4.00 out of 5)
Loading...
Thanks for reading.
Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply
Great solutions 🙂