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

by

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.

More Related Contents:

  1. How can I sort an STL map by value?
  2. Insertion sort stops working after million input
  3. How to use Quick Sort to sort an array of strings
  4. How to implement classic sorting algorithms in modern C++?
  5. c++ sort keeping track of indices [duplicate]
  6. The intersection of two sorted arrays
  7. `std::list::sort()` – why the sudden switch to top-down strategy?
  8. Memory-constrained external sorting of strings, with duplicates combined&counted, on a critical server (billions of filenames)
  9. Is it possible to implement lock free map in C++
  10. c++ push reference node to stl list
  11. Which is the fastest algorithm to find prime numbers?
  12. Is there any advantage of using map over unordered_map in case of trivial keys?
  13. Why does the C++ map type argument require an empty constructor when using []?
  14. Rounding up to the nearest multiple of a number
  15. Magic number in boost::hash_combine
  16. Creating all possible k combinations of n items in C++
  17. How do I calculate the week number given a date?
  18. In STL maps, is it better to use map::insert than []?
  19. Where can I get a “useful” C++ binary search algorithm?
  20. What is the default constructor for C++ pointer?
  21. C++ Loop through Map
  22. C++: Converting Hexadecimal to Decimal
  23. Printing prime numbers from 1 through 100
  24. Print all permutation in lexicographic order
  25. Circular lock-free buffer
  26. Efficiently getting all divisors of a given number
  27. Is NaN a valid key value for associative containers?
  28. Sorting a vector of objects by a property of the object
  29. How to use sort() in C++ with custom sort member function?
  30. Finding square root without using sqrt function?

Leave a Comment