---

C++ Iteratorの基本 – 種類と役割を理解する

はじめに：なぜC++プログラミングにイテレータが不可欠なのか

C++で効率的かつ汎用的なプログラミングを行う上で、イテレータ（iterator）は欠かせない要素です。特にSTL（Standard Template Library）を利用する際には、イテレータの概念とその使い方を深く理解することが非常に重要となります。イテレータは、コンテナ（要素の集合を保持するデータ構造、例: std::vector, std::list, std::mapなど）の要素にアクセスし、それらを順次処理するための抽象化されたメカニズムを提供します。

では、なぜイテレータが必要なのでしょうか？ C言語には配列とポインタがあり、配列の要素にはポインタを使ってアクセスできます。C++の配列も同様です。しかし、STLには配列以外にも、リスト、ツリー、ハッシュテーブルなど、様々な内部構造を持つコンテナがあります。これらのコンテナの要素にアクセスする方法は、その内部構造によって異なります。例えば、配列やstd::vectorは要素が連続したメモリに配置されているため、ポインタ演算（p++, p + nなど）で要素間を移動できますが、std::listのような双方向リンクリストでは、各要素はポインタで繋がっており、連続したメモリには配置されていません。この場合、ポインタ演算で次の要素に移動することはできません。

もし、各コンテナごとに異なるアクセス方法をアルゴリズム（要素を操作する関数、例: ソート、検索、コピーなど）に要求するとしたら、同じ「検索」という処理でも、std::vector用、std::list用、std::map用と、コンテナの数だけ異なるバージョンのアルゴリズムを作成しなければならなくなります。これは非効率的であり、コードの再利用性を著しく低下させます。

ここでイテレータが登場します。イテレータは、コンテナの内部構造を隠蔽し、要素へのアクセスと移動を標準化するための「ポインタのような」オブジェクトです。異なる種類のコンテナであっても、イテレータという共通のインターフェースを通じて要素にアクセスし、次の要素へ進むことができるようになります。これにより、アルゴリズムは特定のコンテナ型に依存することなく、イテレータが提供する操作だけを利用して汎用的に記述することが可能になります。

つまり、イテレータはSTLにおけるコンテナとアルゴリズムを繋ぐ橋渡しの役割を果たしているのです。コンテナはイテレータを提供し、アルゴリズムはそのイテレータを使って要素を操作します。この分離こそが、STLの強力な汎用性と柔軟性を実現しています。

この記事では、C++イテレータの基本的な概念から始め、その様々な種類（カテゴリ）とそれぞれの特性、そして具体的な役割について、詳細なコード例とともに深く掘り下げていきます。イテレータをマスターすることは、C++でのデータ構造とアルゴリズムを扱う能力を格段に向上させるでしょう。

1. イテレータの基本概念

イテレータは、コンテナ内の特定の要素を指し示すオブジェクトです。ポインタがメモリ上のアドレスを指すように、イテレータはコンテナが管理する要素の「位置」を抽象的に表現します。イテレータの最も基本的な操作は以下の通りです。

• 要素へのアクセス（Dereference）: * 演算子を使用して、イテレータが指す要素の値を取得または変更します。これはポインタのデリファレンスと同じです。
• 次の要素への移動（Increment）: ++ 演算子を使用して、イテレータをコンテナ内の次の要素に進めます。これはポインタのインクリメントと似ていますが、内部的にはコンテナの構造に応じて異なる処理が行われます。
• イテレータの比較（Comparison）: == および != 演算子を使用して、2つのイテレータが同じ要素を指しているか、または同じ位置（例えばコンテナの終端）を示しているかを比較します。

ほとんどのコンテナは、要素の範囲を示すために、先頭要素を指すイテレータと、最終要素の「次」の位置を指すイテレータを提供します。これらは通常、コンテナのメンバ関数である begin() および end() によって取得できます。

• container.begin(): コンテナの最初の要素を指すイテレータを返します。
• container.end(): コンテナの最後の要素の「次」の位置を指すイテレータを返します。この位置は有効な要素を指しません。イテレータが end() と等しくなったとき、コンテナの全要素を処理し終えたことを意味します。この [begin, end) という半開区間の考え方は、C++の多くのアルゴリズムで利用されています。

簡単な例を見てみましょう。

“`cpp

include

include

int main() {
std::vector numbers = {10, 20, 30, 40, 50};

// begin() と end() を使用してイテレータを取得
std::vector<int>::iterator it = numbers.begin();

// end() に達するまで要素を順に処理
while (it != numbers.end()) {
    // イテレータが指す要素にアクセス
    std::cout << *it << " ";

    // 次の要素へ移動
    ++it;
}
std::cout << std::endl;

return 0;

}
“`

