Day 026 — カスタムイテレータの実装（自作 StepBy イテレータの off-by-one バグを発見・修正する）

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

Day 016〜025ではIterator・IntoIterator・FromIterator・Extend・DoubleEndedIteratorなど、様々なトレイトを自作型に実装してきました。ここまでで得た教訓のひとつは「型が合ってコンパイルが通ること」と「意味的に正しく動くこと」は別問題だ、ということです。

借用チェッカーは「同時に複数の可変参照が存在しないか」「参照がダングリングしないか」を厳密にチェックしてくれますが、あなたが書いたnext()の中身が業務要件どおりの値を返しているかまでは検証してくれません。Iteratorトレイトが要求するのは「fn next(&mut self) -> Option<Self::Item>というシグネチャを満たすこと」だけであり、「何番目の要素を返すべきか」というロジックの正しさは、型システムの外側にあるあなた自身の責任です。

今日はその典型例として、標準ライブラリのIterator::step_by(n)（n個おきに要素を取り出す）を自作するMyStepBy<I>を題材にします。

// 標準ライブラリの動作(お手本)
let v: Vec<i32> = (0..10).step_by(2).collect();
assert_eq!(v, vec![0, 2, 4, 6, 8]);

step_by(2)は「2個おき」＝「インデックス0, 2, 4, 6, 8」を返します。一見単純に見えるこのロジックですが、自分でnext()を書くとoff-by-one（1個分のズレ）バグに非常に陥りやすい実装です。今日はまずバグ入りの実装を提示するので、それを見抜いて修正してください。

📝 問題

以下のMyStepBy<I>は「step個おきに要素を返すイテレータ」を意図して書かれたコードです。コンパイルは通りますが、実行すると標準ライブラリのstep_by()とは異なる結果になります。

📋 コピーpub struct MyStepBy<I: Iterator> {
    iter: I,
    step: usize,
}

impl<I: Iterator> MyStepBy<I> {
    pub fn new(iter: I, step: usize) -> Self {
        MyStepBy { iter, step }
    }
}

impl<I: Iterator> Iterator for MyStepBy<I> {
    type Item = I::Item;

    fn next(&mut self) -> Option<Self::Item> {
        let item = self.iter.next()?;
        for _ in 0..self.step {
            self.iter.next();
        }
        Some(item)
    }
}

fn main() {
    let v: Vec<i32> = MyStepBy::new(0..10, 2).collect();
    println!("{:?}", v);
}

課題

1. まず手を動かさずに、上記コードを実行した場合の出力を予測してください（0..10に対してstep=2を渡した場合）
2. 実際にcargo runして予測と照合してください。標準ライブラリの(0..10).step_by(2).collect::<Vec<i32>>()（期待値: [0, 2, 4, 6, 8]）と比較し、何が・なぜズレているかを言語化してください
3. stepが「返した要素の後に何個スキップするか」ではなく「何個おきに返すか（＝ストライド幅そのもの）」を意味するようにnext()を修正してください。修正後はMyStepBy::new(0..10, 2).collect::<Vec<i32>>()が[0, 2, 4, 6, 8]と一致すること
4. 標準ライブラリのstep_by()はstep == 0が渡されるとパニックする仕様です（assert!でガード）。MyStepBy::new()にも同様のガードを追加してください
5. #[test]で以下を検証してください
   • step=1のとき元のイテレータと完全に同じ結果になる（MyStepBy::new(0..5, 1).collect::<Vec<_>>() == (0..5).collect::<Vec<_>>()）
   • step=2とstep=3それぞれについて、標準の.step_by()の結果と自作MyStepByの結果が一致する
   • MyStepBy::new(0..10, 0)を呼ぶと#[should_panic]でパニックすることを確認する

🔍 ヒント（段階的開示）

📋 コピーimpl<I: Iterator> MyStepBy<I> {
    pub fn new(iter: I, step: usize) -> Self {
        assert!(step != 0, "step must be non-zero");
        MyStepBy { iter, step, first_take: true }
    }
}

