Day 017 — カスタムイテレータの実装

📚 背景知識（読んでから問題へ）

Day 016で見た通り、Iteratorトレイトが要求するメソッドは実質next()ただ1つです。裏を返せば、自分の定義した型にnext()さえ実装すれば、map・filter・take・sum・collectなど標準ライブラリが持つ数十のメソッド群がすべてタダで手に入るということです。今日はこの「タダで手に入る」側ではなく、next()を自分で書く側に立ちます。

📋 コピーpub trait Iterator {
    type Item;                              // このイテレータが生成する値の型
    fn next(&mut self) -> Option<Self::Item>;  // 実装必須なのはこれだけ
}

type Itemは関連型（associated type）です。ジェネリクス（Iterator<T>のような型パラメータ）ではなく関連型が選ばれているのは、「1つの型に対してイテレータの要素型は1種類に定まるべき」という設計判断によるものです。Vec<i32>に対するIterator実装がItem = i32とItem = Stringの2通り存在する、という曖昧さをそもそも型システムのレベルで排除しています。

カスタムイテレータを自作する場面は主に2つに分かれます。

1. 無限または遅延生成の系列を表す型（例: フィボナッチ数列・カウントダウン・乱数ストリーム）。要素をあらかじめVecに確保できない（そもそも無限に続く）ため、next()が呼ばれるたびにその場で次の値を計算する
2. 既存のコレクションを独自の視点で走査する型（例: 重なり合うウィンドウ・ページ単位の分割・木構造の深さ優先走査）。データはすでに存在するが、走査の順序やまとめ方を自分で定義したい

また、for x in collectionという構文を自作の型にも対応させるにはIntoIteratorトレイトの実装が必要です。IntoIteratorは「この型からイテレータへの変換方法」を定義するトレイトで、Iteratorとは別物です。多くの型はself（所有権を消費）・&self（借用）・&mut self（可変借用）の3パターンそれぞれに対してIntoIteratorを実装し分けることで、for x in collection（消費）・for x in &collection（借用）・for x in &mut collection（可変借用）のすべてに対応します。

📝 問題

以下の4つの要求に順番に答えてください。

要求1（実装: 無限イテレータ — Fibonacci）

Fibonacci { curr: u64, next: u64 }という構造体を定義し、Iteratorトレイトを実装してフィボナッチ数列（0, 1, 1, 2, 3, 5, 8, ...）を無限に生成するイテレータにしてください。Fibonacci::new()で初期状態（curr: 0, next: 1）を作るコンストラクタも用意してください。

要求2（実装: 借用ベースのイテレータ — SlidingWindow）

&'a [T]（ライフタイム'aを持つスライス）を保持するSlidingWindow<'a, T>という構造体を定義し、Iteratorトレイトを実装して指定サイズの重なり合うウィンドウ（Item = &'a [T]）を順に返すイテレータにしてください。標準ライブラリのslice::windows()と同じ動作を、自分でゼロから実装するのが目的です。

例: [1, 2, 3, 4, 5]にサイズ3のウィンドウを適用すると[1,2,3] → [2,3,4] → [3,4,5]の順に返し、それ以上はNoneを返す。

要求3（実装: IntoIterator — 所有権パターン別の3実装）

Inventory { items: Vec<String> }という構造体に対して、次の3パターンのIntoIteratorを実装してください。

• for item in inventory（Stringを所有権ごと取り出す）
• for item in &inventory（&Stringを借用で取り出す）
• for item in &mut inventory（&mut Stringを可変借用で取り出す）

いずれも自前でnext()を書く必要はなく、内部でVecが既に持つイテレータ（into_iter/iter/iter_mut）へ委譲してください。

要求4（実装: カスタムイテレータへのアダプタ適用の実証）

要求1のFibonacciに対して、自分で実装したのはnext()だけなのにfilter・take・collectが問題なく連鎖できることを示すテストを書いてください。具体的には、フィボナッチ数列のうち偶数のものを先頭から5個取り出す処理（Fibonacci::new().filter(...).take(5).collect()）が[0, 2, 8, 34, 144]になることを検証してください。

