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

本文主要是介绍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;类型的数据进行了排序

结果报错：

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官方说明里找到答案。

 我们看类型需求这里：

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结构进行排序，那么我们确实是需要排序，该怎么办呢？这里参考stackoverflow

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++ 踩坑记录：不能使用sort()函数对unordered_map哈希表进行排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！