How to Sort an Stl Map by Value

Sorting std::map using value

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.

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

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.

How can I sort an STL map by value?

You can build a second map, with the first map's values as keys and the first map's keys as values.

This works only if all values are distinct. If you cannot assume this, then you need to build a multimap instead of a map.

Is there any C++ function to sort a Map?

You can not really change the elements of a std::map. However, you can use std::vector to first copy the elements in the vector and then use std::sort().
Sort elements of std::map.

#include<iostream>
#include <map>
#include <vector>
#include <algorithm>

typedef std::pair<std::string,int> pair;

int main()
{
// input map
std::map<std::string,int> map = {
{"two", 2}, {"one", 1}, {"four", 4}, {"three", 3}
};

// create an empty vector of pairs
std::vector<pair> vec;

// copy key-value pairs from the map to the vector
std::copy(map.begin(),
map.end(),
std::back_inserter<std::vector<pair>>(vec));

// sort the vector by increasing order of its pair's second value
// if second value are equal, order by the pair's first value
std::sort(vec.begin(), vec.end(),
[](const pair& l, const pair& r) {
if (l.second != r.second)
return l.second < r.second;

return l.first < r.first;
});

// print the vector
for (auto const &pair: vec) {
std::cout << '{' << pair.first << "," << pair.second << '}' << '\n';
}

return 0;
}

Sorting a std::map by value before output & destroy

Maps are stored as a tree sorted in key order. You want the 10 smallest (or largest) integer values, and their keys, right?

In that case, iterate the map and put all the key-value pairs in a vector of pairs (std::vector<std::pair<std::string, int> >). I think you can just use the two-iterator-arg constructor of std::vector for this. Then use std::partial_sort on the vector. Specify a comparator to partial_sort, which compares pairs by just comparing the value int, ignoring the key string. Then you have the 10 pairs you want at the start of the vector, and the rest of the vector contains the remaining pairs in an unspecified order.

Code (untested):

typedef std::pair<std::string, int> mypair;

struct IntCmp {
bool operator()(const mypair &lhs, const mypair &rhs) {
return lhs.second < rhs.second;
}
};

void print10(const std::map<std::string,int> &mymap) {
std::vector<mypair> myvec(mymap.begin(), mymap.end());
assert(myvec.size() >= 10);
std::partial_sort(myvec.begin(), myvec.begin() + 10, myvec.end(), IntCmp());

for (int i = 0; i < 10; ++i) {
std::cout << i << ": " << myvec[i].first
<< "-> " << myvec[i].second << "\n";
}
}

Note that if there are several strings with the same value, either side of the limit of 10, then it's not specified which ones you get. You can control this by having your comparator look at the string too, in cases where the integers are equal.

std::map sort by size of value (set int )

You can't change the sort order of an existing map.

Illustrating one way to create an index into the map in the form of a sorted vector...

std::vector<std::pair<int, int>> size_key;

for (auto& x : mymap)
size_key.emplace_back(x.second.size(), x.first);
std::sort(std::begin(size_index), std::end(size_index));

// work's done above - just display the results to illustrate access...

for (auto& sk : size_key)
{
std::cout << "with size " << sk.first
<< ", value " << mymap[sk.second].first << '\n';
for (auto& n : mymap[sk.second].second)
std::cout << " " << n << '\n'
}

Also, if I flip the map, as some posts suggest...

Not a good idea: just "flipping" key and value won't help without also changing the sort comparitor, you'd need a multimap if set sizes could be repeated, and slower and more wasteful of memory than building an index as above (unless you can throw away the original mymap once the re-ordered multimap is constructed).

Sorting an STL Map from lowest to greatest value

Something along these lines perhaps:

std::map<std::string, int> old_map = ...;  // initialized somehow
std::map<int, std::string> new_map;

std::transform(old_map.begin(), old_map.end(),
std::inserter(new_map, new_map.end()),
[](decltype(old_map)::iterator it) {
return std::make_pair(it->second, it->first);
}
);

How to sort the map based on value in c++ using stl?

Solution using priority_queue

  class compare {
public:
bool operator()(pair<int,struct node *> a, pair<int,struct node *> b) {
if(a.second->count>b.second->count)
return 0;
if(a.second->count==b.second->count && a.second->index<b.second->index)
return 0;
return 1;
}
};

priority_queue<pair<int,struct node *>, vector<pair<int,struct node *> >, compare > pq(m1.begin(),m1.end());


Related Topics



Leave a reply



Submit