初めに
C++において、vectorを要素の宣言の仕方によっては、2次元配列のように扱えることについて学習した記事です。
結論から言うと、vector bucket(n, vector(0))はジャグ配列であり、2次元配列として扱えます。
bucket[i]に収められているint型の配列を、bucket[i][j]で1要素ずつ取り出せます。
(ただvector(0)と要素数が0として宣言しているので、この場合正しく要素を追加してあげる必要があります)
ご指摘あればコメントでお願いいたします。
きっかけ
C++で競技プログラミングサイトAtCoderの過去問
「ABC323 B - Round-Robin Tournament」
のユーザ解説を見ていて引っかかる点があった(2点目)。
26行目のこの部分。
vector bucket(n, vector(0));
この変数bucketは、パッと見る限り1次元のvector。
こちらもさらっと流しそうになったのだが、2次元配列として扱っている。
27～29行目の
for (int i=0; i<n; i++){
bucket[wins[i]].push_back(i);
}
で要素を追加しているのだが、1行に複数の要素を追加することが可能。
つまり、実質2次元配列として扱っている。
ただこの宣言の仕方だと、1次元配列じゃないのか？と疑問を持ったため、理解が滞る。
なぜ躓いたか
vectorの宣言の仕方を調べてみると、やはり1次元配列である(ように見える)ため。
(このような有用な知識を残してくださった方に多謝)
1次元配列
1次元配列のvectorの宣言は以下．Type部にはint，doubleなどの基本的な型のみならず，自分で作成したclassなども使用できる．
ここで，nは要素数を表し，dは初期化する値を表すものとする．
declaration_1d
vector<Type> v;
vector<Type> v();
vector<Type> v(n);
vector<Type> v(n, d);
2次元配列
2次元配列のvectorの宣言は以下．
ここで，mはnと同様，要素数を表すものとする．
g++のバージョンによっては>>は> >と間に半角スペースがないといけないこともあるので，注意が必要である．
declaration_2d
vector<vector<Type>> vv;
vector<vector<Type>> vv();
vector<vector<Type>> vv(n);
vector<vector<Type>> vv(n, vector<Type>(m));
vector<vector<Type>> vv(n, vector<Type>(m, d));
2次元配列として扱うのなら、この場合
vector<vector<int>> bucket(n, vector<int>(0));
として宣言しなければならないはず。
外側のvectorの要素数n、内側のvectorの要素数0、それぞれint型として宣言しなければならないはずでは？
ネットで再度調べてみたが、やはり明解なドキュメントは見つからず。
結局、再度ChatGPT(3.5)に質問してみることに。
ChatGPTに頼る
前回同様、誤答もありえるため、裏付けをとるように心がける。
質問してみたところ、以下回答が得られた。
いいえ、上記のコードは2次元のベクターではありません。実際には1次元のベクター（bucket）で、各要素が1次元のベクター（vector(0)）です。
このコードでは、サイズnで初期化されたbucketという名前の1次元ベクターを作成しています。各要素は空の1次元ベクターです。
つまり、要素へアクセスするためには bucket[i] のように書きますが、それぞれの要素自体も vector 型なので2次元配列として利用することも可能です。
例えば以下のようにして2次元配列と同様に扱うことができます：
int value = bucket[i][j];
ただし、実際には各要素がサイズ0（空）で初期化されているため、必要な場合は適切なサイズを指定して初期化する必要があります。例えば：
vector<vector<int>> bucket(n, vector<int>(m));
このようにすれば、n行m列の2次元配列を作成することができます。
と回答が得られた。
つまり、
- 1次元のvectorで正しい
- ただし、各要素がさらに1次元のvectorなので、個別の要素にアクセスする際には変数名[i][j]のように2次元配列として扱うことが可能
ということだった。
残念ながらこちらは裏付けとなるwebページが見つからなかった(自身の探し方に問題があるとは思うが)。
……と思ったが
ただ、前回の拙記事のコメントにて、ジャグ配列という概念をご教示いただいたので、今回の件もvector型のジャグ配列だと理解できた。
簡単に言うと、「配列の各要素が配列」となっており、各要素数が行ごとに異なっているのを許容する配列。
1次元配列のような見かけながら、2次元配列として振舞える。
大元のABC323のユーザ解説にもある通り、
push_back(i);
関数で各行に要素を追加し、結果的に2次元配列としてのふるまいを見せている。
結論
vector bucket(n, vector(0))は、1次元配列であるが、2次元配列の振る舞いもできる。
bucket[i]に収められているint型の配列を、bucket[i][j]で各行の要素にアクセスできる。
振り返り
脱線するが、ユーザ解説31～32行目の
// さきほど, 番号の小さい順に bucket に入れたので,
// bucket[i] の中身は, すでに番号の小さい順になっている.
というコメントにもある通り、bucketの中身を追加する処理内で
同順位の場合、順番が若いプレイヤーを上位にするという問いの条件を達成していてエレガントだと思った。
C言語の拡張版という認識のC++、ということからかなり窮屈な印象を持っていた。
しかし、慣れていないというのもあるが、結構柔軟な言語なのかもしれないと思った解説だった。