C++/標準ライブラリ/イテレータライブラリ

C++
イテレータライブラリ

C++のイテレータライブラリは、コンテナ (コンテナライブラリ containers) 内の要素を反復処理するための仕組みを提供します。イテレータは、コンテナ内の要素を一つずつ指す「仮想的なポインタ」のようなもので、コンテナの種類に依存しない統一的な方法で要素にアクセスすることができます。

ヘッダー一覧[編集]

この章で扱うヘッダーファイルは以下の通りです。

イテレータ要件: <iterator>

イテレータ要件[編集]

25.3 Iterator requirements (iterator.requirements)[編集]

25.3.1 In general (iterator.requirements.general)[編集]

イテレータの概要
イテレータはポインタの一般化であり、C++プログラムが異なるデータ構造（例：コンテナやレンジ）を一様な方法で操作できるようにするためのものです。テンプレートアルゴリズムが異なる種類のデータ構造に対して正しく効率的に動作するように、ライブラリはイテレータのインターフェースだけでなく、セマンティクスや複雑性の仮定も形式化しています。例えば、入力イテレータ i は *i という式をサポートし、これはイテレータの値型と呼ばれるあるオブジェクト型 T の値を返します。出力イテレータ i は間接的に書き込み可能な型 T のセットを持ち、 *i = o という式が T 型の値 o に対して有効です。すべてのイテレータ型 X には対応する符号付き整数型があり、これをイテレータの差分型と呼びます。
ポインタの抽象化
イテレータはポインタの抽象化であり、そのセマンティクスはC++のポインタのほとんどのセマンティクスの一般化です。これにより、イテレータを受け取る関数テンプレートは通常のポインタでも動作します。この文書では、定義された操作に基づいてイテレータを以下の六つのカテゴリに分類します：入力イテレータ、出力イテレータ、前進イテレータ、双方向イテレータ、ランダムアクセスイテレータ、および連続イテレータ（表85参照）。
カテゴリの関係

Contiguous → Random Access → Bidirectional → Forward → Input

→ Output
イテレータのカテゴリと概念
六つのイテレータカテゴリは以下のイテレータ概念に対応します：
- input_iterator
- output_iterator
- forward_iterator
- bidirectional_iterator
- random_access_iterator
- contiguous_iterator
一般的な用語としてのイテレータは、 input_or_output_iterator 概念をモデル化する任意の型を指します。
イテレータの互換性
前進イテレータは入力イテレータの要件を満たし、前進イテレータが指定される場合に使用できます。同様に、双方向イテレータは前進イテレータの要件を満たし、ランダムアクセスイテレータは双方向イテレータの要件を満たし、連続イテレータはランダムアクセスイテレータの要件を満たします。
可変イテレータと定数イテレータ
出力イテレータの要件をさらに満たすイテレータは可変イテレータと呼ばれます。非可変イテレータは定数イテレータと呼ばれます。
ネストされたtypedef名
このサブクローズで定められた要件に加えて、イテレータ型には 25.3.2.3 で指定されたネストされたtypedef名を提供する必要があります。これらのtypedef名は直接提供されるか、 iterator_traits 特化がそれらを提供する必要があります。
配列と同様のポインタ保証
配列のポインタが最後の要素の後を指すポインタ値を保証するのと同様に、任意のイテレータ型には対応するシーケンスの最後の要素の後を指すイテレータ値が存在します。このような値をpast-the-end値と呼びます。*i が定義されるイテレータ i の値をdereferenceable（参照可能）値と呼びます。past-the-end値は参照可能であると仮定しません。イテレータには、どのシーケンスにも関連付けられていないsingular（単一）値もあります。ほとんどの式の結果はsingular値に対して未定義です。
レンジを使うアルゴリズムテンプレート
ライブラリのアルゴリズムテンプレートの多くは、レンジを使用します。レンジは計算の始まりと終わりを指定するイテレータとセンチネル、または計算を適用する要素数を指定するイテレータとカウントです。
レンジの比較と範囲
イテレータとセンチネルは比較可能です。レンジ [i, s) が空であるのは i == s の場合です。そうでなければ、 [i, s) はデータ構造の最初の要素 i から s と等しい最初のイテレータ j までの要素を指します。
センチネルの到達可能性
センチネル s がイテレータ i から到達可能であるのは、有限回の ++i の適用で i == s となる場合のみです。s が i から到達可能である場合、 [i, s) は有効なレンジを示します。
カウントされたレンジ
カウントされたレンジ i + [0, n) は n == 0 の場合空です。そうでなければ、 i + [0, n) は i から始まり、 ++i の n 回の適用によって指される要素までの n 個の要素を指します。カウントされたレンジが有効であるのは、 n == 0 であるか、 n が正であり、 i が参照可能で、++i + [0, --n) が有効である場合のみです。
無効なレンジへのライブラリ関数の適用
無効なレンジに対するライブラリ関数の適用結果は未定義です。
定数時間で実現可能な関数のみ
すべてのイテレータカテゴリは、定数時間（平滑化された）で実現可能な関数のみを要求します。したがって、イテレータの要件テーブルおよび概念定義は複雑性を指定しません。
非前進イテレータの破壊
非前進イテレータの破壊は、そのイテレータから以前に取得したポインタおよび参照を無効にする場合があります。
無効なイテレータ
無効なイテレータとは、singular値である可能性のあるイテレータを指します。
constexprイテレータ
イテレータカテゴリの要件を満たすすべての操作が constexpr 関数であるイテレータを constexpr イテレータと呼びます。例えば、 int へのポインタ型や reverse_iterator<int*> は constexpr イテレータです。

