目次

C++（ソートの補足）

複数の要素をまとめてソート

複数の要素をまとめてソートしたいときは、pairの配列（vector<pair<型1, 型2> >）を使うと簡単にできる。

#include <stdio.h>
#include <vector>
#include <algorithm> // sort
#include <map> // pair
using namespace std;

int main() {
  int n = 10;
  vector<pair<int, int> > pairs(n);
  
  for (int i = 0; i < n; i++) {
    pairs[i] = make_pair(i*i % 10, i);
  }

  // firstが小さい順、secondが小さい順にソート
  sort(pairs.begin(), pairs.end());

  for (int i = 0; i < n; i++) {
    printf("(%d,%d) ", pairs[i].first, pairs[i].second);
  }
  puts(""); // => (0,0) (1,1) (1,9) (4,2) (4,8) (5,5) (6,4) (6,6) (9,3) (9,7)
  
  return 0;
}

ソートの順序を指定

STLのソートはそのままでは昇順（小さい順）になるが、この順序を別のものにすることもできる。
sort関数にはソートの順序を定める比較関数を指定することができるので、これを使う。

降順に並べるには、functionalヘッダにあるgreater<型>()を使う。

独自の順序で並べるときは比較関数を自作する必要がある。
比較関数は引数を2つ取り、1番目の引数が2番目の引数よりも「より小さい」（より配列の前方に来る）なら真を返す関数。
引数は値渡しかconst参照（const Hoge&みたいなの）のどちらかであることに注意。

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

// 表示用関数
void disp(vector<int>& vec) {
  cout << "[";
  for (int i = 0; i < vec.size(); i++) cout << " " << vec[i];
  cout << " ]" << endl;
}

// 自作のソート関数
// 5で割った余りの大小で比較
bool less_mod5(int lhs, int rhs) {
  if ((lhs - rhs) % 5 != 0)
    return lhs % 5 < rhs % 5;
  else // 5で割った余りが等しいなら普通に大小比較する
    return lhs < rhs;
}

int main() {
  vector<int> vec(10);
  for (int i = 0; i < vec.size(); i++) vec[i] = 9 - i;

  sort(vec.begin(), vec.end());
  disp(vec); // => [ 0 1 2 3 4 5 6 7 8 9 ]

  sort(vec.begin(), vec.end(), greater<int>()); // 降順（大きい順）でソート
  disp(vec); // => [ 9 8 7 6 5 4 3 2 1 0 ]
  
  sort(vec.begin(), vec.end(), less_mod5); // 自作関数でソート
  disp(vec); // => [ 0 5 1 6 2 7 3 8 4 9 ]
  return 0;
}

余談ですが、比較関数としてsort関数に渡すものとしては関数ポインタだけでなく関数オブジェクトを使うこともできます。 関数オブジェクトの方が何かと便利なのですが、記法が面倒なのでICPCではあまり使いません。

structのソート

構造体はそのままでは比較可能ではないので、ソートできない。ソートしたいときは演算子のオーバーロードを使う（もしくは比較関数を使う）。

C++のSTLでは、オブジェクトの比較には暗黙的にoperator<が使用されている。
この演算子をオーバーロードすることで、組み込み型と同様にソートできるようになる（同様に、max関数やlower_bound関数なども使用できるようになる）。

以下のプログラムは、構造体を使ったソートの例。

問題：標準入力の一行目に人数n、続くn行に学生番号・国語の点数・数学の点数が空白区切りで与えられる。 国語の点数が高い順、数学の点数が高い順、学生番号が小さい順にソートしてn人分の学生番号を1行に出力せよ。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Student {
  int no, kokugo, sugaku;

  // 演算子オーバーロードで比較関数を定義
  bool operator<(const Student& another) const {
    if (kokugo != another.kokugo)
      return kokugo > another.kokugo; // 高い順に並べたいので演算子を逆に
    if (sugaku != another.sugaku)
      return sugaku > another.sugaku; // 同様に比較演算子を反転
    return no < another.no;
  }
};

int main() {
  int n;
  cin >> n;
  vector<Student> vec(n);
  for (int i = 0; i < n; i++)
    cin >> vec[i].no >> vec[i].kokugo >> vec[i].sugaku;

  sort(vec.begin(), vec.end()); // operator< を使ってソートされる

  for (int i = 0; i < vec.size(); i++) cout << vec[i].no << " ";
  cout << endl;

  return 0;
}

入力例：

6
1 50 50
2 100 50
3 0 500
4 50 100
5 50 100
6 50 0

出力例：

2 4 5 1 6 3

※構造体で保持する変数の数が3つくらいなら、以下のように2重のpairを適用することもできる。
演算子オーバーロードで比較関数を自作する必要がない分楽（ただし、どのようにデータを格納したかは把握しておくする必要がある）。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<pair<int, pair<int, int> > > vec(n);
  for (int i = 0; i < n; i++) {
    int no, kokugo, sugaku;
    cin >> no >> kokugo >> sugaku;
    // 点数が高い順にソートしたいので、kokugoとsugakuを前方に持ってきてマイナスにする
    vec[i] = make_pair(-kokugo, make_pair(-sugaku, no));
  }

  sort(vec.begin(), vec.end()); // これで想定通りにソートされる

  for (int i = 0; i < vec.size(); i++)
    // 番号は3番目に入れたのでsecond2つでアクセスする
    cout << vec[i].second.second << " ";
  cout << endl;

  return 0;
}

いや比較関数作った方がわかりやすいかな

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, pair<int, int> > S; // 番号、国語の点、数学の点

// lhs < rhs ならtrueを返す
bool comp(S lhs, S rhs) {
  if (lhs.second.first != rhs.second.first)
    return lhs.second.first > rhs.second.first;
  if (lhs.second.second != rhs.second.second)
    return lhs.second.second > rhs.second.second;
  return lhs.first < rhs.first;
}

int main() {
  int n;
  cin >> n;
  vector<S> vec(n);
  for (int i = 0; i < n; i++) {
    int no, kokugo, sugaku;
    cin >> no >> kokugo >> sugaku;
    vec[i] = S(no, make_pair(kokugo, sugaku));
  }

  sort(vec.begin(), vec.end(), comp);

  for (int i = 0; i < vec.size(); i++)
    // 番号は1番目に入れたのでfirstでアクセスする
    cout << vec[i].first << " ";
  cout << endl;

  return 0;
}

比較関数使うならpairにする必要性がないな

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Student {
  int no, kokugo, sugaku;
};

// a < b ならtrueを返す
bool comp(const Student& a, const Student& b) {
  if (a.kokugo != b.kokugo)
    return a.kokugo > b.kokugo; // 高い順に並べたいので演算子を逆に
  if (a.sugaku != b.sugaku)
    return a.sugaku > b.sugaku; // 同様に比較演算子を反転
  return a.no < b.no;
}

int main() {
  int n;
  cin >> n;
  vector<Student> vec(n);
  for (int i = 0; i < n; i++)
    cin >> vec[i].no >> vec[i].kokugo >> vec[i].sugaku;

  sort(vec.begin(), vec.end(), comp);

  for (int i = 0; i < vec.size(); i++) cout << vec[i].no << " ";
  cout << endl;

  return 0;
}

好きなものを使ってください…。

演習