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.
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< std::pair<int, std::string> > items;
std::set
will sort it's values both by original keys and values that were stored in std::map
.
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<rhs.first
, returnstrue
. Otherwise, ifrhs.first<lhs.first
, returnsfalse
. Otherwise, iflhs.second<rhs.second
, returnstrue
. Otherwise, returnsfalse
.
This way you don't need an additional sorting step and the resulting code is quite short:
std::map<std::string, int> 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<std::pair<int, std::string>> s; // The new (temporary) container.
for (auto const &kv : m)
s.emplace(kv.second, kv.first); // Flip the pairs.
for (auto const &vk : s)
std::cout << std::setw(3) << vk.first << std::setw(15) << vk.second << 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 &[k, v] : m)
s.emplace(v, k); // Flip the pairs.