Day 025 — カスタムイテレータの実装（FromIterator と Extend — .collect()/.extend() を自作型に実装する）

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

Day 024では自作のStack<T>に3種類のIntoIteratorを実装しました。これは「Stack<T>から値を取り出す方向」の変換です。

今日はその逆方向、つまり「イテレータからStack<T>を組み立てる方向」を扱います。具体的には次の2つのトレイトです。

// イテレータを消費して Self を「新規に作る」
pub trait FromIterator<A>: Sized {
    fn from_iter<T: IntoIterator<Item = A>>(iter: T) -> Self;
}

// イテレータを消費して「既存の self に追記する」
pub trait Extend<A> {
    fn extend<T: IntoIterator<Item = A>>(&mut self, iter: T);
}

Vec<T>やHashMap<K, V>がこの2つを実装しているからこそ、私たちは普段何気なく次のように書けています。

let v: Vec<i32> = (1..=5).collect();      // FromIterator が呼ばれている
let mut v2 = vec![1, 2, 3];
v2.extend([4, 5, 6]);                     // Extend が呼ばれている

.collect::<Vec<i32>>()という呼び出しの裏側は、実は次のように脱糖されます。

let v: Vec<i32> = Iterator::collect(iter);
// ↓ collect() の中身はおおよそ
let v: Vec<i32> = FromIterator::from_iter(iter);

Iterator::collect()はジェネリックな「橋渡し役」に過ぎず、実際に値を組み立てているのは戻り値の型が実装しているFromIterator::from_iter()です。戻り値の型注釈（let v: Vec<i32> = ...）だけで呼び出す実装が変わるという、Rustの型推論の力がもっとも顕著に現れる場所のひとつです。

📝 問題

Day 024 で作ったStack<T>（LIFO＝後入れ先出しのスタック、要素はVec<T>で保持し、末尾が「一番上」）に対して、以下を実装してください。

📋 コピーpub struct Stack<T> {
    items: Vec<T>,
}

impl<T> Stack<T> {
    pub fn new() -> Self {
        Stack { items: Vec::new() }
    }

    pub fn push(&mut self, item: T) {
        self.items.push(item);
    }

    pub fn pop(&mut self) -> Option<T> {
        self.items.pop()
    }

    pub fn len(&self) -> usize {
        self.items.len()
    }
}

課題

1. impl<T> FromIterator<T> for Stack<T>を実装してください。let stack: Stack<i32> = vec![1, 2, 3].into_iter().collect();と書いたとき、イテレータが生成する順（1, 2, 3）にそのままの順でpushしたのと同じ状態（＝一番上が3）になるようにしてください
2. impl<T> Extend<T> for Stack<T>を実装してください。stack.extend(vec![4, 5]);と書いたとき、既存のスタックの上に4, 5の順で積み増されるようにしてください（＝push(4); push(5);と同じ結果）
3. 1と2はどちらも内部でVec<T>が既に持つFromIterator/Extend実装に委譲するだけにしてください（Vec<T>: FromIterator<T>とVec<T>: Extend<T>は標準ライブラリに既にあります）。自分でループを書いて1要素ずつpush()する必要はありません
4. mainで以下を実際に動かしてください
   • let stack: Stack<i32> = (1..=5).collect();でStack<i32>を組み立てる
   • stack.extend(vec![10, 20]);で追記する
   • for x in &stack { ... }（Day 024 の&Stack<T>用IntoIteratorを再利用）で結果を表示する
5. #[test]で次を検証してください
   • vec![1, 2, 3].into_iter().collect::<Stack<i32>>()のpop()を3回呼ぶとSome(3), Some(2), Some(1)の順で返る（＝一番最後の要素が一番上）
   • 空のStack::new()にextend(vec![1, 2])した後、さらにextend(vec![3])すると、pop()を3回呼んだ結果がSome(3), Some(2), Some(1)になる（＝2回のextendが正しく積み増しになっている）
6. （任意・発展）Stack<T>に Day 024 で実装済みのIntoIterator for Stack<T>（所有権ごと消費、上から下へ）を使い、let doubled: Stack<i32> = stack.into_iter().map(|x| x * 2).collect();のように「Stack → イテレータ変換 → collect()で別のStackに戻す」往復ができることを確認してください

🔍 ヒント（段階的開示）

📋 コピーimpl<T> FromIterator<T> for Stack<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        Stack {
            items: iter.into_iter().collect(),
        }
    }
}