impl<I: Iterator> Iterator for MyStepBy<I> {
    type Item = I::Item;

    fn next(&mut self) -> Option<Self::Item> {
        if self.first_take {
            self.first_take = false;
            self.iter.next()
        } else {
            self.iter.nth(self.step - 1)
        }
    }
}

✅ 模範解答

📋 コピー// このコードは cargo new day026_stepby_bugfix && cd day026_stepby_bugfix の後、
// src/main.rs をこの内容で置き換えて `cargo run` / `cargo test` で検証できます。

pub struct MyStepBy<I: Iterator> {
    iter: I,
    step: usize,
    first_take: bool,
}

impl<I: Iterator> MyStepBy<I> {
    pub fn new(iter: I, step: usize) -> Self {
        // 標準ライブラリの step_by() と同じ仕様: step が 0 だとパニックする
        assert!(step != 0, "step must be non-zero");
        MyStepBy {
            iter,
            // 「返した後に何個捨てるか」を先に引いておく(step-1)。
            // これが今日のバグの本質的な修正ポイント。
            step: step - 1,
            first_take: true,
        }
    }
}

impl<I: Iterator> Iterator for MyStepBy<I> {
    type Item = I::Item;

    fn next(&mut self) -> Option<Self::Item> {
        if self.first_take {
            // 最初の1個は無条件にそのまま返す(スキップなし)
            self.first_take = false;
            self.iter.next()
        } else {
            // nth(n) は「n個消費してからn+1個目を返す」= 「n個捨てて次を返す」
            self.iter.nth(self.step)
        }
    }
}

fn main() {
    // --- バグ入り版で何が起きていたかの再現(コメントアウトで保存) ---
    // struct BuggyStepBy<I: Iterator> { iter: I, step: usize }
    // impl<I: Iterator> Iterator for BuggyStepBy<I> {
    //     type Item = I::Item;
    //     fn next(&mut self) -> Option<Self::Item> {
    //         let item = self.iter.next()?;
    //         for _ in 0..self.step { self.iter.next(); }
    //         Some(item)
    //     }
    // }
    // バグ版で step=2 を渡すと、1回のnext()で「返す1個+捨てる2個」=計3個消費するため
    // 実質ストライド幅3になり、0, 3, 6, 9 が返ってしまう(期待値は0, 2, 4, 6, 8)。

    let fixed: Vec<i32> = MyStepBy::new(0..10, 2).collect();
    println!("修正後 step=2: {:?}", fixed);

    let std_result: Vec<i32> = (0..10).step_by(2).collect();
    println!("標準ライブラリ step_by(2): {:?}", std_result);

    assert_eq!(fixed, std_result);
    println!("一致を確認しました");
}

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

    #[test]
    fn step_one_matches_original_iterator() {
        let mine: Vec<i32> = MyStepBy::new(0..5, 1).collect();
        let original: Vec<i32> = (0..5).collect();
        assert_eq!(mine, original);
    }

    #[test]
    fn step_two_matches_std_step_by() {
        let mine: Vec<i32> = MyStepBy::new(0..10, 2).collect();
        let std_version: Vec<i32> = (0..10).step_by(2).collect();
        assert_eq!(mine, std_version);
        assert_eq!(mine, vec![0, 2, 4, 6, 8]);
    }

    #[test]
    fn step_three_matches_std_step_by() {
        let mine: Vec<i32> = MyStepBy::new(0..10, 3).collect();
        let std_version: Vec<i32> = (0..10).step_by(3).collect();
        assert_eq!(mine, std_version);
        assert_eq!(mine, vec![0, 3, 6, 9]);
    }

    #[test]
    #[should_panic(expected = "step must be non-zero")]
    fn zero_step_panics() {
        let _ = MyStepBy::new(0..10, 0);
    }
}

$ cargo run
修正後 step=2: [0, 2, 4, 6, 8]
標準ライブラリ step_by(2): [0, 2, 4, 6, 8]
一致を確認しました

