如何对含结构体的C++ vector排序后保留重复ID的原始顺序？

你要的这种排序叫做稳定排序——排序后相同键值（这里是ID）的元素保留原始的相对顺序，C++里有两种直接的实现方式：

方案一：用std::stable_sort直接搞定 #

这是最简单的方案，标准库的std::stable_sort就是专门干这个的，完全匹配你的需求，不用改结构体，一行排序代码搞定。

举个例子，假设你的结构体是这样：

struct Item {
    int id;
    std::string extra_data; // 其他属性
};

排序代码直接这么写：

#include <vector>
#include <algorithm>

int main() {
    std::vector<Item> my_items = {
        {5, "第一个5"}, {2, "随便数据"}, {5, "第二个5"}, {1, "测试"}, {5, "第三个5"}
    };

    // 按id升序排，相同id的元素自动保留原始顺序
    std::stable_sort(my_items.begin(), my_items.end(), [](const Item& a, const Item& b) {
        return a.id < b.id;
    });

    return 0;
}

跑完之后三个id为5的元素会严格按照第一个5→第二个5→第三个5的原始顺序排列，完全符合你的要求。

方案二：给结构体加原始索引，用std::sort自定义排序 #

如果你因为某些原因不想用stable_sort，你说的给结构体加原始顺序属性的方法完全可行，思路就是用原始位置作为“第二排序键”，保证相同id的元素按原顺序排列。

步骤很简单：

1. 给结构体加一个size_t类型的original_pos字段，存元素在原vector里的下标。
2. 遍历vector给每个元素的original_pos赋值（从0开始数）。
3. 排序的时候先比id，id相同就比original_pos，小的在前。

示例代码：
修改后的结构体：

struct Item {
    int id;
    std::string extra_data;
    size_t original_pos; // 新增原始位置字段
};

排序代码：

#include <vector>
#include <algorithm>

int main() {
    std::vector<Item> my_items = {
        {5, "第一个5"}, {2, "随便数据"}, {5, "第二个5"}, {1, "测试"}, {5, "第三个5"}
    };

    // 给每个元素标记原始位置
    for (size_t i = 0; i < my_items.size(); ++i) {
        my_items[i].original_pos = i;
    }

    // 自定义排序逻辑
    std::sort(my_items.begin(), my_items.end(), [](const Item& a, const Item& b) {
        if (a.id != b.id) {
            return a.id < b.id;
        }
        // id相同，按原始位置排，保证顺序不变
        return a.original_pos < b.original_pos;
    });

    return 0;
}

两种方案的对比 #

• std::stable_sort：代码简洁，不用改结构体，优先选这个。它的时间复杂度最坏是O(n log²n)，内存充足时会优化到O(n log n)。
• 自定义索引方案：需要修改结构体，代码稍麻烦，但用的是std::sort（时间复杂度O(n log n)），适合不能用stable_sort的场景。

内容的提问来源于stack exchange，提问作者Coffee'd Up Hacker