如何按降序和第二個元素對對的向量進行排序？

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; 



}