sort an unordered_map using sort()

Question

I am trying to sort an unordered_map using sort() function but I keep getting a compiler error. Can anyone help?

bool comp(pair<char,int> a, pair<char,int> b) {
    return a.second < b.second;
}

void rearrangeKDist(char str[], int d) {
    int n = strlen(str);
    unordered_map<char, int> table;
    for (int i=0; i<n; i++) {
        unordered_map<char, int>::iterator it = table.find(str[i]);   
        if (it == table.end()) {
            table.insert(make_pair(str[i], 1));
        } else {
            it->second = it->second+1;
        }
    }
    for (unordered_map<char, int>::iterator it=table.begin(); it!=table.end(); it++)
        cout<<it->first<<" "<<it->second<<endl;
    sort(table.begin(), table.end(), comp);
    for (unordered_map<char, int>::iterator it=table.begin(); it!=table.end(); it++)
        cout<<it->first<<" "<<it->second<<endl;

}

Answer 1

This is impossible from both a compilation and logical standpoint. From a type standpoint, std::sort requires:

-RandomIt must meet the requirements of ValueSwappable and RandomAccessIterator.
-The type of dereferenced RandomIt must meet the requirements of MoveAssignable and MoveConstructible.

The iterator type on std::unordered_map is a ForwardIterator, not a RandomAccessIterator, so the first requirement is unsatisfied. The type of the dereferenced iterator is pair<const Key, T>, which is not MoveAssignable (can't assign to const), so the second requirement is also unsatisfied.

From a logical standpoint, sorting an unordered container makes no sense. It's unordered. And the complexity guarantees that unordered_map is able to achieve require a very specific ordering that you shouldn't be, and aren't, allowed to mess with.

If you want to "sort" your unordered_map, put them in a vector:

std::vector<std::pair<char, int>> elems(table.begin(), table.end());
std::sort(elems.begin(), elems.end(), comp);