Sorting std map using value

Question

I need to sort an std  map by value rather than by key  Is there an easy way to do it   I got one solution from the follwing thread  std  map sort by data   Is there a better solution    map lt long  double gt  testMap     some code to generate the values in the map   sort testMap begin    testMap end         is there any function like this to sort the map

User · Accepted Answer

Even though correct answers have already been posted, I thought I'd add a demo of how you can do this cleanly:

template<typename A, typename B>
std::pair<B,A> flip_pair(const std::pair<A,B> &p)
{
    return std::pair<B,A>(p.second, p.first);
}

template<typename A, typename B>
std::multimap<B,A> flip_map(const std::map<A,B> &src)
{
    std::multimap<B,A> dst;
    std::transform(src.begin(), src.end(), std::inserter(dst, dst.begin()), 
                   flip_pair<A,B>);
    return dst;
}

int main(void)
{
    std::map<int, double> src;

    ...    

    std::multimap<double, int> dst = flip_map(src);
    // dst is now sorted by what used to be the value in src!
}

Generic Associative Source (requires C++11)

If you're using an alternate to std::map for the source associative container (such as std::unordered_map), you could code a separate overload, but in the end the action is still the same, so a generalized associative container using variadic templates can be used for either mapping construct:

// flips an associative container of A,B pairs to B,A pairs
template<typename A, typename B, template<class,class,class...> class M, class... Args>
std::multimap<B,A> flip_map(const M<A,B,Args...> &src)
{
    std::multimap<B,A> dst;
    std::transform(src.begin(), src.end(),
                   std::inserter(dst, dst.begin()),
                   flip_pair<A,B>);
    return dst;
}

This will work for both std::map and std::unordered_map as the source of the flip.

User · Answer

Flipped structure might no longer be a map but rather a multimap  thus in the flip map example above not all elements from B will necessarily appear in the resulting data structure

User · Answer

In the following sample code  I wrote an simple way to output top words in an word map map where key is string  word  and value is unsigned int  word occurrence    The idea is simple  find the current top word and delete it from the map  It s not optimized  but it works well when the map is not large and we only need to output the top N words  instead of sorting the whole map   const int NUMBER OF TOP WORDS   300  for  int i   1  i  lt   NUMBER OF TOP WORDS  i        if  word map empty        break       Go through the map and find the max item    int max value   0    string max word         for  const auto amp  kv   word map        if  kv second  gt  max value          max value   kv second        max word   kv first                 Erase this entry and print    word map erase max word     cout  lt  lt   Top    lt  lt  i  lt  lt    Count    lt  lt  max value  lt  lt    Word  lt    lt  lt  max word  lt  lt    gt    lt  lt      endl

User · Answer

A std  map sorted by it s value is in essence a std  set  By far the easiest way is to copy all entries in the map to a set  taken and adapted from here   template  lt typename M  typename S gt   void MapToSet  const  M  amp  m  S  amp  s         typename M  const iterator end   m end        for  typename M  const iterator it   m begin    it    end     it                 s insert  it- gt second              One caveat  if the map contains different keys with the same value  they will not be inserted into the set and be lost

User · Answer

You can t sort a std  map this way  because a the entries in the map are sorted by the key  If you want to sort by value  you need to create a new std  map with swapped key and value   map lt long  double gt  testMap  map lt double  long gt  testMap2      Insert values from testMap to testMap2    The values in testMap2 are sorted by the double value   Remember that the double keys need to be unique in testMap2 or use std  multimap

User · Answer

Another solution would be the usage of std  make move iterator to build a new vector  C  11        int main           std  map lt std  string  int gt  map           Populate map        std  vector lt std  pair lt std  string  int gt  gt  v  std  make move iterator begin map                                          std  make move iterator end map               Create a vector with the map parameters         sort begin v   end v                   auto p1  auto p2  return p1 second  gt  p2 second               Using sort   lambda function to return an ordered vector            in respect to the int value that is now the 2nd parameter            of our newly created vector v