🔍 ヒント（段階的開示）

📋 コピーstruct Fibonacci {
    curr: u64,
    next: u64,
}

impl Fibonacci {
    fn new() -> Self {
        Fibonacci { curr: 0, next: 1 }
    }
}

impl Iterator for Fibonacci {
    type Item = u64;
    fn next(&mut self) -> Option<Self::Item> {
        let value = self.curr;
        let new_next = self.curr + self.next;
        self.curr = self.next;
        self.next = new_next;
        Some(value)
    }
}

struct SlidingWindow<'a, T> {
    slice: &'a [T],
    size: usize,
    pos: usize,
}

impl<'a, T> Iterator for SlidingWindow<'a, T> {
    type Item = &'a [T];
    fn next(&mut self) -> Option<Self::Item> {
        if self.pos + self.size > self.slice.len() {
            return None;
        }
        let window = &self.slice[self.pos..self.pos + self.size];
        self.pos += 1;
        Some(window)
    }
}

struct Inventory {
    items: Vec<String>,
}

impl IntoIterator for Inventory {
    type Item = String;
    type IntoIter = std::vec::IntoIter<String>;
    fn into_iter(self) -> Self::IntoIter {
        self.items.into_iter()
    }
}

impl<'a> IntoIterator for &'a Inventory {
    type Item = &'a String;
    type IntoIter = std::slice::Iter<'a, String>;
    fn into_iter(self) -> Self::IntoIter {
        self.items.iter()
    }
}

impl<'a> IntoIterator for &'a mut Inventory {
    type Item = &'a mut String;
    type IntoIter = std::slice::IterMut<'a, String>;
    fn into_iter(self) -> Self::IntoIter {
        self.items.iter_mut()
    }
}

✅ 模範解答

📋 コピー// 要求1: 無限イテレータ Fibonacci
struct Fibonacci {
    curr: u64,
    next: u64,
}

impl Fibonacci {
    fn new() -> Self {
        Fibonacci { curr: 0, next: 1 }
    }
}

impl Iterator for Fibonacci {
    type Item = u64;

    fn next(&mut self) -> Option<Self::Item> {
        let value = self.curr;
        let new_next = self.curr + self.next;
        self.curr = self.next;
        self.next = new_next;
        Some(value)
    }
}

// 要求2: 借用ベースの SlidingWindow
struct SlidingWindow<'a, T> {
    slice: &'a [T],
    size: usize,
    pos: usize,
}

impl<'a, T> SlidingWindow<'a, T> {
    fn new(slice: &'a [T], size: usize) -> Self {
        SlidingWindow { slice, size, pos: 0 }
    }
}

impl<'a, T> Iterator for SlidingWindow<'a, T> {
    type Item = &'a [T];

    fn next(&mut self) -> Option<Self::Item> {
        if self.size == 0 || self.pos + self.size > self.slice.len() {
            return None;
        }
        let window = &self.slice[self.pos..self.pos + self.size];
        self.pos += 1;
        Some(window)
    }
}

// 要求3: IntoIterator の3パターン
struct Inventory {
    items: Vec<String>,
}

impl IntoIterator for Inventory {
    type Item = String;
    type IntoIter = std::vec::IntoIter<String>;

    fn into_iter(self) -> Self::IntoIter {
        self.items.into_iter()
    }
}

impl<'a> IntoIterator for &'a Inventory {
    type Item = &'a String;
    type IntoIter = std::slice::Iter<'a, String>;

    fn into_iter(self) -> Self::IntoIter {
        self.items.iter()
    }
}

impl<'a> IntoIterator for &'a mut Inventory {
    type Item = &'a mut String;
    type IntoIter = std::slice::IterMut<'a, String>;

    fn into_iter(self) -> Self::IntoIter {
        self.items.iter_mut()
    }
}

