Sort cmp function on unordered map

Question

I am trying to sort my unordered map using the values.

This is the code I have:

#include <iostream>
#include <algorithm>
#include <string>
#include <unordered_map>

using namespace std;

bool cmp(pair<char,int> &left, pair<char,int> &right){
    cout<<"Inside comp function"<<endl;
    return left.second < right.second;
}

int main(){
    int len;
    unordered_map<char,int> charCount;
    cin >> len;
    string s,t;
    cin >> s;
    for(int i=0;i<s.length();i++){
        if(charCount.find(s[i]) != charCount.end()){
            charCount[s[i]]++;
        }else{
            charCount.insert(make_pair<char&,int>(s[i],1));
        }
    }
    sort(charCount.begin(),charCount.end(),cmp);
    for(auto& it:charCount){
        cout <<it.first<<" -> "<<it.second<<endl;
    }
    cout<<endl;
    return 0;
}

This is the error I am getting:

In file included from /usr/include/c++/4.9/algorithm:62:0,
                 from solution.cc:21:
/usr/include/c++/4.9/bits/stl_algo.h: In instantiation of 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::__detail::_Node_iterator<std::pair<const char, int>, false, false>; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::pair<char, int>&, std::pair<char, int>&)>]':
/usr/include/c++/4.9/bits/stl_algo.h:4717:78:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = std::__detail::_Node_iterator<std::pair<const char, int>, false, false>; _Compare = bool (*)(std::pair<char, int>&, std::pair<char, int>&)]'
solution.cc:58:49:   required from here
/usr/include/c++/4.9/bits/stl_algo.h:1968:22: error: no match for 'operator-' (operand types are 'std::__detail::_Node_iterator<std::pair<const char, int>, false, false>' and 'std::__detail::_Node_iterator<std::pair<const char, int>, false, false>')
     std::__lg(__last - __first) * 2,
                      ^
/usr/include/c++/4.9/bits/stl_algo.h:1968:22: note: candidates are:
In file included from /usr/include/c++/4.9/bits/stl_algobase.h:67:0,
                 from /usr/include/c++/4.9/bits/stl_tree.h:61,
                 from /usr/include/c++/4.9/map:60,
                 from solution.cc:1:
/usr/include/c++/4.9/bits/stl_iterator.h:328:5: note: template<class _Iterator> typename std::reverse_iterator<_Iterator>::difference_type std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&)
     operator-(const reverse_iterator<_Iterator>& __x,
     ^

Can someone please guide me how to correct the comparator function? I will take down my post if someone feels this is not the right forum to ask this question. Thanks and look forward for your help!!!

`bool cmp(const pair &left, const pair &right){` most probably. — πάντα ῥεῖ, Sep 24 '16 at 20:50
@πάνταῥεῖ It's not that - he's trying to sort an unordered map. — Sergey Kalinichenko, Sep 24 '16 at 20:54

Sergey Kalinichenko · Answer 1 · 2016-09-24T20:58:00.020

Unordered map is what its name implies - it's, well, unordered. You cannot make it ordered because of that.

Unfortunately, the message is too cryptic to explain what is going on. Basically, C++ complains about a property of map iterator required for sorting, which is not there on iterators of unordered containers.

If you want to make an ordered container with the data from unordered map, you need to copy the data into something that you can order, such as a vector or an array:

vector<pair<char,int>> orderedCounts(charCount.begin(),charCount.end());
sort(orderedCounts.begin(), orderedCounts.end(), cmp);

Sort cmp function on unordered map

1 Answers1