Day 023 — カスタムイテレータの実装（DoubleEndedIterator と ExactSizeIterator の実装）

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

Day 022では&mut [i32]を1要素ずつ取り出すIterMut<'a>を、std::mem::takeを使って安全に実装しました。今日はこのIterMut<'a>に、標準ライブラリの多くのイテレータが実装している2つのマーカー的な拡張トレイトを追加します。

1. DoubleEndedIterator: next()（先頭から取り出す）に加えてnext_back()（末尾から取り出す）を提供するトレイトです。このトレイトを実装すると、標準ライブラリが提供する.rev()アダプタが自動的に使えるようになります。

pub trait DoubleEndedIterator: Iterator {
    fn next_back(&mut self) -> Option<Self::Item>;
}

2. ExactSizeIterator: 「残り要素数をO(1)で正確に把握できる」ことを表明するトレイトです。Vec::with_capacityを使ったcollect()の事前確保など、標準ライブラリの各所がこの性質を利用して最適化を行います。

pub trait ExactSizeIterator: Iterator {
    fn len(&self) -> usize {
        // デフォルト実装は size_hint() の (lower, upper) が
        // upper == Some(lower) であることを前提に lower を返す
        let (lower, upper) = self.size_hint();
        assert_eq!(upper, Some(lower));
        lower
    }
}

これらは「マーカートレイト」と呼ばれることもありますが、Rustにおいては単なる目印ではなく、「この性質を満たすことをコンパイラと呼び出し側に約束する契約」です。誤った実装をしても即座にコンパイルエラーにはなりませんが（unsafe traitではないため）、契約違反は「ロジックエラー」として扱われ、.rev().rev()の不一致やVec::with_capacityの見積もりミスといった形で静かに現れます。

📝 問題

Day 022のIterMut<'a>（下記に再掲）に、次の3つを追加実装してください。

📋 コピーstruct IterMut<'a> {
    slice: &'a mut [i32],
}

impl<'a> IterMut<'a> {
    fn new(slice: &'a mut [i32]) -> Self {
        IterMut { slice }
    }
}

impl<'a> Iterator for IterMut<'a> {
    type Item = &'a mut i32;

    fn next(&mut self) -> Option<Self::Item> {
        let slice = std::mem::take(&mut self.slice);
        if slice.is_empty() {
            return None;
        }
        let (first, rest) = slice.split_at_mut(1);
        self.slice = rest;
        Some(&mut first[0])
    }
}

課題

1. Iterator::size_hintをオーバーライドし、self.slice.len()を使って常に正確な残り要素数を返すようにしてください（(lower, upper)の両方が同じ値になります）
2. DoubleEndedIteratorを実装し、next_back()で末尾から1要素ずつ&mut i32を取り出せるようにしてください。next()と同様にstd::mem::takeを使い、借用チェッカーを通してください
3. ExactSizeIteratorを実装してください（Step 1でsize_hintを正確にしていれば、デフォルトのlen()がそのまま使えるはずです。使えない場合は理由を考えてください）
4. mainでIterMut::new(&mut data).by_ref().rev()を使い、要素を逆順に処理しながら全要素を10倍する処理を書いてください
5. 次の3点を#[test]で検証してください
   • .rev()で本当に末尾から順に処理されること
   • next()の呼び出し前後で.len()が正しく減ること
   • next()とnext_back()を交互に呼んでも要素の重複・取りこぼしが起きないこと（「両端から真ん中に向かって消費する」動作の正しさ）

🔍 ヒント（段階的開示）

📋 コピーimpl<'a> Iterator for IterMut<'a> {
    type Item = &'a mut i32;

    fn next(&mut self) -> Option<Self::Item> {
        // (Day 022 と同じ)
        let slice = std::mem::take(&mut self.slice);
        if slice.is_empty() {
            return None;
        }
        let (first, rest) = slice.split_at_mut(1);
        self.slice = rest;
        Some(&mut first[0])
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let len = self.slice.len();
        (len, Some(len)) // 常に正確なので lower == upper
    }
}

impl<'a> DoubleEndedIterator for IterMut<'a> {
    fn next_back(&mut self) -> Option<Self::Item> {
        let slice = std::mem::take(&mut self.slice);
        if slice.is_empty() {
            return None;
        }
        let last_index = slice.len() - 1;
        let (rest, last) = slice.split_at_mut(last_index);
        self.slice = rest;
        Some(&mut last[0])
    }
}

impl<'a> ExactSizeIterator for IterMut<'a> {
    // len() はデフォルト実装（size_hint 由来）のままでOK
}

✅ 模範解答

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

struct IterMut<'a> {
    slice: &'a mut [i32],
}

impl<'a> IterMut<'a> {
    fn new(slice: &'a mut [i32]) -> Self {
        IterMut { slice }
    }
}

impl<'a> Iterator for IterMut<'a> {
    type Item = &'a mut i32;

    fn next(&mut self) -> Option<Self::Item> {
        let slice = std::mem::take(&mut self.slice);
        if slice.is_empty() {
            return None;
        }
        let (first, rest) = slice.split_at_mut(1);
        self.slice = rest;
        Some(&mut first[0])
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let len = self.slice.len();
        (len, Some(len))
    }
}

impl<'a> DoubleEndedIterator for IterMut<'a> {
    fn next_back(&mut self) -> Option<Self::Item> {
        let slice = std::mem::take(&mut self.slice);
        if slice.is_empty() {
            return None;
        }
        let last_index = slice.len() - 1;
        let (rest, last) = slice.split_at_mut(last_index);
        self.slice = rest;
        Some(&mut last[0])
    }
}

