Day 020 — カスタムイテレータの実装（自作アダプタ型 Windows2<I> と拡張トレイトパターン）

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

Day 017〜019ではCounterやAlternatorのような「ソースイテレータ」（データを内部で生成し、外部の値を持たない）を実装してきました。今日は一段階進んで、「アダプタイテレータ」――既存の任意のIteratorを内部に包み込み（wrap）、それを加工した値を返す型――を自分で実装します。標準ライブラリのMap<I, F>やFilter<I, P>はまさにこの形をしています。

📋 コピー// 標準ライブラリの Map の概念的な構造（実際はもう少し複雑）
pub struct Map<I, F> {
    iter: I,  // 内側のイテレータをまるごと所有する
    f: F,
}

impl<B, I: Iterator, F> Iterator for Map<I, F>
where
    F: FnMut(I::Item) -> B,
{
    type Item = B;
    fn next(&mut self) -> Option<B> {
        self.iter.next().map(&mut self.f)
    }
}

ここで重要なのは、Map<I, F>が特定の型に対してではなく、任意のI: Iteratorに対してジェネリックに実装されているという点です。あなたがVec::iter()に対して.map()を呼んでも、独自のCounterに対して.map()を呼んでも、コンパイラは呼ばれた具体的なIごとに単相化されたMap<Vec<T>への参照, F>やMap<Counter, F>を生成します。

もう1つ今日学ぶのが「拡張トレイト（extension trait）パターン」です。Rustにはオーファンルール（orphan rule: 自分のクレートで定義していない型に対して、自分のクレートで定義していないトレイトを実装できない）があるため、Vec<T>のような標準ライブラリの型に対して勝手にメソッドを生やすことはできません。しかし「Iteratorを実装しているすべての型に対して、自分で定義したトレイト（に自分で書いたデフォルト実装）を一括で実装する」というブランケット実装（blanket impl）を使えば、標準の型・自作の型を問わず.windows2()のような独自メソッドを追加できます。これはitertoolsクレートが.tuple_windows()や.chunks()のようなメソッドを任意のイテレータに追加している仕組みそのものです。

📝 問題

std::sliceにあるwindows(2)（スライスに対して重なり合う2要素のウィンドウを順に返す）と同等の機能を、任意のイテレータに対して使えるアダプタとして実装してください。

要求1: Windows2<I> 構造体の実装

内側のイテレータIを保持し、(前の要素, 今の要素)のペアを順に返す構造体Windows2<I>を定義し、Iteratorを実装してください。

• I::Item: Cloneという制約を型に課してよい（値を複製して保持する設計にする）
• 内側のイテレータが[a, b, c, d]を生成する場合、Windows2は(a,b), (b,c), (c,d)の順に3つのペアを返す
• 内側の要素が0個または1個しかない場合、Windows2は1つも値を返さない（Noneを即座に返す）

要求2: 拡張トレイト Windows2Ext の実装

Iteratorを実装しているあらゆる型（標準のVec::into_iter()・Range・自作のCounter等）に対して.windows2()という新しいメソッドを追加する拡張トレイトWindows2Extを定義し、ブランケット実装（impl<I: Iterator> Windows2Ext for I where I::Item: Clone {}のような形）で、Iteratorを実装するすべての型に自動的に行き渡るようにしてください。

要求3: 動作確認

以下2パターンをテストで確認してください。

• vec![1, 2, 3, 4].into_iter().windows2()が[(1,2), (2,3), (3,4)]を返す
• 要素が1個以下の場合（例: vec![1].into_iter().windows2()）に何も返さない（.next()が最初からNone）

🔍 ヒント（段階的開示）

📋 コピーstruct Windows2<I: Iterator> {
    inner: I,
    prev: Option<I::Item>,
}

impl<I: Iterator> Iterator for Windows2<I>
where
    I::Item: Clone,
{
    type Item = (I::Item, I::Item);

    fn next(&mut self) -> Option<Self::Item> {
        if self.prev.is_none() {
            self.prev = self.inner.next();
        }
        let prev = self.prev.clone()?;
        let current = self.inner.next()?;
        self.prev = Some(current.clone());
        Some((prev, current))
    }
}

trait Windows2Ext: Iterator + Sized {
    fn windows2(self) -> Windows2<Self>
    where
        Self::Item: Clone,
    {
        Windows2 { inner: self, prev: None }
    }
}

impl<I: Iterator> Windows2Ext for I {}

✅ 模範解答

📋 コピーstruct Windows2<I: Iterator> {
    inner: I,
    prev: Option<I::Item>,
}