このコードは、std::vectorの要素をイテレータを使って順番に表示しています。*it で現在の要素にアクセスし、++it で次の要素に進んでいます。ループの終了条件は、イテレータが end() が返す位置に達したかどうかです。

C++11以降で導入された範囲ベースforループは、このイテレータを使ったループの糖衣構文（シンタックスシュガー）として機能します。

“`cpp

include

include

int main() {
std::vector numbers = {10, 20, 30, 40, 50};

// 範囲ベースforループ（イテレータが内部で使われている）
for (int number : numbers) {
    std::cout << number << " ";
}
std::cout << std::endl;

return 0;

}
“`

このコードは上記のイテレータを使ったループとほぼ同じ働きをしますが、記述がより簡潔です。しかし、範囲ベースforループは常に begin() から end() までの全要素を順番に処理するため、要素の一部だけを処理したり、複雑な移動（例えば2つ飛ばしや逆順）を行ったりする場合には、明示的にイテレータを使う必要があります。

2. イテレータの種類（カテゴリ）

すべてのコンテナが同じ種類のイテレータを提供するわけではありません。コンテナの内部構造によって、イテレータがサポートできる操作のレベルが異なります。例えば、リンクリストの要素間はポインタで繋がっているため、前後の要素への移動は可能ですが、任意の位置への「ジャンプ」は効率的にできません。一方、配列のように要素が連続していれば、任意の位置へ直接アクセス（ランダムアクセス）できます。

C++標準ライブラリでは、イテレータの機能レベルに応じて以下の5つのカテゴリを定義しています。これらのカテゴリは階層構造になっており、下位のカテゴリの要件を満たすイテレータは、上位のカテゴリの要件も満たします。

1. Input Iterator (入力イテレータ)
2. Output Iterator (出力イテレータ)
3. Forward Iterator (前方イテレータ)
4. Bidirectional Iterator (双方向イテレータ)
5. Random Access Iterator (ランダムアクセスイテレータ)

これらのカテゴリは、イテレータがサポートする操作と、それらの操作に求められるセマンティクス（意味）によって定義されます。アルゴリズムは、必要とする最低限の機能を持つイテレータカテゴリを指定することで、そのアルゴリズムが適用可能なコンテナの種類を限定します。例えば、要素をソートするアルゴリズムは、要素の位置を頻繁に入れ替えたり、任意の位置にジャンプしたりする必要があるため、より高機能なイテレータを要求します。

各イテレータカテゴリについて詳しく見ていきましょう。

2.1. Input Iterator (入力イテレータ)

特徴:

• コンテナから要素を「読み取る」ためのイテレータです。書き込みはできません。
• 進行方向は単方向です（前進のみ）。
• マルチパス保証がありません。 これは、同じイテレータを複数回デリファレンスしたり、コピーしたイテレータで同じ位置を指し続けたりすることが保証されないという意味です。一度要素を読み取ったら、そのイテレータは次の要素へ進むか、あるいは無効になると考えるのが安全です。つまり、「一回限り」の操作に適しています。

サポートする操作:

• *it: 現在の要素を読み取ります。（右辺値としてのみ使用可能）
• it->m: (*it).m と同じ。要素のメンバにアクセスします。
• ++it, it++: 次の要素に進みます。
• it1 == it2, it1 != it2: 2つのイテレータが同じ位置を指しているか比較します。

利用例:

入力ストリームからデータを読み取る std::istream_iterator など。多くの標準アルゴリズムの「入力」部分が要求する最低限のカテゴリです（例: std::find, std::copy）。これらのアルゴリズムは、入力範囲を一度だけ順番に読み取れれば十分です。

“`cpp

include

include

include

include

int main() {
// 標準入力から整数を読み取るInput Iterator
std::istream_iterator input_it(std::cin);
// ストリームの終端を示すInput Iterator
std::istream_iterator end_it;

std::vector<int> numbers;

// std::copy は Input Iterator と Output Iterator を要求
// 標準入力から読み取った整数をvectorにコピー
std::copy(input_it, end_it, std::back_inserter(numbers)); // std::back_inserter は Output Iterator

std::cout << "読み取った数値: ";
for (int n : numbers) {
    std::cout << n << " ";
}
std::cout << std::endl;

return 0;

}
``
この例では、std::istream_iteratorは Input Iterator として振る舞い、標準入力から要素を一度だけ読み取ります。std::copy` アルゴリズムは、入力範囲に対して Input Iterator の機能（読み取り、前進、比較）だけを要求します。

