Day 027 — カスタムイテレータの実装（DoubleEndedIterator — 前後両方向からの走査）

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

Day 024〜026でIntoIterator（3種類の反復方式）、FromIterator/Extend（.collect()/.extend()）、そして自作StepByのoff-by-oneバグ修正を通じて、Iteratorトレイトのnext()実装に習熟してきました。

今日はDoubleEndedIteratorを学びます。これは「末尾からも走査できる」ことを示すトレイトで、next_back()という1つのメソッドを追加実装するだけで、標準ライブラリの.rev()アダプタが自動的に使えるようになります。

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

重要なのは、next()（前から）とnext_back()（後ろから）が同じ要素列を共有しているという点です。Vec<i32>のinto_iter()を思い浮かべるとよいでしょう。標準実装では「前方ポインタ」と「後方ポインタ」の2つを持ち、前から1個進めるたびに前方ポインタを+1、後ろから1個進めるたびに後方ポインタを-1します。2つのポインタが交差した時点で走査終了、つまりfront >= backが終了条件になります。

これは所有権システムと相性がよい設計でもあります。「前からも後ろからも1回ずつしか取り出せない」という制約を型システムではなく走査ロジック（インデックス比較）で表現しているため、同じ要素を二重に返す・所有権を二重に奪う、といったバグが起きやすいポイントです。今日はその境界条件を自分の手で正しく実装することが目的になります。

Vec<T>から要素の所有権を「途中の任意の位置から」奪う場合、単純なdata[i]ではT: Copyでない限りムーブできません（Vecは要素の隙間を許さない連続メモリだからです）。これを回避する定番パターンがVec<Option<T>>にラップし、Option::take()で「その位置だけ空にする」手法です。Option<T>::take()は&mut selfから中身を取り出し、元の場所にはNoneを残す——これも「所有権はムーブするが、元の変数は無効な状態にはせず明示的な『空』状態にする」というRustらしい設計になっています。

📝 問題

以下のVecIter<T>の骨格を完成させ、IteratorとDoubleEndedIteratorを実装してください。要件は以下の通りです。

1. next()は前方から1要素ずつ返す
2. next_back()は後方から1要素ずつ返す
3. next()とnext_back()を交互に呼んでも、同じ要素が2回返されたり、要素が飛ばされたりしないこと（前方ポインタと後方ポインタが交差したら両方ともNoneを返す）
4. .rev()アダプタ（標準ライブラリがDoubleEndedIteratorに対して自動提供する）で完全に逆順のVecが作れること
5. ExactSizeIteratorも実装し、残り要素数を正確に返すこと（size_hint()を根拠にする）

📋 コピーstruct VecIter<T> {
    data: Vec<Option<T>>,
    front: usize,
    back: usize, // 排他的な終端(この位置は含まない)
}

impl<T> VecIter<T> {
    fn new(data: Vec<T>) -> Self {
        todo!()
    }
}

impl<T> Iterator for VecIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        todo!()
    }
}

// ここに DoubleEndedIterator と ExactSizeIterator を実装する

fn main() {
    let it = VecIter::new(vec![1, 2, 3, 4, 5]);
    let collected: Vec<i32> = it.rev().collect();
    assert_eq!(collected, vec![5, 4, 3, 2, 1]);

    let mut it2 = VecIter::new(vec!["a", "b", "c", "d"]);
    assert_eq!(it2.next(), Some("a"));
    assert_eq!(it2.next_back(), Some("d"));
    assert_eq!(it2.next(), Some("b"));
    assert_eq!(it2.next_back(), Some("c"));
    assert_eq!(it2.next(), None);
    assert_eq!(it2.next_back(), None);
    println!("OK");
}

🔍 ヒント（段階的開示）

📋 コピーimpl<T> VecIter<T> {
    fn new(data: Vec<T>) -> Self {
        let len = data.len();
        VecIter {
            data: data.into_iter().map(Some).collect(),
            front: 0,
            back: len,
        }
    }
}

impl<T> Iterator for VecIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        if self.front >= self.back {
            return None;
        }
        let item = self.data[self.front].take();
        self.front += 1;
        item
    }
    fn size_hint(&self) -> (usize, Option<usize>) {
        let remaining = self.back - self.front;
        (remaining, Some(remaining))
    }
}

impl<T> DoubleEndedIterator for VecIter<T> {
    fn next_back(&mut self) -> Option<T> {
        // front >= back のチェックと、back のデクリメント順序を考える
    }
}

✅ 模範解答

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

struct VecIter<T> {
    data: Vec<Option<T>>,
    front: usize,
    back: usize, // 排他的な終端(この位置は含まない)
}

