C++中使用自定义比较器排序时如何保留同键值元素初始顺序？

用户提供的C++代码：

std::vector<std::vector<std::string>> vect{
{"abc","def","2"},
{"def","ghi","2"},
{"abc","def","2"},
{"abc","def","3"}};
std::sort(vect.begin(),vect.end(),
[](const std::vector<std::string>& a,const std::vector<std::string>& b){
/*if(a[2]!=b[2]) return a[2]>b[2];*/});

期望实现：

• 元素第2个索引值不同时，按该值降序排列
• 元素第2个索引值相同时，保留其在原容器中的初始顺序

预期结果：

vect={
{"abc","def","3"},
{"abc","def","2"},
{"def","ghi","2"},
{"abc","def","2"}};

但使用std::sort时，同值元素的原始顺序无法保留，原因是**std::sort是不稳定排序**——即使比较函数对两个元素返回false（即判定为“相等”），std::sort仍可能交换它们的位置，不会保证原始顺序。

解决方案 #

方法一：使用std::stable_sort #

std::stable_sort是稳定排序算法，会严格保留相等元素的原始相对顺序。只需替换std::sort为std::stable_sort，并完善比较函数：

#include <algorithm>
#include <vector>
#include <string>

int main() {
    std::vector<std::vector<std::string>> vect{
        {"abc","def","2"},
        {"def","ghi","2"},
        {"abc","def","2"},
        {"abc","def","3"}};
    
    std::stable_sort(vect.begin(), vect.end(),
        [](const std::vector<std::string>& a, const std::vector<std::string>& b){
            return a[2] > b[2]; // 仅按第2个元素降序，同值时保留原顺序
        });
    
    // 此时vect已符合预期结果
    return 0;
}

方法二：绑定原始索引后使用std::sort #

如果必须使用std::sort，可以给每个元素绑定它在原容器中的索引，排序时先按目标字段降序，再按索引升序，从而间接保留原始顺序：

#include <algorithm>
#include <vector>
#include <string>
#include <utility>

int main() {
    std::vector<std::vector<std::string>> vect{
        {"abc","def","2"},
        {"def","ghi","2"},
        {"abc","def","2"},
        {"abc","def","3"}};
    
    // 为每个元素绑定原始索引
    std::vector<std::pair<std::vector<std::string>, int>> indexed_vect;
    for (int i = 0; i < vect.size(); ++i) {
        indexed_vect.emplace_back(vect[i], i);
    }
    
    // 排序：先按第2个元素降序，同值时按索引升序（即原始顺序）
    std::sort(indexed_vect.begin(), indexed_vect.end(),
        [](const auto& a, const auto& b){
            if (a.first[2] != b.first[2]) {
                return a.first[2] > b.first[2];
            }
            return a.second < b.second;
        });
    
    // 将排序后的元素提取回原容器
    vect.clear();
    for (const auto& item : indexed_vect) {
        vect.push_back(item.first);
    }
    
    // 此时vect已符合预期结果
    return 0;
}

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