競プロ struct コンストラクタの使い方 C++

Question

実現したいこと

コンストラクタの理解

前提

コンストラクタはstruct内の変数の初期化を行う部分だと思うのですが、下記コードQ(int k, int i):k(k),i(i) {} で具体的にどういう挙動になるのか、vector<vector<Q>> でどういういいことがあるのかを教えてほしいです。
pair以上の変数の組の配列を扱うのに便利なのかなという印象です

サンプル

ABC 239 E問題
snukeさんのコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)

struct Q {
  int k, i;
  Q(int k, int i):k(k),i(i) {}
};

int main() {
  int n, q;
  cin >> n >> q;
  vector<int> x(n);
  rep(i,n) cin >> x[i];
  vector<vector<int>> to(n);
  rep(i,n-1) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    to[a].push_back(b);
    to[b].push_back(a);
  }
  vector<vector<Q>> qs(n);
  rep(i,q) {
    int v, k;
    cin >> v >> k;
    --v; --k;
    qs[v].emplace_back(k,i);
  }
  vector<int> ans(q);
  const int K = 20;
  auto merge = [&](vector<int>& a, const vector<int>& b) {
    a.insert(a.end(), b.begin(), b.end());
    sort(a.rbegin(), a.rend());
    a.resize(K);
    return a;
  };
  auto dfs = [&](auto f, int v, int p=-1) -> vector<int> {
    vector<int> res(K);
    res[0] = x[v];
    for (int u : to[v]) {
      if (u == p) continue;
      auto d = f(f, u, v);
      merge(res,d);
    }
    for (auto [k,i] : qs[v]) {
      ans[i] = res[k];
    }
    return res;
  };
  dfs(dfs,0);

  rep(i,q) {
    printf("%d\n", ans[i]);
  }
  return 0;
}

補足情報

説明がヘタダヨ～

Comments

[hoshi-takanori]

これかな。
https://www.gocca.work/cpp-initialize-list/

Answer 1

言語機能は様々な相互作用があるので個々の機能については説明しづらいです。 関連する内容を説明しようとするとキリがないので何がわからないのかより具体的な質問になっていることが好ましいです。 体系的に書かれた入門書を読んだ上で具体的に理解できなかったところを質問するようにしてください。 ここで書ける文章量では大雑把な説明しかできません。

C++ では変数の初期化と代入は明瞭に別物です。 コンストラクタ内でデータメンバを初期化するなら初期化のための文法が必要であり、それがメンバ初期化子リストです。 Q(int k, int i):k(k),i(i) {} と書いてあればこれはコンストラクタの本文に入る前にデータメンバの k と i が初期化されます。 (データメンバと仮引数の名前がかぶっても問題ありません。 一致させるほうが良いという流派と異なる名前にしたほうが良いという流派があるのでそこらへんは流儀の問題です。)

メンバ初期化子リストに含まれないデータメンバについては原則としてはデフォルトコンストラクタ (引数を取らないコンストラクタ) で初期化されます。 ただしトリビアルな型については未初期化という扱いです。 (「トリビアル」の定義についてはここでは述べません。)

データメンバのコンストラクタの起動順序はクラス定義内でのデータメンバの宣言の順序になるというのも要注意です。 たとえばメンバ初期化子リストの順序を変えて

struct Q {
  int k, i;
  Q(int k, int i): i(i), k(k) {}
};

と書いたとしても宣言順序としては k i なので k が初期化されてから i が初期化されます。 (コンパイラやオプションによっては宣言順序とメンバ初期化子リストの順序を一致させるように警告を出すこともあります。)

---

vector<vector<Q>> でどういういいことがあるのかを教えてほしいです。
pair 以上の変数の組の配列を扱うのに便利なのかなという印象です

要素の数が事前に決まっているときは std::array や std::tuple などを使ったほうが便利なことも多いです。 つまり、逆に言えば std::vector が便利なときというのは大きさが事前にわからないときです。 大きさを柔軟に変動できるという部分に意味があると解すべきでしょう。

また、 std::vector は内部のレイアウトが配列と互換性があるので配列を前提とした関数を利用する必要があるときに便利なこともあります。 (競技プログラミングではあまり関係ないと思いますが。)