如何按降序和第二个元素对对的向量进行排序？

Question

我工作的一个编程的挑战，我已经看过这个主题前问：

Sorting elements of vector where each element is a pair [duplicate]

How do I sort a vector of pairs based on the second element of the pair?

而且情况是这样的：

-I有我的矢量的配对：vector< pair<int, int> > rank;

-我已经实现了一个谓词来比较和排序由secon对的向量d元素，按降序排列：

struct predicate 
{ 
    bool operator()(const std::pair<int, int> &left, const std::pair<int, int> &right) 
    { 
     return left.second < right.second; 
    } 
} 

sort(rank.rbegin(), rank.rend(), predicate()); 

编程挑战将给重复值的第二个元素，而对于情况下，我必须离开以它插入到对的矢量的时间排序的第一个元素，例如：

 
K V 
1 3 
2 4 
4 5 
33 3 

排序必须是：

 
4 5 
2 4 
1 3 
33 3 

问题是当我测试我的测试情况下，我设计的解决方案：

 
K V 
1 2 
16 3 
11 2 
20 3 
18 2 
39 39 
23 22 
12 19 
123 4 
145 6 
3 5 
26 4 
9574 4 
7 1 
135 5 
193 99 
18237 3 
22 4 
1293 3 
3471 33 

它应该输出应该是这样的，排序向量后：

 
193 99 
39 39 
3471 33 
23 22 
12 19 
145 6 
3 5 
135 5 
123 4 
26 4 
9574 4 
22 4 
16 3 
20 3 
18237 3 
1293 3 
1 2 
11 2 
18 2 
7 1 

但不是说，我得到了第一值也订购了一些元素：

 
193 99 
39 39 
3471 33 
23 22 
12 19 
145 6 
3 5 
135 5 
123 4 
26 4 
9574 4 
22 4 
20 3 ->Changed element 
16 3 ->Changed element 
18237 3 
1293 3 
18 2 ->Changed element 
11 2 
1 2 ->Changed element 
7 1 

为什么发生这种情况？我究竟做错了什么？？ 帮助将不胜感激

Answer 1

std :: sort不保证“相等”元素的顺序保持不变。为此，你想要std :: stable_sort。 “公平”在此上下文中是指两个元件A和B为其中

!((a < b) || (b < a)) 

Answer 2

尝试下面的代码

#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <utility> 

int main() 
{ 
    std::vector<std::pair<int, int>> v; 

    // If your compiler does not support list initialization then you can use push_back 
    v.push_back(std::pair<int, int>(1, 3)); 
    v.push_back(std::pair<int, int>(2, 4)); 
    v.push_back(std::pair<int, int>(4, 5)); 
    v.push_back(std::pair<int, int>(33, 3)); 

    // The lambda expression can be substituted for a function with the same body 
    std::sort(v.begin(), v.end(), 
       [](const std::pair<int, int> &p1, const std::pair<int, int> &p2) 
       { 
        return (p1.second > p2.second || 
          (!(p2.second > p1.second) && p1.first < p2.first)); 
       }); 

    for (const auto &p : v) std::cout << p.first << '\t' << p.second << std::endl; 
    std::cout << std::endl; 
} 

输出是

4  5 
2  4 
1  3 
33  3 

你的谓词的外观按以下方式

struct predicate 
{ 
    bool operator()(const std::pair<int, int> &left, const std::pair<int, int> &right) const 
    { 
     return (left.second > right.second || 
       (!(right.second > left.second) && left.first < right.first)); 
    } 
}; 

Answer 3

它是钙lled stable_sort这意味着如果第二个值是相同的，那么它将遵循与输入相同的排序，如16 3在输入之前20 3。所以结果16 3将在20 3之前。在C++代码中，您应该添加stable_sort（）而不是sort（）。这是我接受代码：

#include <bits/stdc++.h> 
using namespace std; 
bool compare(const pair<long long int,long long int>& x, const pair<long long int, long long int>& y) 
{ 

    return (x.second>y.second); 

} 
int main() 
{ 
    vector<pair<long long int,long long int> >a; 
    long long int n,i,j,b,c; 
    cin>>n; 
    for(i=1;i<=n;i++) 
    { 
     cin>>b>>c; 
     a.push_back(pair<long long int,long long int>(b,c)); 
    } 
    stable_sort(a.begin(),a.end(),compare); //must include stable_sort 
    vector<pair<long long int,long long int> >::iterator p; 
    for(p=a.begin();p!=a.end();p++) 
    { 
     cout<<p->first<<" "<<p->second<<endl; 
    } 
    return 0; 



}