Day 021 — カスタムイテレータの実装（実装すべきトレイトの選定とAPI設計判断）

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

Day 017〜020でCounter（ソースイテレータ）とWindows2<I>（アダプタイテレータ）を実装し、「動くコードを書く」段階は一通り経験しました。今日は一段視点を上げて、「自作イテレータに、Iterator本体以外のどのマーカートレイトまで実装すべきか」という設計判断を扱います。

標準ライブラリのイテレータ関連トレイトには、Iterator本体の他に主に3つの補助トレイトがあります。

これらはマーカートレイト（あるいは追加の性能保証を与えるトレイト）であり、「実装できるかどうか」はイテレータの内部ロジックによって決まります。無条件に全部実装すればよいというものではなく、「実装した場合に契約（コントラクト）を本当に守れるか」を先に検証し、守れない・守るコストが割に合わないものは実装しないという判断も、Rustのトレイト設計では重要なスキルです。これは「トレイトを実装できること」と「トレイトを実装すべきこと」が必ずしも一致しないという、API設計者に固有の意思決定です。

もう1つ今日扱うのが、公開API関数の戻り値の型設計です。イテレータを返すライブラリ関数を書くとき、-> Vec<T>（即座に全計算して積んだ結果を返す・eager）と-> impl Iterator<Item = T>（呼ばれるたびに1要素ずつ計算する・lazy）のどちらを選ぶかは、性能特性とAPIの柔軟性の両方に影響する設計判断です。

📝 問題

「連続する同じ値をまとめて(値, 連続回数)のペアにする」Run-Length Encoding（連長圧縮）を行うカスタムイテレータRunLengthEncode<I>を題材に、以下の設計判断を行い、それぞれ理由付きで結論を出し、結論を裏付けるコードを実装してください。

設計判断1: ExactSizeIteratorを実装すべきか

RunLengthEncode<I>に対してExactSizeIterator（len()をO(1)かつ正確に返す）を実装すべきかどうかを判断してください。「実装できるか（コンパイルが通るか）」ではなく「契約を正しく守れるか」の観点で結論と理由を述べてください。

設計判断2: DoubleEndedIteratorを実装すべきか

内側のIがDoubleEndedIteratorを実装している場合、RunLengthEncode<I>側にもDoubleEndedIterator（next_back()で末尾から連長圧縮を取り出す）を実装する価値があるかを検討してください。実装する場合の技術的な難所（前からのカーソルと後ろからのカーソルが同じ「連」の途中で衝突するケースをどう扱うか）にも触れ、実装するかしないか結論を出してください。

設計判断3: FusedIteratorを実装すべきか

RunLengthEncode<I>のnext()実装の書き方次第で、内側IがFusedIteratorかどうかに関係なく無条件にFusedIteratorを実装できるかどうかを判断してください（ヒント: next()の中で「一度Noneを観測した後にもう一度inner.next()を呼ぶコードパス」が存在するかどうかを確認してください）。

設計判断4: 公開関数の戻り値型 — Vec<(T, usize)> か impl Iterator<Item = (T, usize)> か

pub fn run_length_encode(...)という公開関数を設計するとして、戻り値を即座に計算済みのVec<(T, usize)>にするか、遅延評価されるimpl Iterator<Item = (T, usize)>にするかを判断してください。「呼び出し側が.take(2)のように結果の先頭だけを使いたい場合、入力全体を消費してしまうかどうか」を実際にコードで検証し、それを判断根拠に含めてください。

実装要件

• RunLengthEncode<I>構造体とIterator実装（I::Item: PartialEq + Cloneという制約は課してよい）
• 上記の設計判断の結論に基づいたsize_hint()・FusedIteratorの実装（実装すべきでないと判断したものは実装しない）
• .take(2)で先頭2グループだけを取り出した場合に、内側のソースが必要以上に消費されないことを検証するテスト（内側の消費回数をカウントする計測用ラッパーイテレータを自作してよい）

🔍 ヒント（段階的開示）

📋 コピーuse std::iter::Peekable;

struct RunLengthEncode<I: Iterator> {
    inner: Peekable<I>,
}

impl<I: Iterator> Iterator for RunLengthEncode<I>
where
    I::Item: PartialEq + Clone,
{
    type Item = (I::Item, usize);

    fn next(&mut self) -> Option<Self::Item> {
        let first = self.inner.next()?;
        let mut count = 1usize;
        while self.inner.peek() == Some(&first) {
            self.inner.next();
            count += 1;
        }
        Some((first, count))
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let (lo, hi) = self.inner.size_hint();
        let lower = if lo == 0 { 0 } else { 1 };
        (lower, hi)
    }
}

