C++, Order map content based on second iter

Question

I have map as below

string word;
int occurance;
std::map< std::string, std::map<string, int> > map;
map[word]["count"] = occurance;

map output using iterator.

for(auto outer_iter=map.begin(); outer_iter!=map.end(); ++outer_iter) {
        for(auto inner_iter=outer_iter->second.begin(); inner_iter!=outer_iter->second.end(); ++inner_iter) {
            std::cout << outer_iter->first << '\t'  << inner_iter->second << std::endl;
        }
    }

I want to display map by ordering the inner_iter->second value.

How can I do it?

Answer 1

The simplest approach to use (unless profiling indicates otherwise) is to simply make an inside-out map when you need to print:

std::multimap<int, std::string> inverse_map;

for(auto outer_iter=map.begin(); outer_iter!=map.end(); ++outer_iter)
{
    for(auto inner_iter=outer_iter->second.begin(); inner_iter!=outer_iter->second.end(); ++inner_iter)
    {
        inverse_map.insert(std::make_pair(inner_iter->second, outer_iter->first));
    }
}

Then you just loop through the inverted map and print normally.

EDIT: I think you can get the double sorting you want by instead using a set of pairs:

std::set<std::pair<int, std::string> > inverse_map;

for(auto outer_iter=map.begin(); outer_iter!=map.end(); ++outer_iter)
{
    for(auto inner_iter=outer_iter->second.begin(); inner_iter!=outer_iter->second.end(); ++inner_iter)
    {
        inverse_map.insert(std::make_pair(inner_iter->second, outer_iter->first));
    }
}

Answer 2

You can insert into a vector and sort the contents accordingly.

Edit: Modified to sort from highest to lowest.

typedef std::pair<std::string, int> hist_item;
std::vector<hist_item> hist;
hist.reserve(map.size());

for(auto outer_iter=map.begin(); outer_iter!=map.end(); ++outer_iter) {
    for(auto inner_iter=outer_iter->second.begin();
        inner_iter!=outer_iter->second.end(); ++inner_iter) {
        hist.push_back(std::make_pair(outer_iter->first, inner_iter->second));
    }
}
std::sort(hist.begin(), hist.end(),
          [](const hist_item &a,const hist_item &b){return a.second>b.second;});
for (auto i = hist.begin(); i!= hist.end(); ++i) {
    std::cout << i->first << '\t' << i->second << std::endl;
}

This mimics your original output. I am not sure of the purpose of the inner map. If you are tracking properties other than "count" in it, your original output and this routine loses that association, and you just get multiple numbers associated with the outer word.