K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
现有需求:统计一篇英文文章中所有单词的出现频次,最终仅需按频次高低排序输出结果,忽略单词预处理的开销,设单词总数量为n,不同单词的数量为m。
使用std::map<std::string, int>实现统计功能,插入所有单词的平均总时间复杂度为O(n log m),是该场景下的最优选择
使用std::unordered_map<std::string, int>实现统计时,若要获取单词"hello"的出现次数,只能先调用count("hello")判断存在后再通过[]运算符取值,无法直接使用at()方法取值
如果需要将自定义结构体作为unordered_map的key,当标准库没有提供该类型的默认哈希函数时,既可以自定义哈希函数作为模板参数传入,也可以通过特化std::hash模板的方式实现哈希支持
std::unordered_map的遍历顺序与元素插入顺序完全一致,因此无需额外存储即可直接按插入顺序输出单词统计结果