2.2. Output Iterator (出力イテレータ)

特徴:

• コンテナに要素を「書き込む」ためのイテレータです。読み取りはできません。
• 進行方向は単方向です（前進のみ）。
• 同じ位置に複数回書き込むと、最初の書き込み以外の結果は保証されません（通常は上書きされますが、アルゴリズムによっては想定されていない場合があります）。
• マルチpass保証がありません。

サポートする操作:

• *it = value: 現在の要素に値を書き込みます。（左辺値としてのみ使用可能）
• ++it, it++: 次の要素に進みます。

利用例:

コンテナに要素を追加する std::back_inserter, std::front_inserter, std::inserter などのインサートイテレータや、標準出力へデータを書き出す std::ostream_iterator など。多くの標準アルゴリズムの「出力」部分が要求する最低限のカテゴリです（例: std::copy, std::transform）。これらのアルゴリズムは、出力範囲に要素を一度だけ順番に書き込めれば十分です。

“`cpp

include

include

include

include

include

int main() {
std::vector numbers = {1, 2, 3, 4, 5};

// 標準出力へ整数を書き出すOutput Iterator
std::ostream_iterator<int> output_it(std::cout, ", ");

// std::copy は Input Iterator と Output Iterator を要求
// vectorの要素を標準出力にコピー
std::copy(numbers.begin(), numbers.end(), output_it);

std::cout << std::endl;

return 0;

}
``
この例では、std::ostream_iteratorは Output Iterator として振る舞い、標準出力に要素を書き出します。std::copy` アルゴリズムは、出力範囲に対して Output Iterator の機能（書き込み、前進）だけを要求します。

2.3. Forward Iterator (前方イテレータ)

特徴:

• Input IteratorとOutput Iteratorの機能を組み合わせたものです。読み書き両方が可能（または片方のみ）。
• 進行方向は単方向です（前進のみ）。
• マルチパス保証があります。 同じイテレータを複数回デリファレンスしたり、イテレータのコピーを使ったりしても、同じ要素に安定してアクセスできます。これは、同じ範囲を複数回走査するアルゴリズムに適しています。

サポートする操作:

• Input IteratorおよびOutput Iteratorのすべての操作をサポートします（読み書き両方可能な場合）。
• *it = value (書き込み)
• *it (読み取り)
• it->m
• ++it, it++
• it1 == it2, it1 != it2

利用例:

std::forward_list (単方向リンクリスト) のイテレータなど。一部の標準アルゴリズムで利用されます（例: std::replace, std::adjacent_find）。これらのアルゴリズムは、範囲内を複数回走査したり、要素を読み取ってから書き込んだりする必要があるため、Forward Iterator以上の機能が要求されます。

“`cpp

include

include

include

int main() {
std::forward_list numbers = {10, 20, 30, 20, 40};

// std::replace は Forward Iterator を要求
// 値 20 を 25 に置き換え
std::replace(numbers.begin(), numbers.end(), 20, 25);

std::cout << "置換後のリスト: ";
for (int n : numbers) {
    std::cout << n << " ";
}
std::cout << std::endl;

return 0;

}
``std::forward_listのイテレータは前進しかできませんが、要素の読み取りと書き込み（置換）が可能であり、std::replace` アルゴリズムが必要とする Forward Iterator の要件を満たします。

2.4. Bidirectional Iterator (双方向イテレータ)

特徴:

• Forward Iteratorの機能に加えて、後退が可能になります。
• 進行方向は双方向です（前進と後退）。
• マルチパス保証があります。

サポートする操作:

• Forward Iteratorのすべての操作をサポートします。
• --it, it--: 前の要素に後退します。

利用例:

std::list, std::set, std::map, std::multiset, std::multimap などのコンテナのイテレータ。これらのコンテナはノードベースであり、要素は連続したメモリには配置されませんが、各ノードは前後のノードへのポインタを持っているため、双方向に移動できます。std::reverse アルゴリズムなどが要求します。

“`cpp

include

include

include

int main() {
std::list numbers = {1, 2, 3, 4, 5};

// std::reverse は Bidirectional Iterator を要求
std::reverse(numbers.begin(), numbers.end());

std::cout << "反転後のリスト: ";
for (int n : numbers) {
    std::cout << n << " ";
}
std::cout << std::endl;

return 0;

}
``std::listのイテレータは前進と後退が可能であり、std::reverseアルゴリズムが必要とする Bidirectional Iterator の要件を満たします。std::reverse` は範囲の両端からイテレータを動かして要素を交換する必要があるため、双方向の移動が必要です。

2.5. Random Access Iterator (ランダムアクセスイテレータ)