// 設計判断3の結論に基づき、内側の性質に関係なく無条件に実装できる
impl<I: Iterator> std::iter::FusedIterator for RunLengthEncode<I> where I::Item: PartialEq + Clone {}

✅ 模範解答

📋 コピーuse std::cell::Cell;
use std::iter::{FusedIterator, Peekable};
use std::rc::Rc;

// ---- 本体: RunLengthEncode<I> ----

struct RunLengthEncode<I: Iterator> {
    inner: Peekable<I>,
}

impl<I: Iterator> Iterator for RunLengthEncode<I>
where
    I::Item: PartialEq + Clone,
{
    type Item = (I::Item, usize);

    fn next(&mut self) -> Option<Self::Item> {
        // 1つ目を取り出せなければ（内側が空）そこで終了。
        // ここで None を観測したら、以降 inner.next() を二度と呼ばない
        // （= FusedIterator を無条件で実装できる根拠）。
        let first = self.inner.next()?;
        let mut count = 1usize;
        // peek() で消費せずに覗き見て、同じ値が続く限り実際に読み進める
        while self.inner.peek() == Some(&first) {
            self.inner.next();
            count += 1;
        }
        Some((first, count))
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        // 設計判断1の結論: 正確な len() は提供できないが、
        // 下限・上限の「範囲」としての size_hint はO(1)で計算できる。
        let (lo, hi) = self.inner.size_hint();
        let lower = if lo == 0 { 0 } else { 1 };
        (lower, hi) // 上限は「全要素が別グループ」のケースでも inner の上限を超えない
    }
}

// 設計判断3の結論: next() の制御フローが「一度 None を見たら二度と inner に触れない」
// 形になっているため、内側 I が FusedIterator かどうかに関係なく無条件に実装できる。
impl<I: Iterator> FusedIterator for RunLengthEncode<I> where I::Item: PartialEq + Clone {}

// 注意: ExactSizeIterator と DoubleEndedIterator は意図的に実装しない
// （設計判断1・2の結論。理由は「Step-by-Step解説」参照）

trait RunLengthExt: Iterator + Sized {
    fn run_length_encode(self) -> RunLengthEncode<Self>
    where
        Self::Item: PartialEq + Clone,
    {
        RunLengthEncode {
            inner: self.peekable(),
        }
    }
}

impl<I: Iterator> RunLengthExt for I {}

// ---- 設計判断4の検証用: 消費回数を数える計測ラッパー ----

struct CountingIter<I> {
    inner: I,
    count: Rc<Cell<usize>>,
}

impl<I: Iterator> Iterator for CountingIter<I> {
    type Item = I::Item;
    fn next(&mut self) -> Option<Self::Item> {
        self.count.set(self.count.get() + 1);
        self.inner.next()
    }
}