impl<T> Extend<T> for Stack<T> {
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        self.items.extend(iter);
    }
}

✅ 模範解答

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

pub struct Stack<T> {
    items: Vec<T>,
}

impl<T> Stack<T> {
    pub fn new() -> Self {
        Stack { items: Vec::new() }
    }

    pub fn push(&mut self, item: T) {
        self.items.push(item);
    }

    pub fn pop(&mut self) -> Option<T> {
        self.items.pop()
    }

    pub fn len(&self) -> usize {
        self.items.len()
    }
}

// Day 024 で実装済みの「読むだけ」IntoIterator（今日の main / test で再利用する）
impl<'a, T> IntoIterator for &'a Stack<T> {
    type Item = &'a T;
    type IntoIter = std::iter::Rev<std::slice::Iter<'a, T>>;

    fn into_iter(self) -> Self::IntoIter {
        self.items.iter().rev()
    }
}

// Day 024 で実装済みの「消費する」IntoIterator（発展課題の往復変換で使う）
impl<T> IntoIterator for Stack<T> {
    type Item = T;
    type IntoIter = std::iter::Rev<std::vec::IntoIter<T>>;

    fn into_iter(self) -> Self::IntoIter {
        self.items.into_iter().rev()
    }
}

// ① collect() の受け皿: イテレータを「新規に」Stack<T> へ組み立てる
impl<T> FromIterator<T> for Stack<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        // Vec<T> が既に持つ FromIterator に丸投げするだけ。
        // 1, 2, 3 の順で渡されたら、Vec には [1, 2, 3] のまま入る
        // = push(1); push(2); push(3) した状態と同じ(一番上が3)。
        Stack {
            items: iter.into_iter().collect(),
        }
    }
}

// ② extend() の受け皿: 既存の self に「追記」する
impl<T> Extend<T> for Stack<T> {
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        // Vec<T> の extend も「末尾に順番通り追記する」実装なので、
        // そのまま委譲すれば push を繰り返したのと同じ結果になる。
        self.items.extend(iter);
    }
}

fn main() {
    // 1. collect() で Stack<i32> を新規に組み立てる
    let mut stack: Stack<i32> = (1..=5).collect();
    print!("collect直後 (上から): ");
    for x in &stack {
        print!("{x} ");
    }
    println!();

    // 2. extend() で追記する(上に積み増す)
    stack.extend(vec![10, 20]);
    print!("extend後 (上から): ");
    for x in &stack {
        print!("{x} ");
    }
    println!();

    // 3. (発展) Stack -> イテレータ変換 -> map -> 別の Stack へ collect() する往復
    let doubled: Stack<i32> = stack.into_iter().map(|x| x * 2).collect();
    print!("doubled (上から): ");
    for x in &doubled {
        print!("{x} ");
    }
    println!();
}

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

    #[test]
    fn collect_preserves_source_order_as_push_order() {
        let mut stack: Stack<i32> = vec![1, 2, 3].into_iter().collect();
        // 1, 2, 3 の順で push したのと同じ = 一番上(最後にpushされた)が3
        assert_eq!(stack.pop(), Some(3));
        assert_eq!(stack.pop(), Some(2));
        assert_eq!(stack.pop(), Some(1));
        assert_eq!(stack.pop(), None);
    }

    #[test]
    fn extend_appends_on_top_across_multiple_calls() {
        let mut stack: Stack<i32> = Stack::new();
        stack.extend(vec![1, 2]);
        stack.extend(vec![3]);

        // 2回の extend が正しく「積み増し」になっていること
        assert_eq!(stack.pop(), Some(3));
        assert_eq!(stack.pop(), Some(2));
        assert_eq!(stack.pop(), Some(1));
        assert_eq!(stack.pop(), None);
    }

    #[test]
    fn round_trip_through_iterator_adapter_preserves_semantics() {
        let stack: Stack<i32> = vec![1, 2, 3].into_iter().collect();
        let doubled: Stack<i32> = stack.into_iter().map(|x| x * 2).collect();

        let collected: Vec<&i32> = (&doubled).into_iter().collect();
        assert_eq!(collected, vec![&6, &4, &2]);
    }
}

$ cargo run
collect直後 (上から): 5 4 3 2 1
extend後 (上から): 20 10 5 4 3 2 1
doubled (上から): 40 20 10 8 6 4 2