特徴:

• Bidirectional Iteratorの機能に加えて、任意の位置への高速なジャンプ（ランダムアクセス）が可能になります。
• 要素がメモリ上で連続して配置されている場合に提供されます。
• 進行方向は双方向です。
• マルチパス保証があります。

サポートする操作:

• Bidirectional Iteratorのすべての操作をサポートします。
• it + n, n + it: イテレータをn要素だけ前進させます。
• it - n: イテレータをn要素だけ後退させます。
• it1 - it2: 2つのイテレータ間の要素数を計算します。
• it[n]: *(it + n) と同じ。現在の位置からn要素離れた位置の要素にアクセスします。
• it1 < it2, it1 <= it2, it1 > it2, it1 >= it2: 2つのイテレータの位置を比較します。

利用例:

std::vector, std::deque, std::string, Cスタイル配列のイテレータ（つまりポインタ）。これらのコンテナは要素がメモリ上で連続しているか、あるいはそれに近い構造を持っているため、ポインタ演算と同様の高速なランダムアクセスが可能です。std::sort, std::binary_search などの多くの高性能なアルゴリズムが要求します。これらのアルゴリズムは、要素を効率的に比較・交換したり、範囲の中央に素早くアクセスしたりする必要があるため、ランダムアクセスの機能が不可欠です。

“`cpp

include

include

include

int main() {
std::vector numbers = {5, 2, 8, 1, 9, 4};

// std::sort は Random Access Iterator を要求
std::sort(numbers.begin(), numbers.end());

std::cout << "ソート後のベクトル: ";
for (int n : numbers) {
    std::cout << n << " ";
}
std::cout << std::endl;

// Random Access Iterator固有の操作
std::vector<int>::iterator it = numbers.begin();
std::cout << "先頭から2番目の要素 (it[1]): " << it[1] << std::endl;
std::cout << "先頭から3要素進んだ位置 (it + 3) が指す要素: " << *(it + 3) << std::endl;

std::vector<int>::iterator it_end = numbers.end();
// end() は最後の要素の次を指す。最後の要素を指すには --end() とする必要があるが、
// 差分計算では end() - begin() で要素数になる。
std::cout << "ベクトルの要素数 (end() - begin()): " << (it_end - numbers.begin()) << std::endl;

return 0;

}
``std::vectorのイテレータはランダムアクセスが可能であり、std::sort` アルゴリズムが必要とする Random Access Iterator の要件を満たします。また、イテレータ間の減算や添え字アクセスといった Random Access Iterator 固有の操作も使用できます。

2.6. イテレータカテゴリの階層構造

イテレータカテゴリは以下の図のような階層構造になっています。矢印は「〜の機能を含む」または「〜として使用できる」関係を示します。

Input Iterator
^
| (機能を持つ)
Forward Iterator <--- Output Iterator
^
| (機能を持つ)
Bidirectional Iterator
^
| (機能を持つ)
Random Access Iterator

これは、Random Access IteratorはBidirectional Iteratorの機能すべてを持ち、Bidirectional IteratorはForward Iteratorの機能すべてを持ち、Forward IteratorはInput/Output Iteratorの機能すべてを持つ、ということを意味します。つまり、より高機能なイテレータは、より低機能なカテゴリが要求される場所でも使用できます。例えば、std::vector のイテレータ（Random Access）は、std::find（Input Iteratorを要求）やstd::reverse（Bidirectional Iteratorを要求）といったアルゴリズムにも渡すことができます。

しかし、逆は真ではありません。std::list のイテレータ（Bidirectional）は、std::sort（Random Access Iteratorを要求）には渡せません。これは、std::sort が要素の任意位置へのアクセスやイテレータ間の距離計算などの Random Access Iterator 特有の操作を内部で使用しているためです。

アルゴリズムのドキュメントを参照する際は、そのアルゴリズムがどのイテレータカテゴリを要求しているかを確認することが重要です。これにより、そのアルゴリズムを適用できるコンテナの種類がわかります。

3. イテレータの役割

イテレータがC++のSTLにおいて果たす主な役割をまとめます。

3.1. コンテナの抽象化

最も重要な役割の一つは、異なる種類のコンテナへのアクセス方法を抽象化することです。std::vector、std::list、std::map は内部構造が全く異なりますが、イテレータを使うことで、これらのコンテナの要素を統一的な方法で走査したり、アクセスしたりできます。イテレータは、コンテナの内部データ構造（連続メモリ、ノード、ハッシュテーブルなど）に関する詳細を隠蔽し、プログラマに要素レベルの抽象的なビューを提供します。

