SORT（），矢量 >即使两个键值相同，也严格基于键值

Question

从下面的代码我想在STL中使用vector<pair<int,int> >对sort()进行排序。但是，问题是，即使两个键相等，我也要严格按照键来sort() vector<pair<int,int> >。首先插入的值应该是第一个。

我的代码在这里：

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

int main()
{
    long int n,k;
    cin>>n>>k;
    vector<pair<int,int> >a;
    for(int i=0;i<n;i++){
        int temp;
        cin>>temp;
        a.push_back(make_pair(temp%k,temp));
    }
    sort(a.begin(),a.end());
    vector<pair<int,int> >::iterator it;
    for(it=a.begin();it!=a.end();it++) {
        cout<< it->second<<" ";
    }
   return 0;
}

输入：

我们来一个基本的输入：

2 7 17 10

这里有关键值17%7=3和10%7=3。

所以我只想输出17 10，因为因为键是相同的，所以首先输入的元素应该是第一个。

但事实并非如此，输出是：

10 17

许多不同的方法是可能的。但是，我只想使用sort（）来解决这个问题。我可以对我的代码做些什么更改？

Answer 1

operator<的std::pair首先比较first成员，如果它们相等，则比较second成员。由于您要忽略second成员，因此无法使用该默认排序。您可以通过将lambda作为额外参数传递给sort来指定要使用的比较：

std::sort(a.begin(), a.end(),
    [](const std::pair<int,int>& p1, const std::pair<int,int>& p2)
    { return p1.first < p2.first; }); // Not quite there...

但这不会得到你想要的东西：

首先插入的值应该是第一个。

std::sort不保证这样的事情。您只知道最终结果遵循排序，但未指定等效元素的顺序。但类似的功能std::stable_sort确实按照你想要的方式行事。所以：

std::stable_sort(a.begin(), a.end(),
    [](const std::pair<int,int>& p1, const std::pair<int,int>& p2)
    { return p1.first < p2.first; });

Answer 2

如果我得到了你想要的东西，你需要一个所谓的“稳定排序”，标准库确实提供了一个恰当命名的std::stable_sort，你应该使用而不是普通的std::sort。