1. 導入：なぜイテレータの種類を知る必要があるのか？
C++でプログラムを書いていると、コンテナ内の要素数を数えたり、インデックス間の距離を求めたりするために「std::distance」をよく使います。しかし、この関数が「どのように距離を計算しているか」を意識したことはありますか？実は、適当に使っていると、本来一瞬で終わるはずの処理に時間がかかってしまうことがあります。この記事では、イテレータカテゴリという概念を理解し、計算量を最適化する方法を解説します。
2. 基礎知識：イテレータカテゴリとは？
C++のコンテナには、それぞれのデータ構造に適した「イテレータ」が用意されています。例えば、配列のようにメモリが連続している「std::vector」と、要素がバラバラに繋がっている「std::list」では、移動の仕方が異なります。
この能力の差を「イテレータカテゴリ」と呼びます。
・RandomAccessIterator（ランダムアクセス）: どの場所にも直接ジャンプできる（std::vectorなど）。
・ForwardIterator（前方イテレータ）: 1つずつ順番に進むことしかできない（std::listなど）。
std::distanceは、渡されたイテレータが「直接ジャンプできるか」を自動的に判別し、最適な計算方法を選択します。これを「タグディスパッチ」と呼びます。
3. 実装：計算量の違いを知る
std::distanceは、内部で以下のように動作を切り替えています。
・ランダムアクセス可能な場合：ポインタ同士を引き算するだけ（O(1)、つまり定数時間で完了）。
・それ以外の場合：ループで1つずつ進めてカウントする（O(N)、要素数に比例して時間がかかる）。
もし、std::listのような「進むしかない」コンテナに対して大量の要素数計算を繰り返すと、プログラム全体が低速化する原因になります。
4. サンプルプログラム
以下のコードで、コンテナの種類による挙動の違いを確認してみましょう。
include <iostream>
include <vector>
include <list>
include <iterator>
int main() {
// 1. std::vector (ランダムアクセス可能: O(1)で高速)
std::vector<int> vec = {1, 2, 3, 4, 5};
auto dist_vec = std::distance(vec.begin(), vec.end());
std::cout << "ベクトルの距離: " << dist_vec << std::endl;
// 2. std::list (逐次移動が必要: O(N)で計算)
std::list<int> lst = {1, 2, 3, 4, 5};
auto dist_lst = std::distance(lst.begin(), lst.end());
std::cout << "リストの距離: " << dist_lst << std::endl;
return 0;
}
5. 応用・注意点：自作コンテナを作る時
もしあなたが自分でコンテナクラスを設計する場合、非常に重要な注意点があります。イテレータクラス内に「iterator_category」という型エイリアスを正しく定義しないと、C++の標準ライブラリはあなたのコンテナを「最も低速なイテレータ」と見なしてしまいます。
また、C++20からは「Concepts」が導入され、より直感的にイテレータの能力を制限・判定できるようになりました。現場でパフォーマンスを追求する際は、計算量（O記法）を意識し、自分の書いたアルゴリズムがどのイテレータカテゴリに依存しているのかを常に把握するようにしましょう。これこそが、C++中級者への第一歩です。
コメント