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

User · Answer

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 lt  std  pair lt int  std  string gt   gt  items    std  set will sort it s values both by original keys and values that were stored in std  map

User · Answer

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 lt int std  set lt string gt  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

User · Answer

std  map will sort its elements by keys  It doesn t care about the values when sorting    You can use std  vector lt std  pair lt K V gt  gt  then sort it using std  sort followed by std  stable sort   std  vector lt std  pair lt K V gt  gt  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 lt K V gt  const  amp  a  std  pair lt K V gt  const  amp  b           return a second    b second   a second  lt  b second   a first  lt  b first     std  sort items begin    items end    cmp     That should be efficient    But wait  there is a better approach  store std  pair lt V K gt  instead of std  pair lt K V gt  and then you don t need any comparer at all  mdash  the standard comparer for std  pair would be enough  as it compares first  which is V  first then second which is K   std  vector lt std  pair lt V K gt  gt  items        std  sort items begin    items end       That should work great

User · Answer

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  gt  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

User · Answer

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 lt rhs first  returns true  Otherwise  if rhs first lt lhs first  returns false  Otherwise  if lhs second lt 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 lt std  string  int gt  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 lt std  pair lt int  std  string gt  gt  s      The new  temporary  container   for  auto const  amp kv   m      s emplace kv second  kv first       Flip the pairs   for  auto const  amp vk   s      std  cout  lt  lt  std  setw 3   lt  lt  vk first  lt  lt  std  setw 15   lt  lt  vk second  lt  lt  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  amp  k  v    m      s emplace v  k       Flip the pairs

[c++] How can I sort a std::map first by value, then by key?

Examples related to c++

Examples related to algorithm

Examples related to sorting

Examples related to dictionary

Examples related to key