はじめに

仕組みの理解に重点をおいているため、説明が長くなりがちなのを予めご容赦ください。
記事の内容は執筆時点での最新バージョン（rustc 1.79.0）に基づいています。古いバージョン（特に1.53.0以前）ではライブラリの実装が一部異なります。
情報源は主に公式ライブラリリファレンスとChatGPTの回答です。
実用的なイテレータの実装例は別記事を参照してください。

Iterator（イテレータ）とは？

Iteratorはデータの集合（配列、ベクタ、リストなど）に対して順次アクセスするための仕組みです。RustにおけるIteratorとは、Iteratorトレイトを実装しているデータ型に他なりません。
例えば、0..10のようなRange型はIteratorトレイトを実装しているのでfor文で順次アクセスができます。（正確にはfor文が受け取るのはIntoIteratorなのですが詳細は後ほど）

// 0から9までの数字を表示
for i in 0..10 {
    println!("{i}")
}

以降、"Iteratorトレイト"と"Iteratorトレイトを実装したデータ型"のことを単に"Iterator"と呼称します。どちらを指しているかは文脈で判断してください。

Iterator トレイト

Iteratorの理解を深めるにはライブラリリファレンスから実際の定義を見るのが良いでしょう。
Iteratorは以下のように定義されています。

Iterator

pub trait Iterator {
    type Item;

    // Required method
    fn next(&mut self) -> Option<Self::Item>;

    // Provided methods
    // 中略
}

"Required methods"はトレイトを実装する上でユーザーが実装を与えなければならないメソッドで、"Provided methods"はデフォルトの実装が与えられているメソッドです。

next()は要素が残っていればSome(T)を返し、要素をすべて消費しきったらNoneを返すメソッドです。
for文は内部的にはこのnext()をNoneが返ってくるまで何度も呼び出すことでループを実現しているわけです。

"Provided methods"は多すぎるので中略しましたが、リンク先を見てもらえば分かる通り、map()やfold()、find()などの他言語でもよく見かける便利なメソッドが多数定義されています。

つまり、next()さえ実装してしまえば、for文とこれらのメソッドが自動的に使えるようになるということです。
試しに、はじめに紹介したRange型を自前で簡易実装して使ってみましょう。

struct MyRange {
    i: i32,
    n: i32,
}

impl Iterator for MyRange {
    type Item = i32;
    fn next(&mut self) -> Option<Self::Item> {
        if self.i != self.n {
            let i = self.i;
            self.i += 1;
            Some(i) // 要素が残っていればSome(i)を返す
        } else {
            None // 終端に達したのでNoneを返す
        }
    }
}

fn main() {
    // Iteratorはfor文で使える
    let r0 = MyRange { i: 0, n: 10 };
    for i in r0 {
        println!("{i}")
    }

    // for文を使わずにnextを明示的に呼んでみる
    let mut r1 = MyRange { i: 0, n: 10 };
    while let Some(i) = r1.next() {
        println!("{i}")
    }

    // provided methodsを使ってみる
    let r2 = MyRange { i: 0, n: 10 };
    let n: i32 = r2.map(|i| i.pow(2)).sum(); // 二乗和を計算
    println!("{n}")
}

一番下の例でmap()の戻り値に対してさらっとsum()を呼び出していますが、これが可能なのはmap()もまたMapというIteratorを返却するからです。リンク先の左側のフレームのメニューから"Trait Implementations"にIteratorが存在することを確認できるかと思います。

FromIterator トレイト

データ型に対してFromIteratorトレイトが実装されていればfrom_iter()にIteratorを渡すことで、その型を生成することができます。

例えば、VecはFromIteratorを実装しているので以下のように書けます。

let v = Vec::from_iter(0..5); // vec![0, 1, 2, 3, 4]と等価

ジェネリックなメソッドの内部などの変換対象の型を特定できない文脈においては、以下のようにFromIterator::from_iter()を直接呼び出す方法が有効です。

let v: Vec<_> = FromIterator::from_iter(0..5);

しかし、普段使いではfrom_iter()よりもIterator側からcollect()を呼ぶことのほうが多いでしょう。

let v: Vec<_> = (0..5).collect();

または

let v = (0..5).collect::<Vec<_>>();

collect()は実装（リンク先の右上のsourceをクリック）を見ても分かるとおり、結局は内部でFromIterator::from_iter()を呼び出しています。

IntoIterator トレイト

IntoIteratorトレイトは主にfor文がIteratorを取得するために使用するトレイトです。
例えば、以下のようにfor文に&Vecを渡すとIntoIterator::into_iter()を呼び出して、返ってきたIteratorを使用してループ処理を行います。

