c++algorithmsortingdictionarykey

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


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

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