impl<'a> ExactSizeIterator for IterMut<'a> {
    // len() は Iterator::size_hint() から自動導出されるデフォルト実装のままでよい。
    // size_hint() を正確に (len, Some(len)) にしておけば、
    // ExactSizeIterator::len() のデフォルト実装内の assert_eq!(upper, Some(lower)) が
    // 必ず成立するため、ここでの再実装は不要。
}

fn main() {
    let mut data = vec![1, 2, 3, 4, 5];
    let mut it = IterMut::new(&mut data);
    assert_eq!(it.len(), 5);

    // by_ref() で it 自体を消費せずに参照として rev() に渡す
    for x in it.by_ref().rev() {
        *x *= 10;
    }
    println!("{:?}", data);
}

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

    #[test]
    fn rev_processes_from_the_back() {
        let mut data = vec![1, 2, 3];
        let mut order = Vec::new();
        for x in IterMut::new(&mut data).rev() {
            order.push(*x);
        }
        // 元の値がそのまま「末尾→先頭」の順に観測される
        assert_eq!(order, vec![3, 2, 1]);
    }

    #[test]
    fn len_tracks_remaining_elements_precisely() {
        let mut data = vec![1, 2, 3];
        let mut it = IterMut::new(&mut data);
        assert_eq!(it.len(), 3);

        it.next();
        assert_eq!(it.len(), 2);

        it.next_back();
        assert_eq!(it.len(), 1);

        it.next();
        assert_eq!(it.len(), 0);
        assert_eq!(it.next(), None);
    }

    #[test]
    fn alternating_front_and_back_never_overlaps_or_skips() {
        let mut data = vec![1, 2, 3, 4, 5];
        let mut it = IterMut::new(&mut data);
        let mut front = Vec::new();
        let mut back = Vec::new();

        loop {
            match it.next() {
                Some(x) => front.push(*x),
                None => break,
            }
            match it.next_back() {
                Some(x) => back.push(*x),
                None => break,
            }
        }

        back.reverse();
        let mut merged = front;
        merged.extend(back);
        // 両端から交互に消費しても、5要素すべてが重複・欠落なく
        // 元の並び順で回収できる
        assert_eq!(merged, vec![1, 2, 3, 4, 5]);
    }
}

$ cargo run
[10, 20, 30, 40, 50]

$ cargo test
running 3 tests
test tests::alternating_front_and_back_never_overlaps_or_skips ... ok
test tests::len_tracks_remaining_elements_precisely ... ok
test tests::rev_processes_from_the_back ... ok

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

🪜 Step-by-Step 解説

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

DoubleEndedIteratorとExactSizeIteratorはどちらも契約ベースのトレイトです。コンパイラは「あなたのnext_back()が本当にnext()と反対側から要素を取り出しているか」や「あなたのlen()が本当に正確か」を検証できません（これは意味論の正しさであり、型では表現しきれないためです）。それでもRustがこのようなトレイトを標準に用意しているのは、「性質を型に刻み込み、その性質に依存する最適化コードを安全に書けるようにする」という設計哲学の表れです。

• .rev()はDoubleEndedIteratorを実装したイテレータにしか使えません。これにより、「進行方向が1つしかないイテレータに.rev()を書いてしまうミス」はコンパイルエラーになります（実行時に気づくのではなく）
• Vec::with_capacityを使うcollect::<Vec<_>>()の内部実装は、対象のイテレータがExactSizeIterator（またはTrustedLen、Rustの内部トレイト）を実装していれば、事前に必要な容量を確保してから要素を詰め込みます。これにより再割り当て（reallocation）の回数がゼロになり、pushを繰り返すよりも高速になります

🌐 他言語との比較

C++のイテレータカテゴリ（Input/Forward/Bidirectional/RandomAccess）はコンセプト的には近いですが、C++20以前は「その型が本当にそのカテゴリの要件を満たしているか」をコンパイラが強制できず、規約（documentation）に頼る面がありました。RustのDoubleEndedIterator/ExactSizeIteratorはトレイトというコンパイラが検証できる境界として表現される点が大きな違いです（ただし「意味論的な正しさ」＝本当に逆から取り出しているか、は依然としてコンパイラの検証範囲外である点は同じです）。

🏆 実務での使いどころ

• .rev(): ログの新しい順から古い順への走査、VecDequeを使ったスタック/キューの両端操作、回文判定（先頭と末尾を同時に消費して比較する）
• ExactSizeIterator + .len(): プログレスバーの進捗計算（(total - remaining) / total）、バッチ処理での残件数表示
• 並列処理クレートrayonのpar_iter()は、内部でIndexedParallelIterator（ExactSizeIteratorに近い性質を要求する）を使い、「作業を半分に割って別スレッドに投げる」という分割統治を安全に行っています。今日実装したsize_hint/lenの正確さは、こうした並列分割の土台になる性質です
• ゲームのダブルバッファ・リングバッファで「両端から同時に要素を取り出したい」（例: 最古のイベントと最新のイベントを同時に処理する）場面

⚠️ よくある誤解・ミス

🚀 次のステップ

• 発展: ExactSizeIterator::len()をあえて独自にオーバーライドしてself.slice.len()を直接返す版と、今日のデフォルト実装版とで、生成されるアセンブリやパフォーマンスに違いが出るかcargo build --releaseして比較してみましょう（多くの場合インライン化されて差はなくなりますが、「単一の情報源に一本化する」設計判断の実感が得られます）
• 次回予告: 自己評価で「完全理解」または「おおむね理解」が3回連続で記録された時点で、次のテーマスマートポインタ①（Box<T>）（ヒープ確保・再帰的データ構造）に進みます

🎯 自己評価

自分の回答

気づき・メモ