Tamflexの貯蔵庫

やる気のない備忘録

c++でソート

C++でソートするときの備忘録

参考文献
C++(ソートの補足) - アルゴリズム講習会

stlを用いてソートしたいとき少し困ったので書き留める。

  • 基本的にはvectorに入れてsortすれば一番目の要素の小さい順に二番目の要素が小さい順にsortされる。
  • 自作のstructでソートしたい時やpairを別の順番で自分でソートしたい時は比較関数を書いてあげればOK。
  • mapに関してはデフォルトでkeyでsortされているのでvalueでsortしたいときはpairを使う。
  • queueに関してはpriority_queueを用いる。


pairでのソートの例

#include <bits/stdc++.h>

#define REP(i,n) for(int i=0;i<n;i++)
#define ALL(o) (o).begin(), (o).end()

using namespace std;

typedef pair<int, int> Pii;

bool comp(Pii l, Pii r)
{
  return l.first != r.first ? l.first > r.first : l.second > r.second;
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  // FROM HERE
  int n; cin >> n;
  vector<Pii> p(n);
  REP(i,n)
  {
    int a, b; scanf("%d %d",&a,&b);
    p[i] = make_pair(a,b);
  }
  sort(ALL(p));  // firstが小さい順,secondが小さい順にソート
  REP(i,n) printf("%d\t%d\n",p[i].first,p[i].second);
  printf("\n");
  sort(ALL(p),comp);  // firstが大きい順,secondが大きい順にソート
  REP(i,n) printf("%d %d\n",p[i].first,p[i].second);
  return 0;
}

Input

5
3 2
1 1
2 1
2 2
3 1

Output

1 1
2 1
2 2
3 1
3 2

3 2
3 1
2 2
2 1
1 1