こんにちは、42Tokyo Advent Calendar 2021 の6日目を担当する、在校生のnafukaです。
先日、42Tokyo の課題でC++のSTLコンテナを再実装しました。
この記事では、課題で学んだことを振り返りたいと思います。
どちらかというと42Tokyoの学生向けの内容となっていますが、学生以外の方でも42Tokyoでどんなことを行っているか、参考になるかもしれません。
課題の概要
STLコンテナとは
STLとは「Standard Template Library」の略で、C++の標準ライブラリの1つです。
その名の通りテンプレートを使ったライブラリで、以下の機能を提供しています。
- コンテナ：データの格納（データはテンプレート引数にし、格納方法だけクラスで定義する）
- イテレータ：データの要素アクセス
- アルゴリズム：イテレータを介したデータの操作
- 関数オブジェクト：処理のクラス（行いたい処理を引数に渡せる）
コンテナ、イテレータ、アルゴリズムの関係を図にすると、以下のようになります。
今回は、コンテナ以外にも、コンテナに結びつくイテレータ、およびアルゴリズムの一部を再実装することになります。
また、コンテナの一部では関数オブジェクトを使用します。
再実装する内容
再実装するSTLコンテナは以下です。これらコンテナのイテレータも実装が必要です。
- vector（vector<bool> 以外）
- 要素の追加/削除によって再確保が起こる配列。
- map
- 辞書のような、キーとそれに対応する値を持ったデータ構造。
- stack
- 後入れ先出しのデータ構造。
- set（ボーナス課題。やらなくてもよい）
- 要素の重複のない集合。
STLコンテナ以外には、以下のクラス/構造体も再実装が必要になります。
- iterators_traits, reverse_iterator
- enable_if, is_integral
- equal, lexicographical compare
- pair, make_pair
その他の制約
再実装では実行速度の制限があります。実装元のSTLコンテナの20倍まで許容されます。
再実装にあたり、リファレンスが指定されています。
cplusplus.com と cppreference.com（以下cplusplus、cppreferenceと略します）を参照できます。
課題で得られたこと
- コンテナの内部実装、データ構造
- 計算量を実現するための実装方法が分かりました。
- 型から型を取り出す面白さ
enable_ifやis_integralでテンプレート引数から型を取り出せるのがとても面白かったです。
- リファレンスサイトではなく規格を読むことの大切さ
- これについては「取り組み」の「大変だったこと」で詳しく書きます。
成果物
取り組み
流れ
いきなりコンテナから実装するのは実装量が多く大変そうだったので、最初はコンテナ以外の enable_if, is_integral などを実装しました。
enable_if, is_integral の実装には『プログラミング言語C++ 第4版』を参考にしました。
その後、vector→map→stack→setの順にコンテナを実装しました。
コンテナ実装にあたり、まず 江添亮の入門C++ の「vectorの実装」を読んで実装の大まかな流れを掴みました。
江添亮の入門C++では、イテレータがポインタになっているため、イテレータの実装について調査しました。reverse_iterator の実装が参考になりました。
コンテナの各関数については、cplusplus と Clang、GCCのソースを参考にしました。
実装
各コンテナ
vector, mapについては記事を書いたので、そちらを参照ください。
stackはコンテナのラッパーです。コンテナの末尾に要素を追加/削除することで、スタックのような後入れ先出しのデータ構造を実現します。
実装はラップしたコンテナのメンバ関数を呼び出すだけです。
setはmapのkeyがない版です。木を持ち、mapと同じように木のメンバ関数を呼び出します。
テスト
C++でテストコードを作成し、それをShellScriptでラップしました。
テストでは、関数の出力、各関数の実行速度をSTLコンテナと自作コンテナとで比較します。
大変だったこと
リファレンスの差異と規格探し
リファレンスサイトは cplusplus と cppreference が指定されているのですが、それぞれで関数定義が異なりました。
具体的には、map::at や reverse_iterator::operator= など、cppreference にあって、 cplusplus にない関数がありました。
どちらが正しいのか知るため、C++98の規格を探しました。
まず、こちらのサイトを参考に、C++03のJIS規格を見たのですが、英字が文字化けしていて読めませんでした。
次に、「ISO/IEC 14882:1998」でググって出てきたpdfを見ました。これは多分C++98の規格な気がします……がネットに落ちてるものなので、信頼できるものなのか分かりません。
とりあえず見たところ、 map::at と reverse_iterator::operator= はpdfにありませんでした。
どちらかと言うと、cplusplusの方が規格に沿っている部分が多いのかもしれません。
ただ、全てが合っているわけではなさそうです。cplusplusだと iterator_traits はstructではなくclassになっていました。
レビューでの説明
42では、課題は学生同士のコードレビューで評価されます。
レビュー相手は誰になるか分かりません。C++を学んだことがない方とマッチする可能性もあります。
今回の課題は、
です。これにより、全体像を把握せずレビュアーがコードを見ると、どこに着目すればいいか分からない状態になることが予想されました。
そのため、全体像を把握するためのスライドを作成しました。テキストでもいいのですが、データ構造は図にした方が分かりやすいので、スライドにしました。
赤黒木についても、実装が複雑だったので別でスライドを作成しました。
42において、コードレビューはお互いの学びを深める場です。
課題の詳細を全て説明するよりも、ざっくり課題の概要を説明した後にMakefileやC言語のことを話した方が、場合によっては相手の学びにつながることがあります。
（もちろん場合によります。相手の理解度に合わせて柔軟に説明内容を変え、学びをなるべく多くするのが大切だと思っています）
スライドが相手の学びを深めるためにも役立ったかなと思います。
レビュー用の資料を作っておくと、後で自分が忘れても読み返せたり、これから課題に取り組む人が参照できるのでとてもおすすめです。
参考にした書籍・URL
URL
- 江添亮の入門C++
- 「vectorの実装」が参考になりました。
- hacking C++
- 各コンテナを図で説明していて分かりやすいです。
書籍
コンテナ、イテレータ、アルゴリズムの説明が分かりやすいです。
enable_ifの実装が参考になります。
赤黒木の実装で参考にしました。擬似コードが載っています。オススメの読む順番は、付録 B.5 木 → 12. 2分探索木 → 13. 2色木 です。
終わりに
この記事がどなたかの参考になれば幸いです。
明日は、hosuzukiさんが
プログラミング未経験者が42Tokyoの入学試験「Piscine」に合格のするためにした「ありとあらゆる前準備」（39日間）
について書いてくださる予定だそうです。そちらの記事もお楽しみに！
追記
hosuzukiさんの記事が公開されました！以下からアクセスできます。 note.com
また、42Tokyoのアドベントカレンダーから他の方が書いた記事を見ることができます。こちらも是非参照ください。 qiita.com
