この記事は2024夏のブログリレー10日目の記事です。

こんにちは。24Bの @zoi_dayo です。競技プログラミングをやったりやらなかったりしています。この記事では競プロの話をします。

C++の話しかしません。Pythonユーザーの方、ごめんなさい...

structってなんですか

複数の値をまとめて、新しい型を作ることができる機能です。他の言語ではclassと呼ばれていたりします。
(実はC++にはstructもclassもあってややこしいです。C++のstructとclassにほぼ違いはないです。正確には、structはデフォルトのアクセス権限がpublic、classはprivateになっています。)

こんな感じで使うことができます。

struct Coord {
  int x, y;
};

Coord s = {1,2};
cout << s.x << ", " << s.y << endl; // 1, 2
s.x = 3;
cout << s.x << ", " << s.y << endl; // 3, 2

まるでpair<int, int>ですね。ただし、firstとsecondではなく好きな名前をつけることができます。さらに、値を3つ以上持たせることもできます。

これでもう、tuple<int,int,int>を作って「コストって1番目だっけ...3番目だっけ...?」と悩んだり、pair<int, pair<int, int>>などを作ってhoge.second.firstする必要がなくなります。やった〜!!

メンバ関数

さらに、structには関数を入れておくこともできます。

struct Coord {
  int x, y;
  int manhattan() {
    return abs(x)+abs(y);
  }
};

Coord s = {1,2};
cout << s.manhattan() << endl;

データとそれに関する処理を近くに置けるわけです。嬉しいね!!

比較関数

例えば、長方形領域をstructで表したとしましょう。

struct Rect {
  int x1, y1, x2, y2;
  int h() { return x2 - x1; };
  int w() { return y2 - y1; };
  int area() { return h() * w(); };
};

ここで、vector<Rect>を面積の昇順でソートしたいとします。もちろん以下のように書くことはできるのですが、sortやpriority_queueが出てくるたびに書かないといけないので少し面倒です。

vector<Rect> rects = { /* 略 */ };
sort(rects.begin(), rects.end(), [](Rect& a, Rect& b){ return a.area() < b.area(); });

そこで、<演算子をRectに使えるようにしておくと楽です。

struct Rect {
  int x1, y1, x2, y2;
  int h() const { return x2 - x1; };
  int w() const { return y2 - y1; };
  int area() const { return h() * w(); };
};
bool operator<(const Rect& a, const Rect& b) {
  return a.area() < b.area();
}

sort(rects.begin(), rects.end());

<演算子だけ準備しておけばsort関数はいい感じにしてくれるので楽です。

ちなみに、>や+、>>など他の演算子も同じように定義できるので、必要があればやってみましょう。興味があれば「演算子オーバーロード」で検索!

ちょっと余談1 (constの話)

area()などの関数にconstがつきましたが、これは「この関数は実行してもメンバ変数(struct内に書いた変数、今回はx1など)を書き換えないよ」という意味です。
比較関数の実行前後で値が変わるのは嫌なので比較関数operator<()にはconst Tが渡されるのですが、これに対して関数を呼び出して書き換えが発生しないように、比較関数内で使っているarea()もconstをつけないといけないわけです。

ただ書くときにちょっと注意が必要で、const bool operator<(...) {}と書いてしまうと、このconstはconst boolと解釈されてしまって思ったように動かなかったりします。関数をconstにしたいわけなので、bool operator<() const {}が正しいです。場所に気をつけましょう。

ちょっと余談2 (<=>の話)

もしpriority_queueでgreater<>を設定するなど、>が必要になったときはそれも書かないといけないのですが、C++20以降なら<=>という変な比較演算子(三方比較演算子/宇宙船演算子)があり、これを実装しておけば<、>、<=、==などいろいろなものを勝手に作ってくれます。

小さい、等しい、大きいの3つを表さないといけないので、operator<=>の返り値はboolではないです。autoにしておきましょう。(strong_orderingとかweak_orderingとか何種類かあるらしいです)

auto operator<=>(const Rect& a, const Rect& b) {
  return a.area() <=> b.area();
}

コンストラクタ

structの変数に初期値をセットしたい場合、以下のように書けます。

struct Coord {
  int x = 0, y = 0;
};

Coord p;
cout << p.x << endl; // 0

しかし、もっと柔軟に初期値を設定したい場合もあると思います。たとえば、n×nの正方行列を表すstructを書くとき、初期値の設定のためにnが必要です。
コンストラクタを使えばこう書けます。

struct Mat {
  int size;
  vector<vector<int>> val;
  Mat(int n) {
    size = n;
    val = vector(n, vector<int>(n, 0));
  }
};
Mat m(2);

Matが作られるときに実行される関数を指定できるってことです。

ちなみに、メンバ変数の初期化についてはこう書くこともできます。

struct Mat {
  int size;
  vector<vector<int>> val;
  Mat(int n) : size(n), val(n, vector<int>(n, 0)) {}
};

テンプレート

先程のMatの例では、int型の行列しか表せませんでした。これをdoubleなどでも使えるようにするために、MatInt、MatDouble、...と作るのは大変です。

これを解決するため、template<>という機能があります。

template<class T>
struct Mat {
  int size;
  vector<vector<T>> val;
  Mat(int n) : size(n), val(n, vector<T>(n, 0)) {}
};
Mat<int>    mat_int(2);
Mat<double> mat_double(2);

vector<>とかでよく見る記法ですね。型をTとして書いておいて、あとで好きに置き換えられるようにしています。ライブラリを作るときはこんなふうに一般化させとくと使いやすいことがあります。(たとえばSegtree<int>みたいな書き方ができる)

まとめ

pairとかは比較関数もついてて便利ですが、firstとかsecondとかのままでは中身がなにか分かりづらくなってしまいます。多少複雑なBFSなどを書くときは、データをまとめてstructに入れてしまったほうが見やすいことが多いのでおすすめです!

コンテスト中にコンストラクタやtemplateまで書くのは大変ですが、ライブラリを作る際にここらへんの機能を使うといい感じにできます。うまくライブラリを書けると楽しいので暇ならやりましょう。やりすぎると精進の時間がなくなるので適度に...(n敗)

明日は @masu_kou さん、 @el さん、 @masataro さん、 @ch4tla さん、 @vPhos さん、 @Cd_48 さんの記事が出るらしいです。楽しみ～～!!