How can i get the top n keys of std::map based on their values?

Question

How can i get the top n keys of std::map based on their values? Is there a way that i can get a list of say for example the top 10 keys with the biggest value as their values?
Suppose we have a map similar to this :

mymap["key1"]= 10;
mymap["key2"]= 3;
mymap["key3"]= 230;
mymap["key4"]= 15;
mymap["key5"]= 1;
mymap["key6"]= 66;
mymap["key7"]= 10; 

And i only want to have a list of top 10 keys which has a bigger value compared to the other. for example the top 4 for our mymap is

key3
key6
key4 
key1
key10 

note:
the values are not unique, actually they are the number of occurrences of each key. and i want to get a list of most occurred keys

note 2:
if map is not a good candidate and you want to suggest anything, please do it according to the c++11 ,i cant use boost at the time.

note3:
in case of using std::unordered_multimap<int,wstring> do i have any other choices?

Answer 1

The order of a map is based on its key and not its values and cannot be reordered so it is necessary to iterate over the map and maintain a list of the top ten encountered or as commented by Potatoswatter use partial_sort_copy() to extract the top N values for you:

std::vector<std::pair<std::string, int>> top_four(4);
std::partial_sort_copy(mymap.begin(),
                       mymap.end(),
                       top_four.begin(),
                       top_four.end(),
                       [](std::pair<const std::string, int> const& l,
                          std::pair<const std::string, int> const& r)
                       {
                           return l.second > r.second;
                       });

See online demo.

Choosing a different type of container may be more appropriate, boost::multi_index would be worth investigating, which:

... enables the construction of containers maintaining one or more indices with different sorting and access semantics.

Answer 2

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int main(int argc, const char * argv[])
{
    map<string, int> entries;

    // insert some random entries
    for(int i = 0; i < 100; ++i)
    {
        string name(5, 'A' + (char)(rand() % (int)('Z' - 'A') ));
        int number = rand() % 100;

        entries.insert(pair<string, int>(name, number));
    }

    // create container for top 10
    vector<pair<string, int>> sorted(10);

    // sort and copy with reversed compare function using second value of std::pair
    partial_sort_copy(entries.begin(), entries.end(),
                      sorted.begin(), sorted.end(),
                      [](const pair<string, int> &a, const pair<string, int> &b)
    {
        return !(a.second < b.second);
    });

    cout << endl << "all elements" << endl;

    for(pair<string, int> p : entries)
    {
        cout << p.first << "  " << p.second << endl;
    }

    cout << endl << "top 10" << endl;

    for(pair<string, int> p : sorted)
    {
        cout << p.first << "  " << p.second << endl;
    }

    return 0;
}