impl<T> VecIter<T> {
    fn new(data: Vec<T>) -> Self {
        let len = data.len();
        VecIter {
            data: data.into_iter().map(Some).collect(),
            front: 0,
            back: len,
        }
    }
}

impl<T> Iterator for VecIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        if self.front >= self.back {
            return None;
        }
        let item = self.data[self.front].take();
        self.front += 1;
        item
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let remaining = self.back - self.front;
        (remaining, Some(remaining))
    }
}

impl<T> DoubleEndedIterator for VecIter<T> {
    fn next_back(&mut self) -> Option<T> {
        if self.front >= self.back {
            return None;
        }
        self.back -= 1;
        self.data[self.back].take()
    }
}

impl<T> ExactSizeIterator for VecIter<T> {}

fn main() {
    let it = VecIter::new(vec![1, 2, 3, 4, 5]);
    let collected: Vec<i32> = it.rev().collect();
    assert_eq!(collected, vec![5, 4, 3, 2, 1]);
    println!("rev結果: {:?}", collected);

    let mut it2 = VecIter::new(vec!["a", "b", "c", "d"]);
    assert_eq!(it2.next(), Some("a"));
    assert_eq!(it2.next_back(), Some("d"));
    assert_eq!(it2.next(), Some("b"));
    assert_eq!(it2.next_back(), Some("c"));
    assert_eq!(it2.next(), None);
    assert_eq!(it2.next_back(), None);
    println!("OK");
}

$ cargo run
rev結果: [5, 4, 3, 2, 1]
OK

🪜 Step-by-Step 解説

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

Rustの標準コレクション（Vec::into_iter、slice::iter、VecDeque::iterなど）は、内部的にほぼ全て「前方ポインタと後方ポインタが中央で出会うまで進む」という同じ設計でDoubleEndedIteratorを実装しています。これは単なる実装上の便宜ではなく、所有権モデルと相性のよい唯一に近い設計でもあります。

もし「前から3個返した後にランダムな位置から取り出す」ような汎用API（インデックスアクセス的な取り出し）を許すと、「その要素はもう誰かが所有権を持っているか」をイテレータ自身が毎回チェックしなければならず、Option<T>による「取得済みフラグ」の管理コストが要素ごとに常につきまといます。一方「前方境界」と「後方境界」という2つの単調に動く値だけで状態を表現すれば、front >= backという1つの比較だけで「取り出し可能かどうか」が判定でき、コンパイラも実行時コストゼロでこれを最適化できます。

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

このテーマで典型的にハマるのは、next_back()の順序を逆にした場合です。以下のように書くとコンパイルは通りますが実行時にパニックします。

fn next_back(&mut self) -> Option<T> {
    if self.front >= self.back {
        return None;
    }
    let item = self.data[self.back].take(); // back を先に読んでしまっている
    self.back -= 1;
    item
}

backは排他的境界（有効な最後の要素はback - 1）なので、self.data[self.back]は範囲外または「まだ生きているが本来返すべきでない」要素にアクセスしてしまいます。back == len（初期状態）でこれを呼ぶと、以下のパニックになります。

読み方: 「配列アクセスのインデックスが範囲外」という意味で、原因は境界値のオフバイワン（off-by-one）です。修正方針は「先にデクリメントしてからアクセスする」の順序を守ることです。

🌐 他言語との比較

RustとC++/Pythonは「専用のトレイト/プロトコルを実装すれば汎用アダプタの恩恵を受けられる」という点で近い設計思想を持ちますが、Rustは所有権付きの値を安全に取り出す（コピーもガベージコレクションも不要）という点で独自性が強い部分です。

🏆 実務での使いどころ

• VecDeque（両端キュー）を扱うコードで前後どちらからも消費するロジックを書く際、標準のDoubleEndedIterator実装を前提にした.rev()や.next_back()の挙動を正しく理解している必要があります
• パーサやトークナイザで「先頭からトークンを読みつつ、末尾の終端記号だけ先に確認する」といった両端アクセスパターンに応用できます
• 独自のリングバッファやスライスラッパー型を実装する際、標準コレクションと同じ「境界の相互作用」の設計に揃えることで、利用者が直感的にAPIを使えるようになります

⚠️ よくある誤解・ミス

🚀 次のステップ

• 発展: next_back()を持つイテレータに対して.rev().rev()を呼んだ場合の挙動（元に戻ることの確認）や、Peekableと組み合わせた両端バッファリングを試してみましょう
• 次回予告: 自己評価で「完全理解」または「おおむね理解」が3回連続で記録された時点で、次のテーマスマートポインタ①（Box<T>）（ヒープ確保・再帰的データ構造）に進みます

🎯 自己評価

自分の回答

気づき・メモ