C++ 踩坑记录:不能使用sort()函数对unordered_map哈希表进行排序

今天写的以下代码: 

class Solution {
public:
    static bool cmp(pair<string,int> a, pair<string,int> b){
    if (a.second==b.second){
        return a.first<b.first;
    }
    else return a.second>b.second;
    }

    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> S;
        for(string s:words) S[s]++;
        sort(S.begin(),S.end(),cmp);
        vector<string> result;
        auto it = S.begin(); 
        while (k>=0)
        {
            string a =it->first;
            result.push_back(a);
            k--;it++;
        }
        return result;
    }

};

这里自定义了一个cmp排序规则,然后sort(S.begin(),S.end(),cmp);

unordered_map<string, int> S;类型的数据进行了排序

结果报错

C++ 踩坑记录:不能使用sort()函数对unordered_map哈希表进行排序

In file included from prog_joined.cpp:1:
In file included from ./precompiled/headers.h:34:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/algorithm:62:
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_algo.h:1968:22: error: invalid operands to binary expression ('std::__detail::_Node_iterator<std::pair<const std::__cxx11::basic_string<char>, int>, false, true>' and 'std::__detail::_Node_iterator<std::pair<const std::__cxx11::basic_string<char>, int>, false, true>')
                                std::__lg(__last - __first) * 2,
                                          ~~~~~~ ^ ~~~~~~~
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_algo.h:4899:12: note: in instantiation of function template specialization 'std::__sort<std::__detail::_Node_iterator<std::pair<const std::__cxx11::basic_string<char>, int>, false, true>, __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(std::pair<std::__cxx11::basic_string<char>, int>, std::pair<std::__cxx11::basic_string<char>, int>)>>' requested here
      std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
           ^
Line 14: Char 9: note: in instantiation of function template specialization 'std::sort<std::__detail::_Node_iterator<std::pair<const std::__cxx11::basic_string<char>, int>, false, true>, bool (*)(std::pair<std::__cxx11::basic_string<char>, int>, std::pair<std::__cxx11::basic_string<char>, int>)>' requested here
        sort(S.begin(),S.end(),cmp);
        ^
....

....

根本原因是:unordered_map结构压根就不能用sort()对其进行排序

我们可以在std::sort官方说明里找到答案。

C++ 踩坑记录:不能使用sort()函数对unordered_map哈希表进行排序

 我们看类型需求这里:

Type requirements

  • RandomIt must meet the requirements of ValueSwappable and LegacyRandomAccessIterator.
  • The type of dereferenced RandomIt must meet the requirements of MoveAssignable and MoveConstructible.
  • Compare must meet the requirements of Compare.

首先 std::unordered_map的迭代器类型是ForwardIterator,而不是第一点要求的RandomAccessIterator,这里不符合。

此外,对于第二点要求的 dereferenced RandomIt 的类型,unordered_map的是 pair<const Key, T>,它不是MoveAssignable(可移动可分配的),因为const无法变更,因此第二个要求也不符合。

因此,务必注意,不能使用sort()对unordered_map结构进行排序,那么我们确实是需要排序,该怎么办呢?这里参考*

1. 先使用std::set结构对键进行排序,如下所示:

std::unordered_map<int, int> unordered;
std::set<int> keys;
for (auto& it : unordered) keys.insert(it.first);
for (auto& it : keys) {
    std::cout << unordered[it] << ' ';
}

 2. 使用 vector 来存储键值对,在 vector 中对它们进行排序,最后放回 map 中。

上一篇:c++常用数组结构和哈希结构定义


下一篇:c++ map与unordered_map区别及使用