今天写的以下代码:
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结构进行排序,那么我们确实是需要排序,该怎么办呢?这里参考*
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 中。