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?

Answer 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.

Answer 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.

Answer 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.

Answer 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.

Answer 5

EDIT: The other two answers make a good point. I'm assuming that you want to order them into some other structure, or in order to print them out.

"Best" can mean a number of different things. Do you mean "easiest," "fastest," "most efficient," "least code," "most readable?"

The most obvious approach is to loop through twice. On the first pass, order the values:

if(current_value > examined_value)
{
    current_value = examined_value
    (and then swap them, however you like)
}

Then on the second pass, alphabetize the words, but only if their values match.

if(current_value == examined_value)
{
    (alphabetize the two)
}

Strictly speaking, this is a "bubble sort" which is slow because every time you make a swap, you have to start over. One "pass" is finished when you get through the whole list without making any swaps.

There are other sorting algorithms, but the principle would be the same: order by value, then alphabetize.