c++ - SORT(),vector> 严格基于键值，即使两个键值相同

Question

我想从下面的代码中对 vector<pair<int,int> > 进行排序使用 sort()在STL中。但是，问题是我想 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成员(member)，您不能使用该默认顺序。您可以通过将 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...

但这也不会让你得到你想要的:

The value which was inserted first should come first.

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; });