compartor function in sort

[funprogrammer]

Can someone please help me with the sort comparator function? I am getting below error:

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,
     ^
/usr/include/c++/4.9/bits/stl_iterator.h:328:5: note:   template argument deduction/substitution failed:
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:1968:22: note:   'std::__detail::_Node_iterator<std::pair<const char, int>, false, false>' is not derived from 'const std::reverse_iterator<_Iterator>'
     std::__lg(__last - __first) * 2,
                      ^
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:380:5: note: template<class _IteratorL, class _IteratorR> decltype ((__y.base() - __x.base())) std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)
     operator-(const reverse_iterator<_IteratorL>& __x,
     ^
/usr/include/c++/4.9/bits/stl_iterator.h:380:5: note:   template argument deduction/substitution failed:
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:1968:22: note:   'std::__detail::_Node_iterator<std::pair<const char, int>, false, false>' is not derived from 'const std::reverse_iterator<_Iterator>'
     std::__lg(__last - __first) * 2,
                      ^
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:1121:5: note: template<class _IteratorL, class _IteratorR> decltype ((__x.base() - __y.base())) std::operator-(const std::move_iterator<_Iterator>&, const std::move_iterator<_IteratorR>&)
     operator-(const move_iterator<_IteratorL>& __x,
     ^
/usr/include/c++/4.9/bits/stl_iterator.h:1121:5: note:   template argument deduction/substitution failed:
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:1968:22: note:   'std::__detail::_Node_iterator<std::pair<const char, int>, false, false>' is not derived from 'const std::move_iterator<_Iterator>'
     std::__lg(__last - __first) * 2,
                      ^
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:1128:5: note: template<class _Iterator> decltype ((__x.base() - __y.base())) std::operator-(const std::move_iterator<_Iterator>&, const std::move_iterator<_Iterator>&)
     operator-(const move_iterator<_Iterator>& __x,
     ^
/usr/include/c++/4.9/bits/stl_iterator.h:1128:5: note:   template argument deduction/substitution failed:
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:1968:22: note:   'std::__detail::_Node_iterator<std::pair<const char, int>, false, false>' is not derived from 'const std::move_iterator<_Iterator>'
     std::__lg(__last - __first) * 2,
                      ^
In file included from /usr/include/c++/4.9/deque:64:0,
                 from solution.cc:6:
/usr/include/c++/4.9/bits/stl_deque.h:335:5: note: template<class _Tp, class _Ref, class _Ptr> typename std::_Deque_iterator<_Tp, _Ref, _Ptr>::difference_type std::operator-(const std::_Deque_iterator<_Tp, _Ref, _Ptr>&, const std::_Deque_iterator<_Tp, _Ref, _Ptr>&)
     operator-(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
     ^
/usr/include/c++/4.9/bits/stl_deque.h:335:5: note:   template argument deduction/substitution failed:
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:1968:22: note:   'std::__detail::_Node_iterator<std::pair<const char, int>, false, false>' is not derived from 'const std::_Deque_iterator<_Tp, _Ref, _Ptr>'
     std::__lg(__last - __first) * 2,

My code is

#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;
}

[Chervil]

The only way I could get this to work was to create a vector from the unordered map, and then sort the vector instead.

    std::vector< std::pair<char, int>> vec(charCount.begin(), charCount.end());

[keskiverto]

The http://en.cppreference.com/w/cpp/algorithm/sort
says:

template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );

RandomIt must meet the requirements of ValueSwappable and RandomAccessIterator.

The std::unordered_map's iterators are not RandomAccessIterators.


Another workaround:
http://www.cplusplus.com/forum/beginner/168761/

[funprogrammer]

Hello Chervil,
Thanks for the reply. How did you sort the vector? Using a comparator function like above?

[Chervil]

Yes, more or less the same code. The only difference was the two parameters left and right of the cmp() function needed to be declared as const.

@keskiverto
Thanks for the clarification and links.

[funprogrammer]

@keskiverto: What if I changed unorderd_map to map? Are map iterators RandomAccessIterators?

[keskiverto]

Read: http://www.cplusplus.com/reference/map/map/