競プロ用 C++ struct 超初級

概要

競プロ用の C++ ライブラリを作るための struct の使い方を説明する

メンバ変数

struct を使うと、std::pair<int, int> と似たようなものを作ることが出来ます。

#include <iostream>

struct t {
  int a;
  int b;
};

int main() {
  t x;
  x.a = 1;
  x.b = 2;
  std::cout << x.a << " " << x.b; // 1 2 と表示される
}

struct 型の名前 { }; が基本の構文です (最後のセミコロン忘れに注意)。波括弧の中に書かれた変数をメンバ変数と呼び、x.a のようにして使用できます。

メンバ関数

このままでは芸がないので、a と b の両方に同じ値を代入する機能を付けてみます。

#include <iostream>

struct t {
  int a;
  int b;

  void f(int v) {
    a = v;
    b = v;
  }
};

int main() {
  t x;
  x.f(3);
  std::cout << x.a << " " << x.b; // 3 3 と表示される
}

波括弧の中に書いた関数をメンバ関数と呼び、x.f() のようにして呼び出すことが出来ます。メンバ関数内ではメンバ変数やメンバ関数を自由に使うことが出来ます。

コンストラクタ

std::vector a(3, 1); のように、宣言したときに struct の中身を決められると便利です。 t x(v); とすると a が v で、b がその 2 倍で初期化されるようにしてみます。

#include <iostream>

struct t {
  int a;
  int b;

  t(int v) {
    a = v;
    b = 2 * v;
  }
};

int main() {
  t x(4);
  std::cout << x.a << " " << x.b << " " << t(3).b; // 4 8 6 と表示される
}

型名(引数){処理} のように書いたものをコンストラクタと呼び、変数を宣言する時や、その型の値を作る時に呼ばれる関数になります。メンバ関数とよく似た記法ですが、少しだけ異なります。

コンストラクタでのメンバ変数の初期化

コンストラクタの節で書いたような方法では、メンバ変数が初期化されたのちコンストラクタ内で再び代入されます *1。これは効率が良くないので、いきなり値を決めて初期化する機能が存在します。

#include <iostream>

struct t {
  int a;
  int b;

  t(int v) : a(v), b(2 * v) {}
};

int main() {
  t x(4);
  std::cout << x.a << " " << x.b; // 4 8 と表示される
}

コンストラクタの引数の閉じ括弧の後ろに : を書き、変数名(引数) のように書きます。この初期化ではメンバ変数のコンストラクタが呼ばれています。よって次のようなことも出来ます。

#include <iostream>
#include <vector>

struct t {
  int a;
  std::vector<int> b;

  t(int n) : a(n), b(n, 1) {}
};

int main() {
  t x(2);
  std::cout << x.a << " " << x.b[0] << " " << x.b[1]; // 2 1 1 と表示される
}

t のコンストラクタに n を与えると、a は n、b は n 個の 1 で初期化されます。

Union Find Tree を書いてみる

簡単にするため、経路圧縮だけのものを実装してみます。

#include <iostream>
#include <vector>

struct union_find {
  std::vector<int> par;

  union_find(int n) : par(n) {
    for (int i = 0; i < n; i++) {
      par[i] = i;
    }
  }

  int find(int x) {
    if (par[x] == x)
      return x;
    else {
      par[x] = find(par[x]);
      return par[x];
    }
  }

  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    par[y] = x;
  }
};

int main() {
  union_find uf(3);
  uf.unite(1, 0);
  std::cout << uf.find(0); // 1 と表示される
}

template

a や b が int 以外のものも欲しくなるかもしれません。しかし、double や long など、全ての型について同じものを書くのは大変です。 template と呼ばれる機能を使うことで解決されます。

#include <iostream>

template <class T>
struct t {
  T a;
  T b;
};

int main() {
  t<int> x;
  t<double> y;
  x.a = 3.14;
  y.a = 3.14;
  std::cout << x.a << " " << y.a; // 3 3.14 と表示される
}

template と最初に付け、使う時に型名<型引数> とすることで、任意の型に対して使用することが出来ます。型引数と書いた通り、これは関数と類似した機能です。引数の個数を増やしたりできます。

#include <iostream>

template <class T, class U>
struct t {
  T a;
  U b;
};

int main() {
  t<int, double> x;
  x.a = 2.72;
  x.b = 2.72;
  std::cout << x.a << " " << x.b; // 2 2.72 と表示される
}

a と b の型が異なる場合も自由に使えるようになりました。よく見ると、std::pair と似たような機能、使い方になっています。 std::pair を始めとする標準ライブラリの便利な型の数々も、template を用いて実装されています。

const メンバ関数

a と b の合計を取得するメンバ関数 sum を書いてみます。このメンバ関数は a や b の値を変化させません。 const メンバ関数という機能を使うと、書き換えをコンパイルエラーにすることが出来ます。

#include <iostream>

struct t {
  int a;
  int b;

  int sum() const {
    // a = 3; // コンパイルエラーになる
    return a + b;
  }
};

int main() {
  t x;
  x.a = 2;
  x.b = 3;
  std::cout << x.sum(); // 5 と表示される
}

メンバ関数の引数の閉じ括弧の後ろに const を付けると const メンバ関数となります。間違えて書き換えてしまうことを防止する利点があります。

private

struct 内部でだけ使うメンバ変数やメンバ関数を書くこともあります。外部から触れないようにできれば、誤用を防止できて便利です。

struct t {
  int a;

private:
  int b;
};

int main() {
  t x;
  x.a = 1;
  // x.b = 2; // コンパイルエラーになる
}

private: と書くと、そこから下に書いたメンバ変数やメンバ関数は外部から触れなくなります。逆に public: と書くと、外部から触れるようになります。 struct はデフォルトで public なので、何も書かないと外部から全て触れる状態になります。

class

struct とよく似た機能に class が存在します。この 2 者の違いはデフォルトで public か private かしかありませんので、好きな方を使えばよいです。

static メンバ変数 / static メンバ関数

値ではなく型そのものに紐づいた変数や関数を使いたいときに使用します。割愛。

*1:この例だと int なので未初期化の値になっているのですが、事情が面倒なので割愛します

noshi91のメモ

データ構造のある風景