複合データ：まとめと挑戦課題

単元で達成したこと

この単元は、データのコレクションを表し、それを基本的なアルゴリズムで処理し、そのコストを見積もることを教えようとした。この目的は、導入が既知と宣言したことだけに基づいて果たされた。不変条件をもつループ、関数とその渡し方、整数の算術である。五つの変数で余ったデータを黙って捨てていた得点のプログラムは、今ではベクターで書かれる。また、すべての組を調べると百万個のデータに数分かかっていた同点の問いには、ソートして隣どうしを比べることで答えられる。

配列

レッスン 配列は、サイズが固定された並びである std::array を紹介した。その添字はオフセットなので、ゼロから数える。添字 $i$ が有効であるのは $0 \leq i < n$ のとき、かつそのときに限ること、[] による各アクセスはそれをループの不変条件で証明することを求めること、そして範囲外アクセスは未定義動作であり、.at() はそれを定められた停止に変えることを確立した。さらに std::size_t を導入し、C 言語の配列の読み方を教えた。

ベクター

レッスン ベクターは、push_back で伸びる並びを紹介し、データの列を保存しなければならないのはいつかを定めた。あるデータについての判断が後のデータに依存する場合である。定番の走査（集約・抽出・変換）を、その不変条件とライブラリでの略記（std::ranges::count、std::ranges::max、std::ranges::fold_left）とともに確立し、ベクターの渡し方の規則と、サイズと容量の違いを示した。この違いから、push_back の平均して一定のコストと、ベクターが引っ越すときの参照の無効化が導かれる。

アルゴリズムのコスト

レッスン アルゴリズムのコストは、二つ目の問いを加えた。最悪の場合の支配的な演算を数えること、増加のオーダーで分類すること、$n$ を 2 倍にしたときの効果を予測すること、そして std::chrono::steady_clock で、最適化を付け、サニタイザなしで、繰り返して中央値を取って測定することである。

探索とソート

レッスン 探索とソートは、二分探索をその不変条件と尺度で正当化し、選択ソートと挿入ソートを書いてその比較回数を数え、範囲ライブラリのアルゴリズムを、誰も確かめない整列済みという事前条件とともに紹介し、探索の前にソートしたほうが得になるのはいつかを計算した。

表

レッスン 表は、表を行ごと・列ごとに走査し、転置と行列の積をその 3 乗のコストとともに計算し、端からはみ出さずに隣接マスを数え、表を添字 $i \cdot \mathit{columns} + j$ によって一次元化したベクターに保存した。

レコード

レッスン レコードは、並列配列を、各フィールドに初期値をもつ struct に置き換えた。レコードの渡し方と返し方、射影を使ってフィールドでレコードをソートし探索する方法、std::ranges::stable_sort で複数の基準により整列する方法、そしてレコードとベクターを含むレコードで問題をモデル化する方法を教えた。