Chapter 04: Containers¶
Chapter 04 Containers についてのノート。|
4.1 Linear Container¶
std::array¶
これはさすがに時間をかけずに理解できる。std::vector にメソッド
shrink_to_fit が追加されていることにむしろ注目したい。
std::forward_list¶
使い方は std::list と同様。
std::listの二重リンクリストの実装とは異なり、std::forward_listは単一リンクリストを使用して実装されている。複雑さ \(O(1)\) の要素挿入を提供し、高速ランダムアクセスをサポートしない（リンクリスト共通の特徴）。
標準ライブラリコンテナーの中で
size()を提供しない唯一のコンテナー。双方向の反復処理が必要ない場合、
std::listより空間利用率が高い。
4.2 Unordered Container¶
従来の C++ からある順序付きコンテナー std::map/std::set のおさらいから。
これらの型は内部的には赤黒木で実装されている。
挿入と検索の平均的な複雑さは \(O(\log(N))\) だ。
要素を挿入する際には、演算子
operator<に従う。コンテナー内の要素を走査する場合、この順序による。
本節で紹介されるコンテナーでは、要素はソートされておらず、内部はハッシュ表で実装されている。要素の挿入と検索の平均的な複雑さは \(O(1)\) であり、要素の順序を気にすることなく、大幅な性能向上を達成することができる。
C++11 から次の四種のコンテナーが利用可能：
std::unordered_mapstd::unordered_multimapstd::unordered_setstd::unordered_multiset
利用方法はそれぞれ対応する順序付きコンテナーと同様。
4.3 Tuples¶
Python プログラマーなので、この型の概念はすでに習得済みだ。操作方法に集中できる。
Basic Operations¶
中核となる機能は次の三つ（いずれもフリー関数の形式であることに注意）：
関数 |
操作 |
|---|---|
|
生成する |
|
要素を得る |
|
unpack する |
get() はテンプレート引数に型を指示するか、インデックスを指示する：
std::tuple<std::string, double, double, int> t("123", 4.5, 6.7, 8);
std::cout << std::get<std::string>(t) << std::endl;
std::cout << std::get<double>(t) << std::endl; // illegal, runtime error
std::cout << std::get<3>(t) << std::endl;
読者ノート
tie() については、もっと簡潔な記法があったと以前述べられていた：
// double gpa;
// char grade;
// std::string name;
auto [gpa, grade, name] = get_student(1);
tuple オブジェクトのメンバーすべてを得るときにしかできない方法だということに注意する。
Runtime Indexing¶
get() でインデックスを指示するのは（テンプレート引数で行うので）コンパイル時に限る。これを動的に指定するには C++17 から用意されている std::variant を用いる。本書のようなテンプレート関数 tuple_index を自前で書く必要がある。
Merge and Iteration¶
二つの
tupleオブジェクトを結合するにはstd::tuple_catを用いる。std::tuple_size<T>::valueでtupleの長さをコンパイル時に得る。
Conclusion¶
現代 C++ の新しいコンテナーの使い方は、従来の C++ からある既存コンテナーと同様だ。
std::tuple は効果的だが、標準ライブラリーでは機能が限られている。実行時のインデックスや反復処理の要件を満たす方法がない。やるなら方法を自前で実装する。