fn main() {
    // 要求1の実行例: 無限イテレータを take で有限化してから消費する
    let first_ten: Vec<u64> = Fibonacci::new().take(10).collect();
    println!("first_ten = {:?}", first_ten);

    // 要求2の実行例
    let data = [1, 2, 3, 4, 5];
    let windows: Vec<&[i32]> = SlidingWindow::new(&data, 3).collect();
    println!("windows = {:?}", windows);

    // 要求3の実行例: 3パターンすべての for ループ
    let mut inventory = Inventory {
        items: vec!["pen".to_string(), "notebook".to_string(), "eraser".to_string()],
    };

    for item in &inventory {
        println!("borrowed: {}", item);
    }

    for item in &mut inventory {
        item.push_str("!");
    }
    println!("after mutation: {:?}", inventory.items);

    for item in inventory {
        // ここで inventory の所有権が消費される（以降 inventory は使えない）
        println!("owned: {}", item);
    }

    // 要求4の実行例
    let even_fibs: Vec<u64> = Fibonacci::new().filter(|x| x % 2 == 0).take(5).collect();
    println!("even_fibs = {:?}", even_fibs);
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn fibonacci_generates_correct_sequence() {
        let first_ten: Vec<u64> = Fibonacci::new().take(10).collect();
        assert_eq!(first_ten, vec![0, 1, 1, 2, 3, 5, 8, 13, 21, 34]);
    }

    #[test]
    fn sliding_window_produces_overlapping_windows() {
        let data = [1, 2, 3, 4, 5];
        let windows: Vec<&[i32]> = SlidingWindow::new(&data, 3).collect();
        assert_eq!(windows, vec![&[1, 2, 3][..], &[2, 3, 4][..], &[3, 4, 5][..]]);
    }

    #[test]
    fn sliding_window_returns_none_when_slice_shorter_than_size() {
        let data = [1, 2];
        let mut window_iter = SlidingWindow::new(&data, 3);
        assert_eq!(window_iter.next(), None);
    }

    #[test]
    fn inventory_into_iterator_by_value_moves_ownership() {
        let inventory = Inventory {
            items: vec!["a".to_string(), "b".to_string()],
        };
        let collected: Vec<String> = inventory.into_iter().collect();
        assert_eq!(collected, vec!["a".to_string(), "b".to_string()]);
    }

    #[test]
    fn inventory_into_iterator_by_ref_borrows() {
        let inventory = Inventory {
            items: vec!["a".to_string(), "b".to_string()],
        };
        let borrowed: Vec<&String> = (&inventory).into_iter().collect();
        assert_eq!(borrowed, vec!["a", "b"]);
        // inventory はここでもまだ使える（借用しただけなので）
        assert_eq!(inventory.items.len(), 2);
    }

    #[test]
    fn inventory_into_iterator_by_mut_ref_allows_mutation() {
        let mut inventory = Inventory {
            items: vec!["a".to_string(), "b".to_string()],
        };
        for item in &mut inventory {
            item.push_str("!");
        }
        assert_eq!(inventory.items, vec!["a!".to_string(), "b!".to_string()]);
    }

    // 要求4: 自作イテレータへのアダプタ適用の実証
    #[test]
    fn custom_iterator_gets_adapters_for_free() {
        let even_fibs: Vec<u64> = Fibonacci::new().filter(|x| x % 2 == 0).take(5).collect();
        assert_eq!(even_fibs, vec![0, 2, 8, 34, 144]);
    }
}

$ cargo run
first_ten = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
windows = [[1, 2, 3], [2, 3, 4], [3, 4, 5]]
borrowed: pen
borrowed: notebook
borrowed: eraser
after mutation: ["pen!", "notebook!", "eraser!"]
owned: pen!
owned: notebook!
owned: eraser!
even_fibs = [0, 2, 8, 34, 144]