イテレータの基本操作[編集]

25.4 Iterator primitives (iterator.primitives)[編集]

25.4.1 General (iterator.primitives.general)[編集]

イテレータの利用の簡略化
イテレータの使用を簡略化するために、ライブラリはいくつかのクラスと関数を提供します。

25.4.2 Standard iterator tags (std.iterator.tags)[編集]

標準イテレータタグ
関数テンプレートの特殊化が、イテレータ引数の最も特定のカテゴリを見つけることがしばしば望まれます。そうすることで、関数はコンパイル時に最も効率的なアルゴリズムを選択できます。そのために、ライブラリではアルゴリズム選択のためのコンパイル時タグとして、以下のカテゴリタグクラスが導入されます：
- output_iterator_tag
- input_iterator_tag
- forward_iterator_tag
- bidirectional_iterator_tag
- random_access_iterator_tag
- contiguous_iterator_tag
すべての I 型のイテレータに対して、iterator_traits::iterator_category が定義され、イテレータの動作を説明するカテゴリタグである必要があります。さらに、 iterator_traits::iterator_concept はイテレータコンセプトへの適合性を示すために使用されることがあります。

例示
イテレータ BinaryTreeIterator<T> を双方向イテレータカテゴリに含めるには、 iterator_traits テンプレートを特殊化します。

