C++ STLのコンテナ型を動作効率を考えて使いこなす！

C++の標準ライブラリには、STLの「コンテナ型」という、特定の型の値を複数格納するための型があります。代表的なものとしては、vectorという可変長配列のための型があります。
しかしC++には、配列のためのコンテナ型であっても他にlistやdequeなどが存在しています。それは「動作効率を考えたときに、状況次第で使い分けるべきもの」であるためなのです。
本講座では、それぞれのコンテナ型の特徴や使い分けについて、一般的な話も含め説明していきます。また「どのような場合にどのコンテナ型を選ぶべきか」という指針についても示します。

【キーワード】

本講座内で説明する事項のうち、代表的なキーワード（C++に特化したわけではない用語として）を示します。

• 基本：配列、連想配列、連結リスト、二分探索木、ハッシュテーブル、時間計算量・空間計算量（定数時間・対数時間・線形時間など）、ソート

• 応用：ならし時間計算量（ならし定数時間など）

もしこれらのキーワードの大部分について、挙動などを詳しくご存知であれば、本講座での新たな学びは少ないかもしれません。逆に本講座でこれらのキーワードを知り、より詳しく学びたいと思った方については、これらのキーワードを活用していただければと思います。

【主に扱う型】

vector, array, deque, list (forward_listを含む), set (unordered_set, multisetなどを含む), map (unordered_map, multimapなどを含む)

【各節の内容】

• 第0節「はじめに」：この講座で何を学んでいただくかをお話しします。<プレビュー可>

• 第1節「コンテナ型を使い分けたい場面とは」：コンテナ型を使い分ける典型的な例を示します。具体的にはvectorとlistの挙動の比較を、いくつかのタスクについて行います（例：途中の要素を削除する）。<プレビュー可>

• 第2節「vector型の基本」：基本的な使い方や、メモリ効率に関わる使い方（例：reserveメソッド）を解説します。<第2.1節プレビュー可>

• 補足A「vectorのメモリ量の増え方について」：vectorの大きさを自動的に増やしていく場合の、メモリ消費の増え方について解説します。

• 第3節「その他のコンテナ型の概要」：コンテナ型の分類や、それぞれの実装について解説します。<第3.1節プレビュー可>

• 第4節「コンテナ型の使い分け：事例別」：事例に基づいて、使い分けの基準を示します。<第4.0節プレビュー可>

  • 第4.1節「取得したい要素の指定方法による使い分け」：「●番目の要素を取り出したい」「存在するか確認できればよい」など、取り出す手段での分類です。

  • 第4.2節「要素追加・削除の方法による使い分け」：そのコンテナ型にどんな変更が加わるかによる分類です。

  • 第4.3節「メモリ消費量による使い分け」

• 第5節「実際に使い分けを考えてみる」：問題を用意しています。考えてみてください。

• 第6節「STLをさらに活用する」：「コンテナアダプタ」「<algorithm>」といった、コンテナ型の利用に関連したライブラリの機能について解説します。

• 第7節「おわりに」