$ cargo test
running 4 tests
test tests::step_one_matches_original_iterator ... ok
test tests::step_two_matches_std_step_by ... ok
test tests::step_three_matches_std_step_by ... ok
test tests::zero_step_panics ... ok

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

🪜 Step-by-Step 解説

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

Rustの型システムと借用チェッカーが保証するのは「メモリ安全性」（ダングリングポインタ・データ競合・二重解放が起きない）であり、「あなたのアルゴリズムが要件を満たしているか」ではありません。この区別はRust学習者が誤解しやすいポイントで、「コンパイルが通った＝正しい」という思い込みは危険です。

今日のバグは、for _ in 0..self.step { self.iter.next(); }という一見自然に見えるループの中に、stepとstep - 1の混同という単純な意味論のズレが隠れていた例です。型チェックはこのズレを一切検出できません。だからこそ、Rustの標準ライブラリのソースコードでもIteratorの自前実装には必ずテスト（多くの場合#[test]に加えて#[should_panic]によるエッジケース検証）が付随します。「借用チェッカーが守ってくれる領域」と「テストで自分が守るべき領域」を明確に線引きする感覚は、Rustで実務コードを書くうえで不可欠です。

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

今日の問題はコンパイルエラーではなく実行時の論理バグです。cargo buildはバグ入り版に対してもエラー・警告なしで成功します。これは今日の学びの核心でもあります。

読み方: ビルドが成功しても、それは「型が合っている」「借用規則に違反していない」ことしか保証しません。今日のように「返す個数と捨てる個数の計算式を1個間違える」ようなロジックバグは、テストを書いて期待値と突き合わせるまで気づけません。

もし修正の途中でself.stepをusizeの範囲外に落とし込むミス（例えばstep: 0のままnth(self.step - 1)を呼んでアンダーフローする）をすると、今度は次のような実行時パニックが出ます。

読み方: usizeは符号なし整数なので0 - 1は表現できず、デバッグビルドでは「オーバーフロー検出」によりパニックします。これは今日の課題4（step == 0をnew()の時点でassert!によって弾く）が必要な理由そのものです。コンストラクタでガードしておけば、next()側でself.step - 1（stepフィールドは既にstep - 1を保持済み）のような引き算を安全に行えます。

🌐 他言語との比較

どの言語でも「1個目は特別扱い、2個目以降は等間隔」という非対称なロジックを実装する際にoff-by-oneが起きやすい点は共通しています。Rustが他言語と違うのは、型システムがこのバグを検出できないことをコード上で自覚しやすい（unsafeを使っていないのに「安全なのに間違っている」という状態が明示的にテストの失敗として現れる）点です。

🏆 実務での使いどころ

• ログやメトリクスのサンプリング処理（大量のイベントストリームから一定間隔で1件だけ処理する）で、既存のIterator/Streamをラップする独自アダプタを書く場面は多く、今日のような「最初の要素の特別扱い」を含む非対称ロジックは頻出パターンです
• ページネーションAPIのラッパーで「N件ごとに1件だけプレビュー表示する」といった間引き処理を独自実装する際、今日と同じ off-by-one の罠にはまりやすい箇所です
• 「コンパイルは通るがロジックが間違っている」バグは、コードレビューでも見逃されやすい種類のバグです。今日のように「標準ライブラリの正解実装と突き合わせるテストを書く」（assert_eq!(mine, std_version)）というアプローチは、独自実装が標準の挙動を模倣すべき場面（互換レイヤーの実装等）で実務的に非常に有効です

⚠️ よくある誤解・ミス

🚀 次のステップ

• 発展: 今日のMyStepBy<I>にDoubleEndedIterator（Day 023で実装済みのトレイト）を追加実装し、後ろからもstep個おきに取り出せるようにしてみましょう。前からと後ろからで「1個目の特別扱い」の非対称性がどう影響するか、考えてみると理解が深まります
• 次回予告: 自己評価で「完全理解」または「おおむね理解」が3回連続で記録された時点で、次のテーマスマートポインタ①（Box<T>）（ヒープ確保・再帰的データ構造）に進みます

🎯 自己評価

自分の回答

気づき・メモ