これにより、アルゴリズムやその他の汎用関数は、特定のコンテナ型ではなく、イテレータという抽象的なインターフェースに対して記述することができます。

3.2. アルゴリズムとの連携

STLのアルゴリズムは、特定のイテレータカテゴリを要求するように設計されています。これにより、同じアルゴリズムコードを様々なコンテナ型に適用できます。アルゴリズムはイテレータが提供する操作のみを使用するため、イテレータの背後にあるコンテナの詳細は知る必要がありません。

例えば、std::find アルゴリズムは Input Iterator を要求します。これは、std::find が検索範囲を先頭から終端まで一度だけ順に走査し、要素を読み取るだけで済むためです。したがって、std::find は std::vector, std::list, std::set など、Input Iterator の機能を持つ（またはそれ以上の機能を持つ）イテレータを提供するあらゆるコンテナに対して使用できます。

一方、std::sort アルゴリズムは Random Access Iterator を要求します。これは、ソートアルゴリズム（多くの場合はQuickSortやIntroSortの派生）が要素を効率的に比較、交換、そしてランダムにアクセスする必要があるためです。したがって、std::sort は std::vector, std::deque, std::array (C++11以降), Cスタイル配列といった Random Access Iterator を提供するコンテナにのみ適用できます。std::list や std::set には直接 std::sort を適用できません。std::list にはメンバ関数として sort() が用意されていますが、これはリストの内部構造に適したソートアルゴリズム（通常はMergeSort）を実装しており、Bidirectional Iterator の機能だけで動作します。

3.3. 範囲の指定

begin() と end() イテレータのペアを使用することで、アルゴリズムが操作するコンテナ内の要素の「範囲」を正確に指定できます。この範囲は常に [begin, end) という半開区間として解釈されます。これにより、コンテナ全体だけでなく、その一部に対してもアルゴリズムを適用することが可能です。

例えば、std::vector の最初の5つの要素だけをソートしたい場合、以下のように範囲を指定できます。

“`cpp

include

include

include

int main() {
std::vector numbers = {10, 40, 20, 50, 30, 60, 70};

// 最初の5つの要素だけをソート
std::sort(numbers.begin(), numbers.begin() + 5);

std::cout << "ソート後のベクトル: ";
for (int n : numbers) {
    std::cout << n << " ";
}
std::cout << std::endl;
// 出力例: 10 20 30 40 50 60 70
// (元の {10, 40, 20, 50, 30} がソートされて {10, 20, 30, 40, 50} になる)

return 0;

}
``
ここでは、numbers.begin() + 5` という Random Access Iterator 特有の操作を利用して、範囲の終端を指定しています。

3.4. 特殊なイテレータ

STLは、標準のコンテナイテレータ以外にも、特定の目的に特化した様々な種類のイテレータを提供しています。これらもイテレータカテゴリのいずれかに属し、アルゴリズムと組み合わせて使用されます。

• Insert Iterators (std::back_inserter, std::front_inserter, std::inserter): アルゴリズムの出力先として使用され、デリファレンスと代入（*it = value）の操作が、コンテナへの要素の挿入（push_back, push_front, insert）に翻訳されます。これらは Output Iterator として機能します。
• Stream Iterators (std::istream_iterator, std::ostream_iterator): 標準入出力ストリームとの間でデータの読み書きを行うためのイテレータです。std::istream_iterator は Input Iterator、std::ostream_iterator は Output Iterator として機能します。
• Reverse Iterators (std::reverse_iterator): 通常のイテレータをラップし、++ で前の要素へ、-- で次の要素へ移動するように動作を反転させます。コンテナの rbegin() と rend() メンバ関数によって提供されます。これは、ラップしているイテレータと同じカテゴリの機能（ただし、後退が可能なら Bidirectional/Random Access）を持ち、逆順での走査を容易にします。
• Move Iterators (std::move_iterator): 通常のイテレータをラップし、デリファレンス操作 (*it) が要素の値への参照ではなく、要素の値からの右辺値参照を返すようにします。これにより、アルゴリズムが要素をコピーではなくムーブするようになり、特に大きい要素の処理でパフォーマンスが向上する可能性があります。これは、ラップしているイテレータと同じカテゴリの機能（Forward Iterator以上）を持ちます。

これらの特殊なイテレータは、アルゴリズムと組み合わせて使用することで、様々なタスク（例えば、あるコンテナから別のコンテナへのコピー時に自動的に挿入を行う、ファイルから直接コンテナに読み込むなど）を効率的に、かつ簡潔に記述することを可能にします。

例として、std::back_inserter を使用して、あるベクトルから別のベクトルへ要素をコピーする際に、自動的に push_back を呼び出す方法を示します。

