C++中使用vector pair排序时，相同计数元素无法保持插入顺序的问题

云原生阿岚

2026-5-21

问题原因及解决办法

嘿，这个问题我之前也踩过坑！咱们先搞清楚为啥插入顺序没保留，再给你几个实用的解决方案：

为啥插入顺序丢了？

C++里std::pair的默认比较逻辑是：先比第一个元素（也就是你存的count[i]），如果第一个元素相等，就会自动比较第二个元素（你的arr[i]）。这就导致当两个元素的count值相同时，它们会按照arr[i]的大小排序，完全无视你插入的先后顺序。

举个实际例子：如果你先插(2, 5)，再插(2, 3)，默认排序后会变成(2, 3)、(2, 5)，和你插入的顺序完全反过来了。

怎么搞定这个问题？

有几种简单的方案，你可以根据自己的代码情况选：

方案1：给元素加上插入索引，自定义排序规则

最简单的思路是给每个元素记录插入时的顺序，排序时count相等就按这个索引来排，这样就能保留原顺序。你可以用嵌套的pair来实现：

插入元素时，顺便把循环的索引（也就是插入顺序）存进去：

vector<pair<pair<int, int>, int>> vect;
int idx = 0;
for (int i = 0; i < arr.size(); ++i) {
    // 第一层pair存(count, 插入索引)，第二层存arr[i]
    vect.push_back(make_pair(make_pair(count[i], idx), arr[i]));
    idx++;
}

写个自定义的排序lambda，先按count排序，count相等就按插入索引排序：

sort(vect.begin(), vect.end(), [](const auto& a, const auto& b) {
    // 先比count，小的排前面
    if (a.first.first != b.first.first) {
        return a.first.first < b.first.first;
    }
    // count相等时，按插入索引升序，保留原顺序
    return a.first.second < b.first.second;
});

最后输出的时候取vect[i].second就可以了。

方案2：用stable_sort简化代码（不用改数据结构）

如果你不想改原来的vector结构，用std::stable_sort也能搞定。stable_sort的特点是会保持被视为相等的元素的相对顺序，所以咱们只需要让count相等的元素在比较时被判定为“不小于也不大于”（也就是比较器返回false）：

// 注意这里用的是stable_sort，不是普通的sort
stable_sort(vect.begin(), vect.end(), [](const auto& a, const auto& b) {
    // 只比较count，count小的排前面；count相等时，不做排序操作
    return a.first < b.first;
});

这个方法最简洁，不用改数据结构，但要知道stable_sort的性能比普通sort略低一点，不过对于大多数日常场景来说完全够用。

方案3：用结构体替代pair（更清晰）

如果嵌套pair看起来有点乱，你也可以定义一个简单的结构体，把count、arr值、插入索引都存进去，排序逻辑更直观：

struct Element {
    int count;
    int value;
    int index;
};

vector<Element> vect;
for (int i = 0; i < arr.size(); ++i) {
    vect.push_back({count[i], arr[i], i});
}

sort(vect.begin(), vect.end(), [](const Element& a, const Element& b) {
    if (a.count != b.count) {
        return a.count < b.count;
    }
    return a.index < b.index;
});

// 输出时取a.value
for (const auto& elem : vect) {
    cout << elem.value << " ";
}

这个方法代码可读性更高，适合元素属性比较多的情况。

总结一下

核心问题就是std::pair默认会在first相等时比较second，破坏了插入顺序。只要我们在排序时，让count相等的元素按照插入顺序（而不是arr的值）来排序，就能解决这个问题。

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