impl<I: Iterator> Iterator for Windows2<I>
where
    I::Item: Clone,
{
    type Item = (I::Item, I::Item);

    fn next(&mut self) -> Option<Self::Item> {
        // prev がまだ埋まっていなければ、内側から1つ取り出して初期化する
        if self.prev.is_none() {
            self.prev = self.inner.next();
        }
        // prev が取れなかった（内側が最初から空だった）場合はそこで終了
        let prev = self.prev.clone()?;
        // 内側から次の要素を取り出す。取れなければ（もう1要素しか残っていなかった）終了
        let current = self.inner.next()?;
        // 次回の呼び出しのために prev を current で更新しておく
        self.prev = Some(current.clone());
        Some((prev, current))
    }
}

// ---- 拡張トレイト: 任意の Iterator に .windows2() を生やす ----

trait Windows2Ext: Iterator + Sized {
    fn windows2(self) -> Windows2<Self>
    where
        Self::Item: Clone,
    {
        Windows2 {
            inner: self,
            prev: None,
        }
    }
}

// ブランケット実装: Iterator を実装するすべての型に一括付与される
impl<I: Iterator> Windows2Ext for I {}

fn main() {
    // 標準の Vec イテレータに対して独自メソッド .windows2() が使える
    let pairs: Vec<(i32, i32)> = vec![1, 2, 3, 4].into_iter().windows2().collect();
    println!("{pairs:?}");

    // Range に対しても同じメソッドが（ブランケット実装のおかげで）使える
    let range_pairs: Vec<(i32, i32)> = (10..14).windows2().collect();
    println!("{range_pairs:?}");
}

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

    #[test]
    fn windows2_yields_overlapping_pairs() {
        let pairs: Vec<(i32, i32)> = vec![1, 2, 3, 4].into_iter().windows2().collect();
        assert_eq!(pairs, vec![(1, 2), (2, 3), (3, 4)]);
    }

    #[test]
    fn windows2_empty_for_single_or_zero_elements() {
        let one: Vec<(i32, i32)> = vec![1].into_iter().windows2().collect();
        assert_eq!(one, Vec::<(i32, i32)>::new());

        let zero: Vec<(i32, i32)> = Vec::<i32>::new().into_iter().windows2().collect();
        assert_eq!(zero, Vec::<(i32, i32)>::new());
    }

    #[test]
    fn windows2_works_on_range_via_blanket_impl() {
        let pairs: Vec<(i32, i32)> = (10..13).windows2().collect();
        assert_eq!(pairs, vec![(10, 11), (11, 12)]);
    }
}

$ cargo run
[(1, 2), (2, 3), (3, 4)]
[(10, 11), (11, 12), (12, 13)]

$ cargo test
running 3 tests
test tests::windows2_empty_for_single_or_zero_elements ... ok
test tests::windows2_works_on_range_via_blanket_impl ... ok
test tests::windows2_yields_overlapping_pairs ... ok

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

🪜 Step-by-Step 解説

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

🌐 他言語との比較

Rustの拡張トレイトパターンは、C#の拡張メソッド（public static class Extensions { public static IEnumerable<T> Windows2(this IEnumerable<T> src) ... }）に発想としては最も近いものです。ただしC#は言語機能として「拡張メソッド」を直接サポートしているのに対し、Rustは「トレイト＋ブランケット実装」という既存の言語機能の組み合わせだけでこれを実現している点が異なります。専用構文を足さずに既存の型システムの表現力だけで同等のことができるのは、Rustのトレイトシステムの汎用性の高さを示す例の1つです。

🏆 実務での使いどころ

• 時系列データの差分計算: センサーログや株価データのような時系列Vec<f64>に対して.windows2().map(|(prev, cur)| cur - prev)とすれば、隣接データ間の差分（変化量）を1行で計算できます。移動平均・変化率検知・異常値検出の前処理として頻出するパターンです
• ログ処理でのイベント間隔計算: タイムスタンプ付きログを.windows2()で走査し、(prev.timestamp, cur.timestamp)の差分からイベント間隔の分布を計測する、というのは監視・オブザーバビリティ基盤の実装で日常的に使われる手法です
• 拡張トレイトパターン自体の実務価値: 社内共通ライブラリで「標準のIteratorに業務固有の集計メソッドを生やしたい」という場面は頻出します（例: .group_consecutive_by()のような独自集計）。今回学んだブランケット実装のパターンは、そのまま社内クレートのAPI設計に転用できます

⚠️ よくある誤解・ミス

🚀 次のステップ

• 発展: 今回のWindows2<I>をさらに一般化し、ウィンドウサイズを2固定ではなくN（VecDeque<I::Item>をリングバッファとして使う）に拡張したWindowsN<I>を実装してみてください。あるいは、値を複製せず&I::Itemの参照ペアを返す設計（内側のイテレータがIterator<Item = &T>である場合に限定すれば複製コストゼロにできる）にも挑戦してみると、Step 2で触れたトレードオフを体感できます
• 次回予告: 自己評価で「完全理解」または「おおむね理解」が3回連続で記録された時点で、次のテーマスマートポインタ①（Box<T>）（ヒープ確保・再帰的データ構造）に進みます

🎯 自己評価

自分の回答

気づき・メモ