25.4.3 Iterator operations (iterator.operations)[編集]
イテレータ操作
ランダムアクセスイテレータのみが + と - 演算子を提供するため、ライブラリは2つの関数テンプレート advance と distance を提供します。
25.4.4 Range iterator operations (range.iter.ops)[編集]
25.4.4.1 General (range.iter.ops.general)[編集]
レンジイテレータ操作
イテレータを操作するための関数テンプレート ranges::advance, ranges::distance, ranges::next, ranges::prev がライブラリに含まれています。これらの操作は、各イテレータカテゴリが提供する演算子セットに適応して、具体的なイテレータ型に対して可能な限り効率的な実装を提供します。
イテレータアダプタ[編集]
25.5 Iterator adaptors (predef.iterators)[編集]
イテレータアダプタは、既存のイテレータを変換したり、機能を追加したりするためのツールです。このセクションでは、イテレータアダプタについて説明されています。
25.5.1 Reverse iterators (reverse.iterators)[編集]
逆行イテレータ(Reverse iterators)は、元のシーケンスの終わりから始まりに向かって反復するイテレータアダプタです。つまり、シーケンスの末尾から始まりに向かって進むようにイテレータを変換します。
25.5.1.1 General (reverse.iterators.general)[編集]
クラステンプレート reverse_iterator は、その基礎となるイテレータによって定義されたシーケンスの末尾からその始まりまで反復するイテレータアダプタです。これは、与えられたイテレータがシーケンスの最後の要素を指すように変換され、その後に前の要素を指すように動作します。
ストリームイテレータ[編集]
25.6 Stream iterators (stream.iterators)[編集]
このセクションでは、ストリームイテレータについて説明されています。これらのイテレータは、入力や出力ストリームとの連携を容易にするためのクラステンプレートです。
25.6.1 General (stream.iterators.general)[編集]
アルゴリズムがストリームと直接やり取りできるようにするために、適切なイテレータのようなクラステンプレートが提供されています。例えば、`partial_sum` は、`cin` から浮動小数点数を読み取り、その部分和を `cout` に出力します。
25.6.2 Class template istream_iterator (istream.iterator)[編集]
25.6.2.1 General (istream.iterator.general)[編集]
istream_iterator クラステンプレートは、構築された入力ストリームから連続する要素を読み取る入力イテレータです。このクラスは、入力イテレータのカテゴリに属し、基本的な操作や振る舞いを提供します。
25.6.2.2 Constructors and destructor (istream.iterator.cons)[編集]
istream_iterator は、デフォルトコンストラクタやストリームからの要素の読み取りをサポートするコンストラクタなど、複数のコンストラクタを提供しています。これらのコンストラクタは、イテレータを適切に初期化します。
25.6.2.3 Operations (istream.iterator.ops)[編集]
istream_iterator は、デリファレンスや前置・後置増分演算子など、イテレータが持つ基本的な操作を提供しています。これらの操作は、入力ストリームからの要素の読み取りやイテレータの進行を処理します。
25.6.3 Class template ostream_iterator (ostream.iterator)[編集]
25.6.3.1 General (ostream.iterator.general)[編集]
ostream_iterator クラステンプレートは、構築された出力ストリームに連続する要素を書き込むための出力イテレータです。これは、出力ストリームに対する基本的な書き込み操作を提供します。
25.6.3.2 Constructors (ostream.iterator.cons)[編集]
ostream_iterator は、出力ストリームに対する書き込みをサポートするコンストラクタを提供しています。これらのコンストラクタは、出力イテレータを適切に初期化します。
25.6.3.3 Operations (ostream.iterator.ops)[編集]
ostream_iterator は、出力ストリームに対する書き込み操作を実行するための操作を提供しています。これには、要素の書き込みやイテレータの進行を処理する演算子が含まれます。
25.6.4 Class template istreambuf_iterator (istreambuf.iterator)[編集]
25.6.4.1 General (istreambuf.iterator.general)[編集]
istreambuf_iterator クラステンプレートは、構築されたストリームバッファから連続する文字を読み取る入力イテレータを定義します。このクラスは、入力イテレータのカテゴリに属し、基本的な操作や振る舞いを提供します。
25.6.4.2 Constructors (istreambuf.iterator.cons)[編集]
istreambuf_iterator のコンストラクタは、ストリームバッファからの文字の読み取りをサポートします。これらのコンストラクタは、イテレータを適切に初期化します。
25.6.4.3 Operations (istreambuf.iterator.ops)[編集]
istreambuf_iterator は、ストリームバッファからの文字の読み取りやイテレータの進行を処理するための操作を提供します。これには、デリファレンスや前置増分演算子などが含まれます。
25.6.5 Class template ostreambuf_iterator (ostreambuf.iterator)[編集]
25.6.5.1 General (ostreambuf.iterator.general)[編集]
ostreambuf_iterator クラステンプレートは、構築されたストリームバッファに連続する文字を書き込むための出力イテレータを定義します。これは、出力イテレータのカテゴリに属し、基本的な操作や振る舞いを提供します。
25.6.5.2 Constructors (ostreambuf.iter.cons)[編集]
ostreambuf_iterator のコンストラクタは、ストリームバッファへの書き込みをサポートします。これらのコンストラクタは、イテレータを適切に初期化します。
25.6.5.3 Operations (ostreambuf.iter.ops)[編集]
ostreambuf_iterator は、ストリームバッファへの書き込み操作を実行するための操作を提供します。これには、文字の書き込みやイテレータの進行を処理する演算子が含まれます。

コンテナライブラリ C++
イテレータライブラリ レンジライブラリ