イテレータ

Essential
最終更新: タグ: Rust, Iterator

前提知識

Rustのすべてのforループは内部でひとつのメソッドを呼び出している：nextだ。**Iterator**トレイトはこの最小限のインターフェイスを捉えており、標準ライブラリで値のシーケンスを生成するほぼすべてのものがこれを実装している。

Iterator トレイト

このトレイトに必須のメソッドはひとつだ：

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

nextは各要素に対してSome(item)を返し、シーケンスが尽きるとNoneを返す。type Itemはイテレータが生成するものを表す関連型だ。

Iteratorを手で実装することはほとんどないが、シグネチャを見るとforの仕組みが明快になる：

let mut iter = vec![10, 20, 30].into_iter();
assert_eq!(iter.next(), Some(10));
assert_eq!(iter.next(), Some(20));
assert_eq!(iter.next(), Some(30));
assert_eq!(iter.next(), None);

forループはまさにこの呼び出しシーケンスにデシュガーされる。

アダプター — 遅延変換

アダプター（adapter）は既存のイテレータをラップして新しいイテレータを返す。アダプターは遅延評価だ：コンシューマーによって駆動されるまで何も実行されない：

let v = vec![1, 2, 3, 4, 5];

// まだ何も実行されない — パイプラインを記述しているだけ
let pipeline = v.iter()
    .filter(|&&x| x % 2 == 0)
    .map(|&x| x * 10);

よく使われるアダプター：

アダプター生成するもの
.map(f)fで変換された要素
.filter(pred)predがtrueの要素
.take(n)最初のn要素まで
.skip(n)最初のn要素を飛ばした残り
.chain(other)selfの要素に続いてotherの要素
.enumerate()(インデックス, 要素)のペア
.zip(other)(self の要素, other の要素)のペア
.flat_map(f)fが返す各サブイテレータの要素
.peekable()消費せずに次の要素を覗けるイテレータ

アダプターは遅延評価なので、いくつ連鎖させてもヒープへの中間アロケーションは発生しない。

コンシューマー — パイプラインを駆動する

コンシューマー（consumer）はイテレータから要素を引き出し、最終的な結果を生成する：

let doubled_evens: Vec<i32> = (1..=10)
    .filter(|x| x % 2 == 0)
    .map(|x| x * 2)
    .collect();
// [4, 8, 12, 16, 20]

よく使われるコンシューマー：

コンシューマー返すもの
.collect::<C>()C: FromIteratorを実装する任意のコレクション
.sum::<T>()すべての要素の合計
.product::<T>()すべての要素の積
.fold(init, f)各要素にfを適用して構築した単一の値
.for_each(f)各要素にfを実行する。()を返す
.count()要素の数
.any(pred) / .all(pred)短絡評価するブールテスト
.find(pred)最初にマッチした要素（Optionとして）
.position(pred)最初にマッチした要素のインデックス（Option<usize>として）
.max() / .min()最大/最小の要素（Optionとして）

foldは最も汎用的なコンシューマーで、sum・product・さらにはcollectさえも内包する：

let product = (1..=5).fold(1u64, |acc, x| acc * x);
assert_eq!(product, 120);

ゼロコスト抽象化

Rustコンパイラはイテレータチェーンをインライン化し最適化するため、等価な手書きループと同じ機械語を生成する。パイプラインを書いてもパフォーマンスのトレードオフはない：

// パイプライン
let sum: i32 = v.iter().filter(|&&x| x > 0).map(|&x| x * 2).sum();

// 手動ループ — リリース最適化後は同じアセンブリ
let mut sum = 0i32;
for &x in &v {
    if x > 0 { sum += x * 2; }
}

独自のイテレータを書く

nextを実装した型はすべて、トレイトのデフォルト実装を通じてアダプターとコンシューマーのメソッドを無料で得られる：

struct Countdown(u32);

impl Iterator for Countdown {
    type Item = u32;

    fn next(&mut self) -> Option<Self::Item> {
        if self.0 == 0 {
            None
        } else {
            self.0 -= 1;
            Some(self.0 + 1)
        }
    }
}

let v: Vec<u32> = Countdown(3).collect();
assert_eq!(v, [3, 2, 1]);

nextだけを実装すれば、.map・.filter・.collectその他すべてが使えるようになる。