$ cargo test
running 3 tests
test tests::collect_preserves_source_order_as_push_order ... ok
test tests::extend_appends_on_top_across_multiple_calls ... ok
test tests::round_trip_through_iterator_adapter_preserves_semantics ... ok

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

🪜 Step-by-Step 解説

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

IntoIterator（Day 024・出す方向）とFromIterator/Extend（今日・入れる方向）が対になっているのは偶然ではなく、Rustの標準ライブラリが「コレクション間の変換はすべて同じ語彙（イテレータ）を経由させる」という設計方針を徹底しているためです。

• Vec<T> → HashSet<T>への変換も、HashMap<K, V> → Vec<(K, V)>への変換も、すべて「IntoIteratorで取り出してFromIterator/collect()で組み立て直す」という同じパターン1つで表現できます。もしこの統一がなければ、vec_to_hashset()、hashmap_to_vec()のような変換関数を型の組み合わせの数だけ書く必要が出てきます（N個の型があればO(N²)の変換関数）
• ExtendがFromIteratorと別トレイトに分かれているのは、「新規に作る」（所有権を持たない状態から始める）と「既存のものに追記する」（既に所有権を持っている&mut selfに対する操作）が本質的に異なる操作だからです。実際、標準ライブラリのFromIterator::from_iterのデフォルト実装の多くは、内部で「空の値を作ってextend()を呼ぶ」という形でExtendに処理を委譲しています（Vec<T>の実装がまさにそうです）

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

今日の実装自体はデバッグ問題ではありませんが、collect()の型推論に関するエラーは初学者が高確率でぶつかるため、代表的な1つを紹介します。

fn main() {
    let stack = (1..=5).collect(); // ← 型注釈なし
    println!("{}", stack.len());
}

読み方: collect::<B>()の型パラメータBは、呼び出し側の文脈（変数の型注釈・関数の戻り値の型・ジェネリック引数の制約など）から逆算されます。let stack = ...のように何の型に集約したいのか手がかりが一切ない場合、コンパイラはVec<i32>なのかStack<i32>なのかHashSet<i32>なのか判断できず、エラーになります。

修正方法は2通り:

// 修正1: 変数に型注釈をつける
let stack: Stack<i32> = (1..=5).collect();

// 修正2: turbofish構文で collect() 自体に型を指定する
let stack = (1..=5).collect::<Stack<i32>>();

どちらも「Bが何かをコンパイラに教える」という点で同じです。実務では、直後に.len()を呼ぶなど型が明白な場合はエラーが出ないこともありますが、collect()を書いたら型注釈をセットで書く癖をつけておくと、このエラーで詰まる時間を減らせます。

🌐 他言語との比較

JavaのCollectorはある程度似た役割を持ちますが、「変換先の型に応じて呼び出し側がCollectors.xxx()を選ぶ」のに対し、Rustでは「変換先の型自体が変換方法（from_iter）を知っている」という点で責任の所在が逆になっています。

🏆 実務での使いどころ

• 設定ファイルやCSVをパースしてVec<Record>を得た後、業務ロジック側で扱いやすい独自コレクション型（例: OrderBook、PriceHistory）に.collect()一発で変換できる。パース処理と業務ロジック側の型が疎結合になる
• APIレスポンス（Vec<UserDto>等）を受け取った直後に.into_iter().map(User::from).collect::<UserRegistry>()のように、DTOからドメインモデルへの変換とコレクション組み立てを1つのメソッドチェーンで完結できる
• テストコードでlet queue: TaskQueue = vec![task1, task2, task3].into_iter().collect();のように、テストデータの用意が1行になり可読性が上がる。Extendを実装しておけばqueue.extend(more_tasks);で追加データの注入も自然に書ける

⚠️ よくある誤解・ミス

🚀 次のステップ

• 発展: Stack<T>にimpl<T> Extend<T> for Stack<T>を応用し、std::iter::sum()のような集約処理を自作の集約型（例えば「積み上げた合計金額を持つLedger」）に対して実装してみましょう。FromIterator/Extendの考え方は数値の集約にもそのまま応用できます
• 次回予告: 自己評価で「完全理解」または「おおむね理解」が3回連続で記録された時点で、次のテーマスマートポインタ①（Box<T>）（ヒープ確保・再帰的データ構造）に進みます

🎯 自己評価

自分の回答

気づき・メモ