vector<pair>のソートの覚書き [C++]

なんとなくpairをソートしてみたら面白かったのでメモする。

pairにも大小関係があるのでソートできる

マクロばっかで申し訳ないがとりあえず昇順ソート

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

using pii = pair<int, int>;
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define all(v) (v).begin(), (v).end()

vector<pii> vp;

void vpii(){
  vp.pb(mp(1,2));
  vp.pb(mp(2,3));
  vp.pb(mp(1,3));
  vp.pb(mp(2,5));
  vp.pb(mp(3,1));
  vp.pb(mp(1,2));
  vp.pb(mp(2,2));
  vp.pb(mp(2,4));
  vp.pb(mp(1,1));
  vp.pb(mp(3,2));
  vp.pb(mp(3,1));
}

int main(){
  vpii();

  for(pii x: vp){
    cout<<x.ff<<","<<x.ss<<endl;
  }

  cout<<"降順ソート\n";
  sort(all(vp));
  for(pii x: vp){
    cout<<x.ff<<","<<x.ss<<endl;
  }
}

1,2
2,3
1,3
2,5
3,1
1,2
2,2
2,4
1,1
3,2
3,1
昇順ソート
1,1
1,2
1,2
1,3
2,2
2,3
2,4
2,5
3,1
3,1
3,2

以後はmain関数のみ書き換えて提示する。

pairにも比較演算子が用意されているので単純にソートができる。

降順ソートは

int main(){
  vpii();

  cout<<"降順ソート\n";
  sort(all(vp), greater<pii>());
  for(pii x: vp){
    cout<<x.ff<<","<<x.ss<<endl;
  }
}

降順ソート
3,2
3,1
3,1
2,5
2,4
2,3
2,2
1,3
1,2
1,2
1,1

変なソート

first降順 second昇順

全体としてfirstを降順にしたいけどfirstが同じだったらその中ではsecond昇順になるようにソートする

ラムダ式で実装

int main(){
  vpii();

  cout<<"first降順 second昇順\n";
  sort(all(vp), [](pii a, pii b){
   return a.ff>b.ff || (a.ff==b.ff && a.ss<b.ss);
  });
  for(pii x: vp){
    cout<<x.ff<<","<<x.ss<<endl;
  }
}

first降順 second昇順
3,1
3,1
3,2
2,2
2,3
2,4
2,5
1,1
1,2
1,2
1,3

和の昇順 first昇順

全体としてfirst+secondの値で昇順ソート、和が等しければfirstを昇順に

int main(){
  vpii();

  cout<<"和の昇順 first昇順\n";
  sort(all(vp), [](pii a, pii b){
   return (a.ff+a.ss)<(b.ff+b.ss) || ((a.ff+a.ss)==(b.ff+b.ss) && a.ff<b.ff);
  });
  for(pii x: vp){
    cout<<x.ff<<","<<x.ss<<endl;
  }
}

和の昇順 first昇順
1,1
1,2
1,2
1,3
2,2
3,1
3,1
2,3
3,2
2,4
2,5

参考

• operator==,!=,<,<=,>,>=(std::pair) - cppreference.com