let v: Vec<i32> = vec![0, 1, 2, 3, 4];
for i in &v {
    println!("{i}")
}

よくある間違いなのですが、VecやMapなどのコレクション型は一般的にIteratorそのものではありません。
実際にVecはIteratorを実装しておらず、代わりにVec、&Vec、&mut VecそれぞれについてIntoIteratorを実装しています。

IntoIteratorが実際にどのような型に対して実装されているかはライブラリリファレンスのIntoIteratorの"Implementors"から確認できます。

最初にIteratorはfor文に渡せることを説明しましたが、これが可能なのはすべてのIteratorを実装する型に対して自動的にIntoIteratorを実装する宣言（ブランケット実装）が標準ライブラリ内に存在するためです。

impl<I: Iterator> IntoIterator for I {
    // 中略
    fn into_iter(self) -> I {
        self
    }
}

見ての通り、Iteratorはinto_iter()が呼び出されると自分自身（つまりIterator）をそのまま返します。
なので、for文は渡された型が何であれ、とにかくinto_iter()を呼び出せばIteratorを取得できるわけです。

for文以外でもIntoIteratorを使うと便利な場合があります。
例えば、ジェネリックメソッドでIteratorを受け取りたい場合であっても、IntoIteratorで受け取ることにより、配列やコレクション型なども受け入れることができます。
地味ですが呼び出し側でiter()やiter_mut()を呼ぶ必要がなくなるのでコードが少しだけスッキリします。

use std::fmt::Display;

fn print_all<T>(it: T)
where
    T: IntoIterator, // ここをIteratorにすると下3つのprint_allはエラーになる
    T::Item: Display,
{
    for i in it {
        println!("{i}")
    }
}

fn main() {
    // 実はfrom_iterもIntoIteratorを受け取るので配列を直接渡せる
    let mut v = Vec::from_iter([0, 1, 2, 3, 4]);

    // IteratorもIntoIterator
    print_all(v.iter());

    // &Vec, &mut Vec, Vecに対してそれぞれIntoIteratorが定義されいている
    print_all(&v); // &Vec
    print_all(&mut v); // &mut Vec
    print_all(v); // Vec (vはmoveされることに注意)
}

Iteratorトレイトの派生

Iteratorの基本的な動作は、next()が呼び出されたときに要素が残っていれば前から順にSome(T)を返し、終端に達したらNoneを返すというものでした。
大抵はこれで十分なのですが、追加の機能があれば一部の処理を効率よく実行できる場合があります。
以下の3つのトレイトはIteratorに対して追加の機能を実装するためのものです。もちろん、これらのトレイトを実装するために前提として、Iteratorトレイトを実装している必要があります。

DoubleEndedIterator トレイト

Iterator::next()が前からなのに対して、DoubleEndedIterator::next_back()を実装することで後ろからの要素アクセスを可能にします。

ExactSizeIterator トレイト

残りの正確な要素数がわかる場合に実装するトレイトです。ExactSizeIterator::len()はIterator::size_hint()を参照するデフォルト実装が与えられているのでsize_hint()が正確な要素数を返すように実装します。サイズ情報はfrom_iter()でコレクション型を生成する時に、予め十分なヒープ領域を確保したい場合などに有用です。

FusedIterator トレイト

next()がNoneを返してきた後、再びnext()を呼んでもNoneが返ってくることを保証するトレイトです。FusedIteratorが実装されていない場合、実装方法によっては最初の要素に戻るかもしれないし、panicを起こしてプログラムが停止するかもしれません。

実装例

上で作成したMyRangeに更にこの3つのトレイトを実装してみましょう。

struct MyRange {
    i: i32,
    n: i32,
}

impl Iterator for MyRange {
    type Item = i32;
    fn next(&mut self) -> Option<Self::Item> {
        if self.i < self.n {
            let i = self.i;
            self.i += 1;
            Some(i)
        } else {
            None
        }
    }

    // ExactSizeIterator用
    fn size_hint(&self) -> (usize, Option<usize>) {
        // 左は残り要素の最小値、右は残り要素の最大値
        // ExactSizeIteratorを実装する場合 右辺 == 左辺 となる
        let len = (self.n - self.i).abs() as usize;
        (len, Some(len))
    }
}

impl DoubleEndedIterator for MyRange {
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.i < self.n {
            self.n -= 1;
            Some(self.n) // 後ろ側(n)をデクリメントして返却
        } else {
            None
        }
    }
}

impl ExactSizeIterator for MyRange {
    // Iterator::size_hint()が正しく実装されていることを確認
}

