如何输出C++ string-int类型map中频次最高与最低的k个元素

问题澄清 #

你当前的问题和把string设为map的key、int设为value没有关系。std::map的特性就是本身仅按照Key排序，你用map<string,int>做单词计数的逻辑是完全正确的，完全不需要调换键值位置：如果强行把int（频次）设为key，由于map的key唯一，多个相同频次的单词会互相覆盖，根本无法完成计数需求。

实现方案 #

你只需要把map中存储的<单词,频次>键值对转存到支持自定义排序的容器中，再按频次排序后取前k个即可，下面是两种常用实现方式：

方案1：全量排序（最直观，适合数据量不大的场景） #

将map的所有元素拷贝到std::vector中，自定义排序规则后截取前k个元素，示例代码如下：

#include <vector>
#include <algorithm>

// 假设你已经完成了单词计数，words是已经填充好的map<string,int>
int k = 5; // 你需要的top k数值
vector<pair<string, int>> word_vec(words.begin(), words.end());

// 按频次从高到低排序，取频次最高的k个
sort(word_vec.begin(), word_vec.end(), [](const pair<string, int>& a, const pair<string, int>& b) {
    return a.second > b.second;
});

cout << "频次最高的" << min(k, (int)word_vec.size()) << "个单词：" << endl;
for (int i = 0; i < k && i < word_vec.size(); i++) {
    cout << word_vec[i].first << " = " << word_vec[i].second << endl;
}

// 按频次从低到高排序，取频次最低的k个
sort(word_vec.begin(), word_vec.end(), [](const pair<string, int>& a, const pair<string, int>& b) {
    return a.second < b.second;
});

cout << "频次最低的" << min(k, (int)word_vec.size()) << "个单词：" << endl;
for (int i = 0; i < k && i < word_vec.size(); i++) {
    cout << word_vec[i].first << " = " << word_vec[i].second << endl;
}

方案2：堆排序（效率更高，适合数据量大、k较小的场景） #

用std::priority_queue实现O(nlogk)复杂度的TopK计算，不需要全量排序：

#include <queue>

int k = 5;
// 取频次最高的k个：用小顶堆，堆顶始终是当前堆中频次最小的元素
priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> max_heap;
for (auto& item : words) {
    max_heap.push({item.second, item.first});
    if (max_heap.size() > k) {
        max_heap.pop();
    }
}
cout << "频次最高的" << min(k, (int)words.size()) << "个单词：" << endl;
while (!max_heap.empty()) {
    auto& top = max_heap.top();
    cout << top.second << " = " << top.first << endl;
    max_heap.pop();
}

// 取频次最低的k个：用大顶堆，堆顶始终是当前堆中频次最大的元素
priority_queue<pair<int, string>> min_heap;
for (auto& item : words) {
    min_heap.push({item.second, item.first});
    if (min_heap.size() > k) {
        min_heap.pop();
    }
}
cout << "频次最低的" << min(k, (int)words.size()) << "个单词：" << endl;
while (!min_heap.empty()) {
    auto& top = min_heap.top();
    cout << top.second << " = " << top.first << endl;
    min_heap.pop();
}

注意事项 #

• 如果k值大于单词总数量，直接输出所有单词即可，上述代码中min(k, size)的逻辑已经做了兼容
• 如果有多个单词频次相同，排序时会按照单词字典序排列，你可以根据需求修改sort的比较规则调整同频次单词的排序逻辑

内容的提问来源于stack exchange，提问作者yepp