How can I sort a std::map first by value, then by key?

Question

I need to sort a std::map by value, then by key. The map contains data like the following:

  1  realistically
  8         really
  4         reason
  3     reasonable
  1     reasonably
  1     reassemble
  1    reassembled
  2      recognize
 92         record
 48        records
  7           recs

I need to get the values in order, but the kicker is that the keys need to be in alphabetical order after the values are in order. How can I do this?

Solution 1

std::map will sort its elements by keys. It doesn't care about the values when sorting.

You can use std::vector<std::pair<K,V>> then sort it using std::sort followed by std::stable_sort:

std::vector<std::pair<K,V>> items;

//fill items

//sort by value using std::sort
std::sort(items.begin(), items.end(), value_comparer);

//sort by key using std::stable_sort
std::stable_sort(items.begin(), items.end(), key_comparer);

The first sort should use std::sort since it is nlog(n), and then use std::stable_sort which is n(log(n))^2 in the worst case.

Note that while std::sort is chosen for performance reason, std::stable_sort is needed for correct ordering, as you want the order-by-value to be preserved.

---

@gsf noted in the comment, you could use only std::sort if you choose a comparer which compares values first, and IF they're equal, sort the keys.

auto cmp = [](std::pair<K,V> const & a, std::pair<K,V> const & b) 
{ 
     return a.second != b.second?  a.second < b.second : a.first < b.first;
};
std::sort(items.begin(), items.end(), cmp);

That should be efficient.

But wait, there is a better approach: store std::pair<V,K> instead of std::pair<K,V> and then you don't need any comparer at all — the standard comparer for std::pair would be enough, as it compares first (which is V) first then second which is K:

std::vector<std::pair<V,K>> items;
//...
std::sort(items.begin(), items.end());

That should work great.

Solution 2

You can use std::set instead of std::map.

You can store both key and value in std::pair and the type of container will look like this:

std::set< std::pair<int, std::string> > items;

std::set will sort it's values both by original keys and values that were stored in std::map.

Solution 3

As explained in Nawaz's answer, you cannot sort your map by itself as you need it, because std::map sorts its elements based on the keys only. So, you need a different container, but if you have to stick to your map, then you can still copy its content (temporarily) into another data structure.

I think, the best solution is to use a std::set storing flipped key-value pairs as presented in ks1322's answer. The std::set is sorted by default and the order of the pairs is exactly as you need it:

3) If lhs.first<rhs.first, returns true. Otherwise, if rhs.first<lhs.first, returns false. Otherwise, if lhs.second<rhs.second, returns true. Otherwise, returns false.

This way you don't need an additional sorting step and the resulting code is quite short:

std::map<std::string, int> m;  // Your original map.
m["realistically"] = 1;
m["really"]        = 8;
m["reason"]        = 4;
m["reasonable"]    = 3;
m["reasonably"]    = 1;
m["reassemble"]    = 1;
m["reassembled"]   = 1;
m["recognize"]     = 2;
m["record"]        = 92;
m["records"]       = 48;
m["recs"]          = 7;

std::set<std::pair<int, std::string>> s;  // The new (temporary) container.

for (auto const &kv : m)
    s.emplace(kv.second, kv.first);  // Flip the pairs.

for (auto const &vk : s)
    std::cout << std::setw(3) << vk.first << std::setw(15) << vk.second << std::endl;

Output:

  1  realistically
  1     reasonably
  1     reassemble
  1    reassembled
  2      recognize
  3     reasonable
  4         reason
  7           recs
  8         really
 48        records
 92         record

Code on Ideone

Note: Since C++17 you can use range-based for loops together with structured bindings for iterating over a map. As a result, the code for copying your map becomes even shorter and more readable:

for (auto const &[k, v] : m)
    s.emplace(v, k);  // Flip the pairs.

Solution 4

std::map already sorts the values using a predicate you define or std::less if you don't provide one. std::set will also store items in order of the of a define comparator. However neither set nor map allow you to have multiple keys. I would suggest defining a std::map<int,std::set<string> if you want to accomplish this using your data structure alone. You should also realize that std::less for string will sort lexicographically not alphabetically.

View more solutions

Comments

[Raxvan]

do you use a std::map to store the data ?

[Wilbert]

Put the std::pair<int, std::string>s into a list, and sort it.

[Trevor Hutto]

@Raxvan yes, its stored in a map.

[Trevor Hutto]

@Wilbert I know that would put the values in order, but then would it keep the keys in alphabetical order after sorting the values?

[Wilbert]

sort on pairs sorts on first, then second item. See here

[Ciro Santilli OurBigBook.com]

value only stackoverflow.com/questions/2699060/stl-map-sort-by-value

[BugShotGG]

@TrevorHutto You can use std::multimap with your values as keys since it allows duplicate keys and will work with std::sort

[Trevor Hutto]

Would the efficiency of the sort be hurt if I add to the vector in alphabetical order like I have it now?

[Trevor Hutto]

Oh I see, it wouldn't because you are sorting on value first?

[Nawaz]

@TrevorHutto: If one (either key or value) is sorted, then you need only stable_sort to sort the other which is not sorted.

[gsf]

That is very bad way to do this. Instead use only one sort but provide compare predicate that compares the keys and in case they are equal compares the value.

[Trevor Hutto]

I don't think I can apply that in this situation. You may tell me differently. But I have functions that add to the map, but if that is already contained in the map it increases the value by one, how can I do that when I'm looking up by the frequency and trying to do something to the string?

[Trevor Hutto]

In other words, I don't think switching the key and value will help me much.

[Trevor Hutto]

I got it working with the last solution in your answer, works like a charm. Thanks.

[Vishal Sahu]

This isn't the case here: the input is map. That might be for various reasons, e.g., values are occurrence of strings in database etc. We can't use set in such cases because set::insert() will treat ("foo", 1) & ("foo", 2) different items.

[Vishal Sahu]

The data is in map. auto cmp = [](std::pair<K,V> const & a, std::pair<K,V> const & b) { return a.second != b.second? a.second < b.second : a.first < b.first; }; std::sort(items.begin(), items.end(), cmp); items is not map.

[BugShotGG]

@Nawaz How there is a better approach: store std::pair<V,K> instead of std::pair<K,V> and then you don't need any comparer at all would even work if you want to extract a value based on key?

[BugShotGG]

@Nawaz I cant see how this would work. Values will be unique so same values will be dropped from map. This should only work with std::multimap

[Nawaz]

@BugShotGG: You asked about extracting value based on key and that sounds like: given a key (which is unique), you want to extract the corresponding value.