fn main() {
    let data = vec![1, 1, 1, 2, 2, 3, 3, 3, 3, 4];
    let groups: Vec<(i32, usize)> = data.into_iter().run_length_encode().collect();
    println!("{groups:?}"); // [(1, 3), (2, 2), (3, 4), (4, 1)]

    // 設計判断4の実証: .take(2) で先頭2グループだけ取れば、
    // 内側の消費は "1,1,1,2,2" の5要素分で止まり、残りの "3,3,3,3,4" には触れない。
    let count = Rc::new(Cell::new(0));
    let source = CountingIter {
        inner: vec![1, 1, 1, 2, 2, 3, 3, 3, 3, 4].into_iter(),
        count: count.clone(),
    };
    let first_two: Vec<(i32, usize)> = source.run_length_encode().take(2).collect();
    println!("{first_two:?}, inner next() 呼び出し回数 = {}", count.get());
}

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

    #[test]
    fn groups_consecutive_equal_elements() {
        let data = vec![1, 1, 1, 2, 2, 3, 3, 3, 3, 4];
        let groups: Vec<(i32, usize)> = data.into_iter().run_length_encode().collect();
        assert_eq!(groups, vec![(1, 3), (2, 2), (3, 4), (4, 1)]);
    }

    #[test]
    fn empty_input_yields_no_groups() {
        let groups: Vec<(i32, usize)> = Vec::<i32>::new().into_iter().run_length_encode().collect();
        assert_eq!(groups, Vec::<(i32, usize)>::new());
    }

    #[test]
    fn size_hint_lower_bound_reflects_at_least_one_group() {
        let iter = vec![1, 1, 2, 2].into_iter().run_length_encode();
        // 中身は2グループだが、size_hint は「範囲」なので下限1・上限4（inner の要素数）で妥当
        assert_eq!(iter.size_hint(), (1, Some(4)));
    }

    #[test]
    fn take_two_does_not_consume_entire_source() {
        let count = Rc::new(Cell::new(0));
        let source = CountingIter {
            inner: vec![1, 1, 1, 2, 2, 3, 3, 3, 3, 4].into_iter(),
            count: count.clone(),
        };
        let first_two: Vec<(i32, usize)> = source.run_length_encode().take(2).collect();

        assert_eq!(first_two, vec![(1, 3), (2, 2)]);
        // 10要素すべてを舐めていれば10になるはずだが、
        // 先頭2グループ（1,1,1,2,2）の直後、3番目のグループの先頭「3」を
        // peek() するところまでで止まるため 6 回で済む。
        assert_eq!(count.get(), 6);
    }

    #[test]
    fn fused_after_exhaustion_never_returns_some_again() {
        let mut iter = vec![1, 1].into_iter().run_length_encode();
        assert_eq!(iter.next(), Some((1, 2)));
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next(), None); // FusedIterator: 何度呼んでも None のまま
    }
}

$ cargo run
[(1, 3), (2, 2), (3, 4), (4, 1)]
[(1, 3), (2, 2)], inner next() 呼び出し回数 = 6

$ cargo test
running 5 tests
test tests::empty_input_yields_no_groups ... ok
test tests::fused_after_exhaustion_never_returns_some_again ... ok
test tests::groups_consecutive_equal_elements ... ok
test tests::size_hint_lower_bound_reflects_at_least_one_group ... ok
test tests::take_two_does_not_consume_entire_source ... ok

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

🪜 Step-by-Step 解説

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

🌐 他言語との比較

Rustが他言語と際立って異なるのは、「遅延か即時か」が関数シグネチャの型そのものに現れるという点です。JavaのStreamやPythonのジェネレータも遅延評価を表現できますが、いずれも「一度しか消費できない」「型注釈だけでは即時評価との区別がつきにくい」といった落とし穴があります。Rustではimpl Iterator<Item = T>という戻り値の型を見ただけで「これは遅延評価される」「複数回collect()はできない（所有権が一度しか渡せない）」という情報がコンパイル時に伝わるため、API利用者が実行してみるまで気付かない類の誤解が構造的に減ります。

🏆 実務での使いどころ

• ログ圧縮・監視データの前処理: 同じステータスコードが連続するアクセスログや、同じセンサー値が連続する時系列データを.run_length_encode()でまとめれば、「変化点だけ」を効率よく抽出できます。ストレージへの保存前に生ログを圧縮する用途にも直結します
• 公開クレートのAPI設計判断そのものが実務スキル: 「このイテレータにExactSizeIteratorを実装していいか」「戻り値をVecにすべきかimpl Iteratorにすべきか」という判断は、社内共通ライブラリやOSSクレートを設計する際に必ず直面する意思決定です。今回学んだ「契約を守れるかで判断する」「破壊的変更のリスクが低い方を先に選ぶ」という基準は、そのままプロダクションのAPI設計レビューに転用できます
• 計測用ラッパーイテレータのテスト手法: CountingIterのように「実際に何回next()が呼ばれたか」を数える薄いラッパーは、パフォーマンスクリティカルなイテレータチェーンで「本当に遅延評価されているか」「意図しない全走査が起きていないか」を検証する実務的なテスト手法として、そのまま流用できます

⚠️ よくある誤解・ミス

🚀 次のステップ

• 発展: 設計判断2で「実装しない」と判断したDoubleEndedIteratorについて、実際に内部状態（front_pending・back_pendingのような両端の未確定カウント）を持たせて実装に挑戦してみると、Step 2で触れた「前後のカーソルが同じ連の中で出会う」問題の難しさを体感できます
• 次回予告: 自己評価で「完全理解」または「おおむね理解」が3回連続で記録された時点で、次のテーマスマートポインタ①（Box<T>）（ヒープ確保・再帰的データ構造）に進みます

🎯 自己評価

自分の回答

気づき・メモ