impl std::iter::FusedIterator for MyRange {
    // 特に実装は必要ないが、Iterator::next()とDoubleEndedIterator::next_back()が
    // 要素をすべて消費しきった後、何度呼び出しても必ずNoneを返す実装になっていることを確認
}

fn main() {
    let mut r = MyRange { i: 0, n: 5 };

    // ExactSizeIteratorのチェック
    assert_eq!(r.len(), 5);

    // DoubleEndedIteratorを実装しているのでrev()が使える
    for i in (&mut r).rev() { // r.rev()だとrがmoveされることに注意（後のassert!で使えない）
        println!("{i}");
    }

    // ExactSizeIteratorのチェック
    assert_eq!(r.len(), 0);
    // FusedIteratorのチェック
    assert_eq!(r.next(), None);
    assert_eq!(r.next_back(), None);
}

実用的なCollectionとIteratorの実装

今回はトレイトの解説がメインのため、実装がIteratorそのものだけで完結するRangeを例に取り上げましたが、本来のIteratorはコレクション型の要素を順次参照するためのものです。
より実用的なコレクション型とそのIteratorの実装の外観は次のようなになります。

// コレクション型
struct A {
    buf: Vec<i32>,
}

impl A {
    pub fn iter(&self) -> Iter<'_> {
        Iter::new(self)
    }
    pub fn iter_mut(&mut self) -> IterMut<'_> {
        IterMut::new(self)
    }
}

impl FromIterator for A {
}

impl IntoIterator for A {
    // into_iterは IntoIter を返す
}
impl<'a> IntoIterator for &'a A {
    // into_iterは Iter を返す (iter()と等価)
}
impl<'a> IntoIterator for &'a mut A {
    // into_iterは IterMut を返す (iter_mut()と等価)
}

// A用のIterator
// A自体を内部にmoveするためライフタイム注釈は不要
struct IntoIter {
    target: A,
    index: usize,
}
impl Iterator for IntoIter {
}

// &A用のIterator
// 内部にAへの参照を持つためライフタイム注釈が必要
struct Iter<'a> {
    target: &'a A,
    index: usize,
}
impl<'a> Iterator for Iter<'a> {
}

// &mut A用のIterator
// 内部にAへの可変参照を持つためライフタイム注釈が必要
struct IterMut<'a> {
    target: &mut 'a A,
    index: usize,
}
impl<'a> Iterator for IterMut<'a> {
}

A, &A, &mut Aそれぞれに対してIterator用の型(IntoIter, Iter, IterMut)を定義してIteratorトレイトを実装して、さらにはIntoIteratorの実装も必要になります。
A以外のimplの中身はすべて省略していますが、それでも見た瞬間わかるほど実装が面倒です。
しかし、実際のVecはすべてのIteratorを真面目に実装しているわけではなく、IterとIterMutについてはDerefとDerefMutを通じてスライスの実装を流用しています。

これに習って、Iteratorを実装したい場合であっても、直接実装しようとする前に何かしらの流用ができないかを検討してみましょう。

iter(), iter_mut()のみを流用

struct A {
    buf: Vec<i32>,
}

impl A {
    fn iter(&self) -> std::slice::Iter<'_, i32> {
        self.buf.iter()
    }

    fn iter_mut(&mut self) -> std::slice::IterMut<'_, i32> {
        self.buf.iter_mut()
    }
}

Vecを丸ごと流用

struct A {
    buf: Vec<i32>,
}

impl std::ops::Deref for A {
    type Target = Vec<i32>;
    fn deref(&self) -> &Vec<i32> {
        &self.buf
    }
}

impl std::ops::DerefMut for A {
    fn deref_mut(&mut self) -> &mut Vec<i32> {
        &mut self.buf
    }
}

動作テスト用main

fn main() {
    let mut a = A {
        buf: (0..10).collect(),
    };

    for i in a.iter_mut() {
        *i *= 2;
    }

    for i in a.iter() {
        println!("{i}");
    }
}

まとめ

RustのIterator周りは3つのトレイトで構成されていることを説明しました。

Iterator : Iterator本体に実装するトレイト
FromIterator : Iteratorから生成したい型に対して実装するトレイト
IntoIterator : Iteratroを生成したい型に対して実装するトレイト

Iteratorのみで不十分な場合は、以下のトレイトを追加で実装することを考えましょう

DoubleEndedIterator : 後ろから要素を取得したい場合
ExactSizeIterator : 残りの要素数が正確に分かっていてメモリ確保を効率的にしたい場合
FusedIterator : 要素を消費しきった後、必ずNoneを返し続けてほしい場合

そもそもIteratorの実装は割と面倒なので流用できないか検討しましょう。