使用STL按元素频率升序排序vector出错，求问题排查

嘿，我来帮你揪出代码里的问题啦～你的排序逻辑出错的核心原因是自定义比较器违反了std::sort要求的「严格弱序」规则，具体来说：

• 当两个元素的出现频率相等时，你的cm函数直接返回false。这会让std::sort认为：a不小于b，同时b也不小于a，但这两个元素本身并不等价（除非它们数值相同）。这种模糊的判断会触发排序算法的未定义行为，导致你得到错误的排序结果。
• 而用pair实现的方法之所以能正常运行，是因为当频率（pair的第二个元素）相等时，pair的默认比较会自动比较第一个元素（原数值），这样就给频率相同的元素提供了明确的排序规则，满足了严格弱序的要求。

修正后的代码 #

我们只需要给频率相等的元素补充一个明确的排序规则（比如按元素本身的大小排序），就能修复这个问题：

#include <bits/stdc++.h>
using namespace std;

unordered_map<int,int> m;
bool cm(int a,int b){
    if(m[a] != m[b]){
        return m[a] < m[b]; // 按频率升序排序
    }
    // 频率相同时，按元素值升序排序（可根据需求改成降序）
    return a < b;
}

int main(){
    int n;
    cin>>n;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
        m[v[i]]++;
    }
    sort(v.begin(),v.end(),cm);
}

更优的写法（避免全局变量） #

全局变量虽然能用，但封装性差，更推荐用C++11的lambda表达式捕获局部的map，代码更安全整洁：

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    vector<int> v(n);
    unordered_map<int,int> m;
    for(int i=0;i<n;i++){
        cin>>v[i];
        m[v[i]]++;
    }
    // 用lambda捕获局部map，同时定义严格弱序的比较规则
    sort(v.begin(),v.end(),[&m](int a,int b){
        if(m[a] != m[b]){
            return m[a] < m[b];
        }
        return a < b;
    });
}

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