“`cpp

include

include

include

include

int main() {
std::vector source = {1, 2, 3, 4, 5};
std::vector destination;

// std::back_inserter は Output Iterator を返す
// sourceからdestinationへコピー。destinationには要素がpush_backされる。
std::copy(source.begin(), source.end(), std::back_inserter(destination));

std::cout << "コピー先のベクトル: ";
for (int n : destination) {
    std::cout << n << " ";
}
std::cout << std::endl;

return 0;

}
``
ここで、std::back_inserter(destination)は、*it = valueという代入操作がdestination.push_back(value)` となるようなイテレータ（Output Iterator）を作成します。これにより、コピー先のベクトルにあらかじめ要素数分の領域を確保する必要がなくなります。

4. イテレータの無効化 (Iterator Invalidation)

イテレータの非常に重要な側面として、「無効化 (invalidation)」があります。イテレータは特定のコンテナ内の特定の要素を指していますが、コンテナの構造が変化すると、イテレータが指していた位置が無効になることがあります。無効になったイテレータを使用すると、未定義動作（Undefined Behavior）を引き起こし、プログラムのクラッシュや予期しない結果につながる可能性があります。

イテレータが無効になる主な原因は、コンテナの要素の追加や削除、あるいはコンテナの内部構造の変更（例えば、メモリの再割り当て）です。イテレータの無効化ルールはコンテナの種類によって大きく異なります。これは、各コンテナの内部構造と、特定の操作がその構造に与える影響が異なるためです。

主要なコンテナにおけるイテレータの無効化ルールを以下にまとめます。

• std::vector:

  • コンテナの末尾以外への挿入や削除は、その位置以降のすべてのイテレータを無効にします。これは、後続の要素が移動するためです。
  • 末尾への挿入（push_backなど）によってメモリの再割り当てが発生した場合（capacityを超える場合）、すべてのイテレータ（begin() から end() まで全て）が無効になります。
  • 末尾の削除（pop_back）は、end() イテレータのみを無効にします。他のイテレータは有効なままです。
  • erase() メンバ関数は、削除された要素を指すイテレータと、それ以降のすべてのイテレータを無効にしますが、次の有効なイテレータ（削除された要素の次を指すイテレータ）を返します。これにより、ループ内で安全に要素を削除できます。
  • insert() メンバ関数は、挿入位置以降のすべてのイテレータを無効にしますが、挿入された最初の要素を指すイテレータを返します。

• std::deque:

  • コンテナの中央付近への挿入や削除は、全てのイテレータを無効にする可能性があります。
  • 先頭や末尾への挿入や削除は、通常、全てのイテレータを無効にしません（ただし、一部例外や処理系依存の場合あり）。end() イテレータは常に無効になります。
  • erase() および insert() メンバ関数は、std::vector と同様に、無効になった次の有効なイテレータを返します。

• std::list:

  • 要素の挿入や削除は、基本的にその操作に関与したイテレータのみを無効にします。例えば、ある要素を削除した場合、その削除された要素を指していたイテレータのみが無効になります。他の要素を指すイテレータは有効なままです。
  • これは、std::list がリンクリスト構造であり、要素の追加や削除がメモリの移動を伴わないためです。
  • erase() メンバ関数は、削除された要素を指すイテレータを無効にしますが、次の有効なイテレータを返します。ループ内での安全な削除が可能です。

• std::forward_list:

  • std::list と同様に、要素の挿入や削除は、操作に関与したイテレータのみを無効にする傾向がありますが、単方向であるため、erase_after() は削除された要素の「次」を指すイテレータを返します（これは std::list とは少し異なります）。

• std::set, std::map, std::multiset, std::multimap (連想コンテナ):

  • 要素の挿入は、既存のイテレータを無効にしません。
  • 要素の削除は、削除された要素を指すイテレータのみを無効にします。他の要素を指すイテレータは有効なままです。
  • erase() メンバ関数は、削除された要素を指すイテレータを無効にしますが、C++11以降では、次の有効なイテレータを返します。これにより、ループ内での安全な削除が可能です。

安全なイテレータの扱い:

イテレータの無効化を避けるためには、以下の点に注意が必要です。

• コンテナを変更する操作（挿入、削除）を行った後、古いイテレータを使い続けない。
• ループ内で要素の削除や挿入を行う場合は、コンテナの erase() や insert() メンバ関数が返す新しいイテレータを使用する。
• 範囲ベースforループは、ループ中にコンテナの構造を変更する操作（要素の追加や削除）を行うと未定義動作を引き起こす可能性があるため、要素の追加・削除が必要な場合は明示的なイテレータベースのループを使用する。

