Rust のイテレータは自分自身への参照を返せない

usize のようなものを返すイテレータでは気にならないのですが, 大きな String や Vec<T> を直接返すようなイテレータは, .next() を叩く度にそれをクローンするコストを払う必要があります. そのため, このような場合イテレータ自身が保持するデータへの参照を返したくなることがあります. しかし, これはできません¹. Rust のイテレータ (std::iter::Iterator) はトレイトであり, その定義は次のようになっています.

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

参照を返すためには, type Item を指定する際にその生存期間を合わせて指定する必要がありますが, いまの場合その生存期間はイテレータそのものの生存期間に等しい (かより短い) です. しかし, 上のトレイトの定義ではイテレータそのものの生存期間と生成されたアイテムの生存期間を結びつけることができません (参考). よくよく考えてみれば, もしそれが可能なら, 生成されたアイテムはいつまで生きているかわからず, いつの間にか値が書き換わっているかもしれない訳です. これはまさに生存期間および Rust の借用のルールによって禁じられるべき挙動です.

Streaming Iterator

そうは言っても参照を返したくなることがあり, それを streaming iterator と呼びます. これは .next() を叩くと自分自身が保持するデータへの参照を返すもので, let Some 構文によって for ループを代替することができます. 具体例として Lorem ipsum を無限に表示する例を挙げておきます².


/// streaming iterator となる構造体
struct Lorem {
    counter: usize,
    sentence: Vec<String>,
}

impl Lorem {
    fn new() -> Lorem {
        Lorem { counter: 3,
                sentence: vec![
                    "Lorem ipsum dolor sit amet,".to_string(),
                    "consectetur adipiscing elit,".to_string(),
                    "sed do eiusmod tempor incididunt".to_string(),
                    "ut labore et dolore magna aliqua.".to_string(),
                ], }
    }

    // `next()` を叩く度に 4 つの `&str` を順に返す.
    fn next(&mut self) -> Option<&str> {
        self.counter = (self.counter+1)%4;
        Some(&self.sentence[self.counter])
    }
}

fn main() {
    let mut lorem = Lorem::new();

    // 注意 これは無限ループです
    while let Some(sentence) = lorem.next() {
        println!("{}", sentence);
    }
}

ちなみに while let Some(item) = iter.next() { /* snip */ } 構文は普通のイテレータの場合にも for 文の代わりに使えます.

ただ, streaming iterator はやはり標準ライブラリのイテレータとは異なり, 手動で複数アイテムを取得して扱うようなことはできません. 例えば上の例で main 関数を

fn main() {
    let mut lorem = Lorem::new();

    let s1 = lorem.next().unwrap();
    let s2 = lorem.next().unwrap();

    println!("{} {}", s1, s2 );
}

としてみると, 通常のイテレータなら問題なく機能するはずですが, 今の場合コンパイラに阻まれます.

$ cargo build
   Compiling lorem v0.1.0
error[E0499]: cannot borrow `lorem` as mutable more than once at a time 
--> src/main.rs:29:14
   |
28 |     let s1 = lorem.next().unwrap();
   |              ----- first mutable borrow occurs here
29 |     let s2 = lorem.next().unwrap();
   |              ^^^^^ second mutable borrow occurs here
30 |
31 |     println!("{} {}", s1, s2 );
   |                       -- first borrow later used here
error: aborting due to previous error

つまり, streaming iterator から新しくアイテムを生成すると, それ以降, 過去に生成したアイテムにアクセスするとコンパイルエラーになります. しかしこの制限は上述のループの形で扱うならば問題にならないため, for ループを代替する形で用いる限り streaming iterator は普通のイテレータと同じ感覚で用いることができます.

ちなみに, streaming iterator を使って順列/組み合わせを生成するコードをつくってみたところ, 普通のイテレータの場合に比べて 10% 程度のコスト削減になりました (github).

streaming-iterator クレート

streaming iterator を扱う場合, streaming-iterator クレートが便利です. このクレートは .filter(), .map(), .take() といった標準ライブラリのイテレータが備えているメソッド (の一部) を自動的に実装してくれます. なおこのクレートでは streaming iterator を .next() メソッドではなく, それを分割した .advance() メソッドと .get() メソッドに分けて定義しています.

trait streaming_iterator::StreamingIterator {
    type Item: ?Sized;
    fn advance(&mut self);
    fn get(&self) -> Option<&Self::Item>;
}

イテレータ自身以外が所有するデータへの参照を返すことはできます. Vec<T> の要素に .iter() メソッドを通じてアクセスする場合など. ↩
この例の場合, こんなことせずとも Vec<String> にインデックスアクセスすればよいのですが, 他に簡単な例が思いつかなかったので... ↩