How to sort a std::map by ascending order of value?

Question

I'm trying to figure out how to sort std::map by ascending order of value.

My Code :

#include <iostream>
#include <map>
#include <string>
#include <iterator>

void printMapByOrder(std::map<std::string, int> mapOfPlanets)
{
    //what should be here?
}

int main() {

    std::map<std::string, int> mapOfPlanets;
    mapOfPlanets["earth"] = 12;
    mapOfPlanets["jupiter"] = 142;
    mapOfPlanets["mars"] = 6;
    mapOfPlanets["mercury"] = 4;
    mapOfPlanets["neptune"] = 49;
    mapOfPlanets["pluto"] = 2;
    mapOfPlanets["saturn"] = 120;
    mapOfPlanets["uranus"] = 51;
    mapOfPlanets["venus"] = 12;
    printMapByOrder(mapOfPlanets);
}

The Result I want :

 pluto : 2
 mercury : 4
 mars : 6
 earth : 12
 venus : 12
 neptune : 49
 uranus : 51
 saturn : 120
 jupiter : 142

Is this possible to do this with std::map?

do you want to sort the map in ascending order (what your text says and what the dupe is about) or do you want to sort the map descending and only print its elements in ascending order (what your code suggests) — 463035818_is_not_an_ai, Aug 28 '18 at 10:19
@user463035818 I want to sort the map in ascending order like my text and code suggests. — Zack Lee, Aug 28 '18 at 10:21
well the code suggests something different, otherwise the "//what should be here" is in the wrong place. Printing elements of a map in order is the same no matter how they are sorted. Nevermind, the dupe has the answer for you — 463035818_is_not_an_ai, Aug 28 '18 at 10:22
The suggested dupe was wrong. This question is about sorting the values not the keys. — john, Aug 28 '18 at 10:30
@ZackLee One simple answer is to copy the map elements into a vector and sort the vector. Then print the vector. — john, Aug 28 '18 at 10:31
@john Thank you but I would like to know more performant solution since this will be called every frame. — Zack Lee, Aug 28 '18 at 10:32
@ZackLee Sounds like you are looking for something like this, https://www.boost.org/doc/libs/1_68_0/libs/multi_index/doc/index.html — john, Aug 28 '18 at 10:40
Sorting a vector with `std::sort` and a predicate IS the better performing solution. How many entries are we talking about? For a dozen, it won’t matter what you do. First benchmark, then worry about performance. — Khouri Giordano, Aug 28 '18 at 10:45
@cristid9 the map would be sorted with respect to the `pair` as a whole, not the keys and values separately. — meowgoesthedog, Aug 28 '18 at 10:50
@KhouriGiordano Usually from 100 to 500 entries will be used. — Zack Lee, Aug 28 '18 at 10:54
So that’s a few kilobytes of RAM. I would start with whatever is easier to code and understand and then work from there. Benchmarking will tell you what’s fast enough. — Khouri Giordano, Aug 28 '18 at 11:15

score 4 · Answer 1 · answered Aug 28 '18 at 11:14

No. Its not possible to sort a map by its values.

One possible solution:

void printMapByOrder(std::map<std::string, int> mapOfPlanets)
{
    std::vector < std::pair<std::string, int> > planets(mapOfPlanets.begin(), mapOfPlanets.end());
    std::sort(planets.begin(), planets.end(), [](auto lhs, auto rhs) {return lhs.second < rhs.second; });
    //print planets
}

score 3 · Accepted Answer · answered Aug 29 '18 at 09:49

A std::map is ordered by its keys, and that can't be changed (after all, the point of a map is fast access by key). You could, however, create a container of pointers to your map elements, and sort that for printing. You'll want to pass your map by const reference, so that your pointers won't be invalidated:

#include <algorithm>
#include <vector>

void printMapByOrder(const std::map<std::string, int>& mapOfPlanets)
{
    using element = typename std::map<std::string, int>::value_type;
    std::vector<const element*> sorted;
    sorted.reserve(mapOfPlanets.size());
    for (auto& planet: mapOfPlanets)
        sorted.push_back(&planet);

    # sort by value
    std::sort(sorted.begin(), sorted.end(),
              [](auto *a, auto *b) {
                  return std::tie(a->second, a->first)
                      <  std::tie(b->second, b->first);
              });

    # print results
    std::transform(sorted.begin(), sorted.end(),
                   std::ostream_iterator<std::string>(std::cout),
                   [](const auto *p) {
                       return p->first + ": "
                           + std::to_string(p->second) + '\n';
                   });
}

How to sort a std::map by ascending order of value?

2 Answers2