例：std::vector から特定の条件を満たす要素を削除する安全な方法

“`cpp

include

include

int main() {
std::vector numbers = {10, 20, 30, 40, 50, 60, 70};

auto it = numbers.begin();
while (it != numbers.end()) {
    // 30より大きい要素を削除する例
    if (*it > 30) {
        // erase() は削除された要素を指すイテレータを無効にするが、
        // 次の要素を指す有効なイテレータを返す
        it = numbers.erase(it);
        // erase後、itは次の要素を指しているため、++itは不要
    } else {
        // 要素を削除しなかった場合は、通常通り次の要素に進む
        ++it;
    }
}

std::cout << "削除後のベクトル: ";
for (int n : numbers) {
    std::cout << n << " ";
}
std::cout << std::endl;

return 0;

}
``
このコードでは、erase()が返した新しいイテレータをit` に再代入することで、ループの中で安全に要素を削除しつつ、適切に次の要素に進むことができています。

5. イテレータとポインタ

イテレータは「ポインタのような」オブジェクトであるとよく説明されますが、両者には重要な違いがあります。

• ポインタ: メモリ上の特定のアドレスを直接指します。ポインタ演算（p++, p + nなど）は、基本的にアドレス値の増減を意味し、指す型に応じたバイト数だけアドレスが進みます。ポインタは生メモリへの低レベルなアクセス手段です。配列のような連続したメモリ領域に対しては非常に効率的ですが、リンクリストのような非連続な構造には適しません。
• イテレータ: コンテナ内の要素の論理的な「位置」を抽象的に指します。++ 演算子などの移動操作は、コンテナの内部構造に応じて適切に実装されています。例えば、std::vector のイテレータの ++ は内部的にはポインタのインクリメントと似ていますが、std::list のイテレータの ++ はリストの次のノードへのポインタを辿る操作になります。イテレータはコンテナの内部構造の詳細を隠蔽します。

すべてのポインタは Random Access Iterator の要件を満たします。そのため、Cスタイルの配列や std::vector の基盤ポインタを、Random Access Iterator を要求するアルゴリズムに渡すことができます。しかし、すべてのイテレータがポインタのように振る舞うわけではありません。特に、Bidirectional Iterator 以下はランダムアクセス操作をサポートしません。

ポインタはコンテナの管理外のメモリを指すこともあり得ますが、コンテナのイテレータは通常、そのコンテナが管理する有効な要素またはその終端の「次」の位置のみを指します。また、ポインタにはイテレータのような「無効化」という概念は厳密にはありませんが、指しているメモリが解放されたり、再配置されたりすれば、そのポインタを使用することはやはり未定義動作となります。コンテナのイテレータの無効化ルールは、コンテナが内部でメモリをどのように管理しているかを反映したものです。

6. イテレータの使用例：アルゴリズムとの連携

イテレータの力を最も実感できるのは、STLアルゴリズムとの組み合わせです。ここではいくつかの例を示します。

例1: 特定の要素を検索する (std::find)

std::find は、指定された範囲内で特定の要素を検索するアルゴリズムです。Input Iterator を要求します。

“`cpp

include

include

include

include

int main() {
std::vector v = {10, 20, 30, 40, 50};
std::list l = {100, 200, 300, 400, 500};

// vectorで30を検索
auto it_v = std::find(v.begin(), v.end(), 30);
if (it_v != v.end()) {
    std::cout << "vectorで30が見つかりました: " << *it_v << std::endl;
    // 見つかった要素のインデックスを知るには Random Access Iterator の機能が必要
    std::cout << "位置: " << std::distance(v.begin(), it_v) << std::endl;
} else {
    std::cout << "vectorで30は見つかりませんでした" << std::endl;
}

// listで300を検索
auto it_l = std::find(l.begin(), l.end(), 300);
if (it_l != l.end()) {
    std::cout << "listで300が見つかりました: " << *it_l << std::endl;
    // listのイテレータは Random Access ではないので、distance() は線形時間に
    std::cout << "位置までの距離: " << std::distance(l.begin(), it_l) << std::endl;
} else {
    std::cout << "listで300は見つかりませんでした" << std::endl;
}

return 0;

}
``std::findは Input Iterator だけを要求するため、std::vector(Random Access) とstd::list(Bidirectional) の両方で使用できます。検索に成功すると、その要素を指すイテレータを返します。失敗した場合は、範囲の終端イテレータ（end()）を返します。std::distance` は、2つのイテレータ間の要素数を計算しますが、Random Access Iterator 以外の場合はイテレータを順番に進めるため、線形時間（O(N)）かかります。

