如何对C++中pair类型vector的指定范围按自定义规则排序

你可以通过两种方式实现需求，第一种是直接使用复合规则一次完成排序，效率更高；第二种是在已完成第二元素降序排序的基础上，遍历找到相同second的区间单独排序。 #

方案1：复合比较函数一次排序（推荐） #

直接在排序时定义优先级规则：先按pair的second降序排序，second相等时按first升序排序，一步完成需求，无需二次处理：

#include<bits/stdc++.h>
#define ll long long

using namespace std;

// 自定义复合排序规则
bool cmp(const pair<ll,ll> &a,const pair<ll,ll> &b)
{
    // 第二元素不相等时按第二元素降序
    if(a.second != b.second){
        return a.second > b.second;
    }
    // 第二元素相等时按第一元素升序
    return a.first < b.first;
}

int main(){
    int n;
    cin>>n;
    
    // 替换变长数组为标准vector，符合C++规范
    vector<ll> a(n);
    vector<ll> b(n);
    
    vector<pair<ll, ll>> v;

    for (int i = 0; i < n; i++) {
        cin>>a[i];
    }
    for (int i = 0; i < n; i++) {
        cin>>b[i];
    }
    
    for (int i = 0; i < n; i++) {
        v.push_back(make_pair(a[i],b[i]));
    }
    
    // 一次排序完成所有规则
    sort(v.begin(), v.end(), cmp);
    
    // 遍历输出结果
    for (auto itr=v.begin(); itr!=v.end(); itr++) {
        cout << itr->first << " " << itr->second << endl;
    }
    return 0;
}

方案2：在已完成第二元素降序的基础上单独处理同值区间 #

如果你需要保留先做全局第二元素降序的逻辑，可通过双指针定位连续相同second的区间，对区间单独排序，把以下代码替换到你注释的/* 待实现逻辑 */位置即可：

int i = 0;
int len = v.size();
while(i < len){
    int j = i;
    // 找到second值相同的连续区间右边界
    while(j < len && v[j].second == v[i].second){
        j++;
    }
    // 对[i,j)区间按first升序排序
    sort(v.begin() + i, v.begin() + j, [](const pair<ll,ll>& x, const pair<ll,ll>& y){
        return x.first < y.first;
    });
    i = j;
}

注意事项 #

• 原代码中自定义比较函数的参数类型为pair<int,int>，与vector存储的pair<ll,ll>类型不匹配，需要修正避免类型错误
• 原代码中ll a[n]、ll b[n]属于可变长度数组，是C标准扩展，不属于标准C++语法，建议替换为vector<ll>保证跨编译器兼容性

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