CODEWITHSUNDEEP
c++dictionary
MistyD
MistyD

Reputation: 17223

sorting a map based on value

Suppose I have a std::map<std::string,int> this map stores an id along with a debt amount. I want to know if there was a way for me to obtain the 5 highest (int) values from the map. I know I could iterate through the map and do a custom sort however is there a custom algorithm that might help me accomplish this ? What would the most efficient way be ?

Upvotes: 3

Views: 107

Answers (3)

Richard Hodges
Richard Hodges

Reputation: 69864

you could build a vector of iterators into 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;
}

Upvotes: 0

Ali Mofrad
Ali Mofrad

Reputation: 318

Create a map std::map<int, std::string> and insert all data from old map into this map. Then 5 key from end of new map have the highest value.

Upvotes: 0

Dani
Dani

Reputation: 15069

Only if you save them in another place while inserting to the map and maintain it. A map is just a map.... Getting the highest 5 will be o(N) on the map. if you manage them while inserting you can do it in o(1)

Upvotes: 2

Related Questions