map sorting in c++ by the frequencies

Question

I have a map containing the following values:

index frequency
65      1
67      5
47      3

In here i want to sort them by frequency in ascending order and print them... Here's my code regarding to this problem:

#include<bits/stdc++.h>
using    namespace    std;
int    main()
{
    string    s;
    while(getline(cin,s))
    {
        map<int,int>m;
        map<int,int>::iterator    it;
        for(int i=0; i<s.size(); i++)
            m[s[i]]++;
        for(it=m.begin(); it!=m.end(); it++)
            cout<<it->first<<" "<<it->second<<endl;
    }
    return    0;
}

You shouldn't do this `#include` and neither you should do that `using namespace std;` — πάντα ῥεῖ, Dec 31 '14 at 13:13
@πάνταῥεῖ: Could you also explain why? It makes sense to me, but it's not very clear why he shouldn't. Next time it's another file and/or namespace that is being included. — Caramiriel, Dec 31 '14 at 13:17
@Caramiriel Well, that was just a side note comment, not an answer. I'm pretty sure you'll be able to find one here. — πάντα ῥεῖ, Dec 31 '14 at 13:19
possible duplicate of [Sorting std::map using value](http://stackoverflow.com/questions/5056645/sorting-stdmap-using-value) — Barry, Dec 31 '14 at 13:19

score 4 · Accepted Answer · answered Dec 31 '14 at 13:23

I encorage you to think a little differently about this problem.

While you currently have a map, i suggest that (atleast for doing this task) to extract the key value pairs.

#include <algorithm>

map<int,int> m;
//fill in
std::vector<std::pair<int,int>> values(m.begin(),m.end());
auto cmp = [](const std::pair<int,int>& l, std::pair<int,int>& r) { return l.second < r.second;};
std::sort(values.begin(),values.end(),cmp);

The above is using c++11 but you can easily make cmp a struct. Complexity is O(nlgn) in time, O(n) in space.

If you have c++11 available, I would also suggest using std::unordered_map instead of std::map, which will have O(1) amoratized insertion and removal rather than O(lg(n)).

map sorting in c++ by the frequencies

1 Answers1