$ cargo test
running 6 tests
test tests::custom_iterator_gets_adapters_for_free ... ok
test tests::fibonacci_generates_correct_sequence ... ok
test tests::inventory_into_iterator_by_mut_ref_allows_mutation ... ok
test tests::inventory_into_iterator_by_ref_borrows ... ok
test tests::inventory_into_iterator_by_value_moves_ownership ... ok
test tests::sliding_window_produces_overlapping_windows ... ok
test tests::sliding_window_returns_none_when_slice_shorter_than_size ... ok

test result: ok. 7 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

🪜 Step-by-Step 解説

📋 コピーfn next(&mut self) -> Option<Self::Item> {
    let value = self.curr;
    let new_next = self.curr + self.next;
    self.curr = self.next;
    self.next = new_next;
    Some(value)
}

📋 コピーstruct SlidingWindow<'a, T> {
    slice: &'a [T],
    size: usize,
    pos: usize,
}

📋 コピーimpl IntoIterator for Inventory { /* self を消費 */ }
impl<'a> IntoIterator for &'a Inventory { /* &self 相当、借用 */ }
impl<'a> IntoIterator for &'a mut Inventory { /* &mut self 相当、可変借用 */ }

📋 コピーFibonacci::new().filter(|x| x % 2 == 0).take(5).collect::<Vec<u64>>()

💡 設計思想・なぜこう書くのか

🛑 コンパイルエラーが出た場合

Iteratorの関連型Itemを指定し忘れると、次のようなエラーが出ます。

読み方: Iteratorトレイトはnext()というメソッドに加えて、type Itemという関連型も要求します。fn next(&mut self) -> Option<Self::Item>と書いても、Self::Itemが何であるかをどこかで宣言しない限りコンパイラは型を決定できません。impl Iterator for Fibonacci { type Item = u64; fn next(...) ... }のように、type Item = 具体型;という行をimplブロックの先頭に必ず追加する必要があります。

また、SlidingWindowのライフタイム注釈を誤って省略すると、次のようなエラーになることがあります。

読み方: 構造体が参照フィールド（&[T]）を持つ場合、その参照が「どれだけ長く有効か」を型自体に刻む必要があります。struct SlidingWindow<'a, T> { slice: &'a [T], ... }のようにライフタイムパラメータ'aを明示的に宣言し、フィールドの参照に紐づけることでコンパイラに寿命の情報を伝えます。

🌐 他言語との比較

Goのiter.Seq（range-over-func、2024年のGo 1.23で追加）は、RustのIteratorが長年提供してきた「呼び出し側が任意のタイミングで停止できるプル型の走査」に近い機能を後から言語に取り込んだ例です。ただし、Rustのようにnext()実装だけで数十のアダプタメソッドが自動的に使えるようになる仕組みは、GoやJavaの標準ライブラリには薄く、Rustのトレイトのデフォルト実装機構ならではの強みです。

🏆 実務での使いどころ

• ページネーションクライアント: APIやDBカーソルから「次のページ」を取得するロジックをIteratorとして実装すると、呼び出し側はtake(3)（先頭3ページだけ）やtake_while(|page| !page.items.is_empty())（空ページに達するまで）のように、ページ送りの詳細を意識せず宣言的に書けます
• ログ/イベントストリームのパーサ: バイト列やファイルを少しずつ読みながらトークンやレコードを1つずつ生成するパーサをIteratorとして書くと、メモリに全データを載せずにfilterやmapを挟んだ処理チェーンを組めます
• 時系列データの特徴量計算: 本問のSlidingWindowのような「重なり合う窓」のイテレータは、移動平均やローリング統計量の計算で頻出するパターンです。標準のslice::windows()はまさにこの実装をライブラリ化したものです

⚠️ よくある誤解・ミス

🚀 次のステップ

• 発展: SlidingWindowにDoubleEndedIterator（next_back()）を追加実装し、.rev()で末尾側からもウィンドウを取り出せるようにしてみてください
• 次回予告: Day 018ではスマートポインタ①（Box<T>）を扱います。ヒープ確保と再帰的データ構造（連結リスト・木構造）を、所有権システムの上でどう表現するかを学びます

🎯 自己評価

自分の回答

気づき・メモ