例2: 要素の並べ替え (std::sort)

std::sort は、指定された範囲の要素を並べ替えるアルゴリズムです。Random Access Iterator を要求します。

“`cpp

include

include

include

include

int main() {
std::vector v = {5, 2, 8, 1, 9, 4};
std::deque d = {50, 20, 80, 10, 90, 40};

// vectorをソート
std::sort(v.begin(), v.end());
std::cout << "ソート後のvector: ";
for (int n : v) {
    std::cout << n << " ";
}
std::cout << std::endl;

// dequeをソート
std::sort(d.begin(), d.end());
std::cout << "ソート後のdeque: ";
for (int n : d) {
    std::cout << n << " ";
}
std::cout << std::endl;

// std::list l = {500, 200, 800};
// std::sort(l.begin(), l.end()); // コンパイルエラー: listのイテレータはRandom Accessではない
// listのソートはメンバ関数を使用: l.sort();

return 0;

}
``std::vectorとstd::dequeは Random Access Iterator を提供するためstd::sortが使用できますが、std::list` は Random Access Iterator を提供しないため使用できません。

例3: 要素のコピー (std::copy)

std::copy は、ある範囲から別の範囲へ要素をコピーするアルゴリズムです。入力範囲には Input Iterator、出力範囲には Output Iterator を要求します。

“`cpp

include

include

include

include // back_inserter に必要

include

int main() {
std::vector source_v = {1, 2, 3, 4, 5};
std::list destination_l;

// vectorからlistへコピー
std::copy(source_v.begin(), source_v.end(), std::back_inserter(destination_l));

std::cout << "vectorからlistへコピー: ";
for (int n : destination_l) {
    std::cout << n << " ";
}
std::cout << std::endl;

std::list<int> source_l = {10, 20, 30};
std::vector<int> destination_v(source_l.size()); // 出力先は事前にサイズが必要（back_inserterを使わない場合）

// listからvectorへコピー (通常のイテレータ使用)
std::copy(source_l.begin(), source_l.end(), destination_v.begin());

std::cout << "listからvectorへコピー: ";
for (int n : destination_v) {
    std::cout << n << " ";
}
std::cout << std::endl;

return 0;

}
``std::copyは Input Iterator と Output Iterator という最も基本的なカテゴリを要求するため、ほとんどのコンテナ間で要素のコピーに使用できます。出力先イテレータとしてstd::back_inserterを使うと、コピー元から読み取った要素が出力先コンテナにpush_back` されます。通常のイテレータを出力先として使う場合は、出力先のコンテナに十分な容量があるか、または要素が既に存在している必要があります。

これらの例からわかるように、イテレータはコンテナの具体的な型を意識することなく、様々なアルゴリズムを適用するための共通のインターフェースを提供しています。

7. まとめ

C++のイテレータは、STLにおけるコンテナとアルゴリズムの連携を可能にする、非常に強力で柔軟なメカニズムです。

• イテレータはコンテナの内部構造を抽象化し、要素への統一的なアクセス方法を提供します。
• 機能レベルに応じて Input, Output, Forward, Bidirectional, Random Access の5つのカテゴリがあり、それぞれサポートする操作とセマンティクスが異なります。
• アルゴリズムは特定のイテレータカテゴリを要求することで、適用可能なコンテナの種類を限定しつつ、コンテナ型に依存しない汎用的なコードを実現します。
• イテレータは [begin, end) という半開区間を用いて、アルゴリズムが操作する範囲を指定します。
• 特殊なイテレータ（インサートイテレータ、ストリームイテレータ、リバースイテレータなど）は、特定の目的のためにイテレータの動作をカスタマイズします。
• コンテナの要素の追加や削除、メモリ再配置などによってイテレータは無効になる可能性があり、そのルールはコンテナによって異なります。無効化されたイテレータの使用は未定義動作です。
• イテレータはポインタと似ていますが、コンテナの内部構造を抽象化し、コンテナのルールに則った振る舞いをします。

C++プログラミング、特にSTLを効果的に利用するためには、これらのイテレータの基本、種類、そして役割をしっかりと理解することが不可欠です。イテレータを使いこなせるようになれば、より柔軟で効率的なデータ処理が可能となり、C++の強力なライブラリ群を最大限に活用できるようになるでしょう。イテレータの概念は最初は少し難しく感じるかもしれませんが、様々なコンテナやアルゴリズムと共に実際に使用していく中で、その設計思想と利便性が理解できるようになるはずです。ぜひ、積極的にコードを書いてイテレータに慣れ親しんでください。

---