Sorting std::map using value

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<long, double> 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?

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.

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<std::pair<int, int>> pairs;
for (auto itr = freq.begin(); itr != freq.end(); ++itr)
    pairs.push_back(*itr);

sort(pairs.begin(), pairs.end(), [=](std::pair<int, int>& a, std::pair<int, int>& b)
{
    return a.second < b.second;
}
);

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.

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 <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  map<int, int> m;
  m[11] = 1;
  m[22] = 2;
  m[33] = 3;

  vector<pair<int, int> > v;
  copy(m.begin(),
       m.end(),
       back_inserter<vector<pair<int, int> > >(v));

  for (size_t i = 0; i < v.size(); ++i) {
    cout << v[i].first << " , " << v[i].second << "\n";
  }

  return 0;
};

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 <typename A, typename B>
multimap<B, A> flip_map(map<A,B> & src) {

    multimap<B,A> dst;

    for(map<A, B>::const_iterator it = src.begin(); it != src.end(); ++it)
        dst.insert(pair<B, A>(it -> second, it -> first));

    return dst;
}

Here is an example program that shows all the key-value pairs being preserved after performing the flip.

#include <iostream>
#include <map>
#include <string>
#include <algorithm>

using namespace std;

template <typename A, typename B>
multimap<B, A> flip_map(map<A,B> & src) {

    multimap<B,A> dst;

    for(typename map<A, B>::const_iterator it = src.begin(); it != src.end(); ++it)
        dst.insert(pair<B, A>(it -> second, it -> first));

    return dst;
}

int main() {

    map<string, int> test;
    test["word"] = 1;
    test["spark"] = 15;
    test["the"] = 2;
    test["mail"] = 3;
    test["info"] = 3;
    test["sandwich"] = 15;

    cout << "Contents of original map:\n" << endl;
    for(map<string, int>::const_iterator it = test.begin(); it != test.end(); ++it)
        cout << it -> first << " " << it -> second << endl; 

    multimap<int, string> reverseTest = flip_map(test);

    cout << "\nContents of flipped map in descending order:\n" << endl;
    for(multimap<int, string>::const_reverse_iterator it = reverseTest.rbegin(); it != reverseTest.rend(); ++it)
        cout << it -> first << " " << it -> second << endl; 

    cout << endl;
}

Result:

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<long, double> testMap;
map<double, long> 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.

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 <typename M, typename S> 
void MapToSet( const  M & m, S & s )
{
    typename M::const_iterator end = m.end();
    for( typename M::const_iterator it = m.begin(); it != end ; ++it )
    {
        s.insert( it->second );
    }
}

One caveat: if the map contains different keys with the same value, they will not be inserted into the set and be lost.

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.

Another solution would be the usage of std::make_move_iterator to build a new vector (C++11 )

    int main(){

      std::map<std::string, int> map;
       //Populate map

      std::vector<std::pair<std::string, int>> 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 > 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
  }

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)

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 <= 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& kv : word_map) {
    if (kv.second > max_value) {
      max_value = kv.second;
      max_word = kv.first;
    }
  }
  // Erase this entry and print.
  word_map.erase(max_word);
  cout << "Top:" << i << " Count:" << max_value << " Word:<" << max_word << ">" <<     endl;
}

An alternative way to sorting a std::map without any additional copying or transformation is to redefine the std::map with different Compare type:

namespace nonstd {
template <class Key,
          class T,
          class Compare = std::greater<T>,
          class Allocator = std::allocator<std::pair<Key const, T>>
          >
using map = std::map<Key, T, Compare, Allocator>;
}

int main() {
  nonstd::map<char, std::size_t> const values = {
    {'A', 3}, {'B', 2}, {'C', 5}
  };

  for (auto const& value : values) {
    std::clog << value.first << " : " << value.second << std::endl;
  }
}

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<int, double> testMap = { {1,9.1}, {2, 8.0}, {3, 7.0}, {4,10.5} };
auto cmp = [](const double &lhs,
              const double &rhs)->bool
{
    return lhs < rhs;
};
std::multimap<double, int, decltype(cmp)> mmap(cmp);
for (auto item : testMap)
    mmap.insert(make_pair(item.second, item.first));

Just put the values into the vector and sort the vector on the value of each map key.

#include <bits/stdc++.h>
using namespace std;

int main()
{

    std::map<std::string, int> mymap;
    mymap.insert(std::make_pair("earth", 5));
    mymap.insert(std::make_pair("moon", 33));
    mymap.insert(std::make_pair("sun", 2));

    vector<std::pair<std::string, int>> myvector {mymap.begin(), mymap.end()};


    sort(myvector.begin(), myvector.end(), [](std::pair<std::string, int> l, std::pair<std::string, int> r)
    {
        return l.second < r.second;
    });
  
    return 0;
}