How can I sort an STL map by value?

Question

How can I implement the sorting of STL cards by value?

For example, I have a map m :

 map<int, int> m; m[1] = 10; m[2] = 5; m[4] = 6; m[6] = 1; 

I would like to sort this map by m value. So, if I print a map, I would like to get the result as follows:

 m[6] = 1 m[2] = 5 m[4] = 6 m[1] = 10 

How can I sort a map this way? Is there a way I can handle the key and value with sorted values?

Answer 1

You can create a second map with the first map values ​​as keys and the first map keys as values.

This only works if all values ​​are different. If you cannot allow this, you need to create a multimap instead of a map.

Answer 2

First, unload all the key-value pairs into set<pair<K, V> > , where set built with less than a functor that compares only a pair of the second value. That way your code is still working, even if your values ​​are not all different.

Or discard key-value pairs in vector<pair<K, V> > , and then sort this vector with the same less than a functor subsequently.

Answer 3

I wonder how I can implement sorting by STL by value.

You cannot, by definition . A map is a data structure that sorts its element by key.

Answer 4

You should use Boost.Bimap for this kind of thing.

Answer 5

I just made a similar question in my C ++ book. The answer I came up with may not be very effective:

 int main() { string s; map<string, int> counters; while(cin >> s) ++counters[s]; //Get the largest and smallest values from map int beginPos = smallest_map_value(counters); int endPos = largest_map_value(counters); //Increment through smallest value to largest values found for(int i = beginPos; i <= endPos; ++i) { //For each increment, go through the map... for(map<string, int>::const_iterator it = counters.begin(); it != counters.end(); ++it) { //...and print out any pairs with matching values if(it->second == i) { cout << it->first << "\t" << it->second << endl; } } } return 0; } //Find the smallest value for a map<string, int> int smallest_map_value(const map<string, int>& m) { map<string, int>::const_iterator it = m.begin(); int lowest = it->second; for(map<string, int>::const_iterator it = m.begin(); it != m.end(); ++it) { if(it->second < lowest) lowest = it->second; } return lowest; } //Find the largest value for a map<string, int> int largest_map_value(const map<string, int>& m) { map<string, int>::const_iterator it = m.begin(); int highest = it->second; for(map<string, int>::const_iterator it = m.begin(); it != m.end(); ++it) { if(it->second > highest) highest = it->second; } return highest; } 

Answer 6

Based on the idea of ​​@swegi, I implemented the solution in C ++ 11 using multimap :

 map<int, int> m = {{1, 10}, {2, 5}, {4, 6}, {6, 1}}; multimap<int, int> mm; for(auto const &kv : m) mm.insert(make_pair(kv.second, kv.first)); // Flip the pairs. for(auto const &kv : mm) cout << "m[" << kv.second << "] = " << kv.first << endl; // Flip the pairs again. 

Ideone Code

I also implemented a C ++ 11 solution based on @Chris idea using a vector of pairs. For proper sorting, I provide lambda expression as a comparison function:

 map<int, int> m = {{1, 10}, {2, 5}, {4, 6}, {6, 1}}; using mypair = pair<int, int>; vector<mypair> v(begin(m), end(m)); sort(begin(v), end(v), [](const mypair& a, const mypair& b) { return a.second < b.second; }); for(auto const &p : v) cout << "m[" << p.first << "] = " << p.second << endl; 

Ideon code

The first solution is more compact, but both solutions should have approximately the same performance. The insert in multimap has the value O (log n), but this needs to be done for n entries, resulting in O (n log n). Sorting the vector in the second solution also results in O (n log n).

I also tried @Chris's idea of ​​using a set of pairs. However, this will not work if the values ​​are not all different. Using a functor that only compares the second element of a pair does not help. If you first enter make_pair(1, 1) into the set, and then try to insert make_pair(2, 1) , then the second pair will not be inserted, because both pairs are considered identical to this set. You can see this effect here on Ideone .

Answer 7

Create another map, provide a less () function based on the value of not key, and the function should return true if value1 <= value2 (not strictly <). In this case, items with fuzzy values ​​can also be sorted.

Answer 8

I found this in this pointer . In the example, std :: map <std :: string, int> is sorted by all int values.

 #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; }