【競技プログラミング】STL::pair ことはじめ

０．はじめに

AtCoder Programming Guide for beginners (APG4b)でSTL::pairを学んだ際、
記述に迷い、エラーを再三出してしまったため、自分用の知識のまとめ、備忘録として記事に残します。
お役に立てれば幸いです。

なお、STL::pairの詳細についてはAPG4bの該当箇所で学習するのがよいと思います。

１．STL::pairとは

pairとは、2個の要素をひとまとめにするクラスです。
例えば科目と点数、氏名と所属などを１つの値として管理できます。
なお、N個の要素をひとまとめにするクラスとして、tupleがあります。

２．ポイント

• 配列と共に使われることが多い。つまりvectorの型として利用するのが基本です。
• pairをソートすると1番目の値で比較され、それが等しい場合は2番目の値で比較されます。
• pair, make_pair, tieの型の並びは統一する必要があります。

３．例題

では実際に例題を通してポイントを確認していきます。
似通った問題を並べてみますので、その違いに注目しましょう。

例題A

全ｎ科目の試験の結果が科目名a, 点数bで与えられる。
点数の低い科目から順番に出力しなさい。

SampleA

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

int main() {
	int  n;
  	cin >> n;
  	vector<pair<int, string>> p(n); //点数を比較したいのでintを前に。
  	for(int i = 0; i < n; i++) {
         string a;
      	 cin >> a;
         int b;
         cin >> b;
         p.at(i) = make_pair(b, a); //pairと合わせてint, stringの順に記述します。
    }
  
  	sort(p.begin(), p.end());
  
  	for(int i = 0; i < n; i++){
      string a;
      int b;
      tie(b, a) = p.at(i); //pair, make_pairと合わせてint, stringの順に記述します。
      cout << a << ": " << b << endl; //出力は任意の順番で問題ありません。
    }
}

入力例A
3
Math 100
English 80
Science 85

出力例A
English: 80
Science: 85
Math: 100

例題B

全ｎ科目の試験の結果が科目名a, 点数bで与えられる。
科目名を辞書順で並び替え、点数と合わせて出力しなさい。

SampleB

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

int main() {
	int  n;
  	cin >> n;
  	vector<pair<string, int>> p(n); //辞書順にしたいのでstringを前に。
  	for(int i = 0; i < n; i++) {
         string a;
      	 cin >> a;
         int b;
         cin >> b;
         p.at(i) = make_pair(a, b); //string, intの順となり例題Aとは反転します。
    }
  
  	sort(p.begin(), p.end());
  
  	for(int i = 0; i < n; i++){
      string a;
      int b;
      tie(a, b) = p.at(i); //上のmake_pairと合わせ、string, intの順で記述します。
      cout << a << ": " << b << endl;
    }
}

入力例B
3
Math 100
English 80
Science 85

出力例B
English: 80
Math: 100
Science: 85

４．まとめ

pairクラスは1番目の値がソート対象になります。
その都合、値の順番を入れ替えることが多いのですが、
pair, make_pair, tieの組み合わせに齟齬が発生するとエラーが発生したり、誤った値が出力されたりします。
厳格な記述を求めてくる印象ですが、記述量が少なく、要素が少ないケースで適している場合が多そうです。

最後までお付き合い頂き、ありがとうございました。

参考文献

AtCoder Programming Guide for beginners (APG4b)
cpprefjp - C++日本語リファレンス
@e869120: 厳選！C++ アルゴリズム実装に使える 25 の STL 機能【前編】
@drken:「記事を書くこと」のススメ 〜 最高の達成感を求めて 〜