Sorting the map by value
Suppose I have std::map<std::string,int>
, this card stores an ID along with the amount owed. I want to know if there is a way to get the 5 highest (int) values ββfrom the map. I know I can scroll the map and do normal sorting, but do you have an algorithm that can help me with this? What's the most efficient way?
+3
source to share
3 answers
you could create a vector of iterators on the map:
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int main()
{
// make some data
using data_map_type = map<string, int>;
data_map_type data_map = {
{ "a", 10 },
{ "b", 5 },
{ "c", 3 },
{ "d", 3 },
{ "e", 4 },
{ "f", 1 },
{ "g", 2 },
{ "h", 5 },
{ "i", 0 },
{ "j", 2 },
{ "k", 1 },
};
// build reverse index (initially unordered)
std::vector<data_map_type::const_iterator> second_index;
for(auto it = begin(data_map) ; it != end(data_map) ; ++it)
second_index.push_back(it);
// order the secondary index by descending debt amount
sort(begin(second_index),
end(second_index),
[](const data_map_type::const_iterator& l,
const data_map_type::const_iterator& r)
{
return l->second > r->second;
});
// emit the top 5 (or fewer)
const auto limit = std::min(second_index.size(), size_t(5));
cout << "top " << limit << " entries:" << endl;
for(size_t i = 0 ; i < limit ; ++i)
{
cout << "key=" << second_index[i]->first << ", value=" << second_index[i]->second << endl;
}
return 0;
}
0
source to share