User · Answer

If you want to present the values in a map in sorted order  then copy the values from the map to vector and sort the vector

User · Answer

In this context  we should convert map to multimap  I think convert map to set is not good because we will lose many information in case of there is many duplicate values in the original map  Here is my solution  I defined the less than comparator that sort by value  cmp function   We can customize the cmp function as our demand    std  map lt int  double gt  testMap      1 9 1    2  8 0    3  7 0    4 10 5     auto cmp      const double  amp lhs                const double  amp rhs - gt bool       return lhs  lt  rhs     std  multimap lt double  int  decltype cmp  gt  mmap cmp   for  auto item   testMap      mmap insert make pair item second  item first

User · Answer

I like the the answer from Oli  flipping a map   but seems it has a problem  the container map does not allow two elements with the same key   A solution is to make dst the type multimap  Another one is to dump src into a vector and sort the vector  The former requires minor modifications to Oli s answer  and the latter can be implemented using STL copy concisely   include  lt iostream gt   include  lt utility gt   include  lt map gt   include  lt vector gt   include  lt algorithm gt   using namespace std   int main       map lt int  int gt  m    m 11    1    m 22    2    m 33    3     vector lt pair lt int  int gt   gt  v    copy m begin           m end           back inserter lt vector lt pair lt int  int gt   gt   gt  v       for  size t i   0  i  lt  v size      i        cout  lt  lt  v i  first  lt  lt         lt  lt  v i  second  lt  lt    n          return 0

User · Answer

To build on Oli s solution  https   stackoverflow com a 5056797 2472351  using multimaps  you can replace the two template functions he used with the following   template  lt typename A  typename B gt  multimap lt B  A gt  flip map map lt A B gt   amp  src         multimap lt B A gt  dst       for map lt A  B gt   const iterator it   src begin    it    src end      it          dst insert pair lt B  A gt  it - gt  second  it - gt  first         return dst      Here is an example program that shows all the key-value pairs being preserved after performing the flip    include  lt iostream gt   include  lt map gt   include  lt string gt   include  lt algorithm gt   using namespace std   template  lt typename A  typename B gt  multimap lt B  A gt  flip map map lt A B gt   amp  src         multimap lt B A gt  dst       for typename map lt A  B gt   const iterator it   src begin    it    src end      it          dst insert pair lt B  A gt  it - gt  second  it - gt  first         return dst     int main          map lt string  int gt  test      test  word     1      test  spark     15      test  the     2      test  mail     3      test  info     3      test  sandwich     15       cout  lt  lt   Contents of original map  n   lt  lt  endl      for map lt string  int gt   const iterator it   test begin    it    test end      it          cout  lt  lt  it - gt  first  lt  lt       lt  lt  it - gt  second  lt  lt  endl        multimap lt int  string gt  reverseTest   flip map test        cout  lt  lt    nContents of flipped map in descending order  n   lt  lt  endl      for multimap lt int  string gt   const reverse iterator it   reverseTest rbegin    it    reverseTest rend      it          cout  lt  lt  it - gt  first  lt  lt       lt  lt  it - gt  second  lt  lt  endl        cout  lt  lt  endl      Result

User · Answer

I needed something similar  but the flipped map wouldn t work for me   I just copied out my map  freq below  into a vector of pairs  then sorted the pairs however I wanted   std  vector lt std  pair lt int  int gt  gt  pairs  for  auto itr   freq begin    itr    freq end      itr      pairs push back  itr    sort pairs begin    pairs end        std  pair lt int  int gt  amp  a  std  pair lt int  int gt  amp  b        return a second  lt  b second

User · Answer

U can consider using boost  bimap that might gave you a feeling that map is sorted by key and by values simultaneously  this is not what really happens  though

[c++] Sorting std::map using value

Examples related to c++

Examples related to dictionary

Examples related to std