Iterator::nth doesn't compose well · Issue #60395 · rust-lang/rust (original) (raw)

Iterators like iter::{Flatten, FlatMap, Chain} that chain multiple iterators together aren't able to implement Iterator::nth in terms of the nth method on their inner iterators, because when nth returns None, there's no way to know how many elements are "left".

This can lead to surprisingly bad performance when the inner iterator has an efficient nth implementation. For example, (0..100_000).chain(0..100_000).nth(50_000) has O(n) performance, even though it never reaches the second iterator.

I don't really know if this is worth fixing, but if it is, a way to fix it could be to add a method similar to nth to Iterator that returns Result<Self::Item, usize>. The Err case represents the "remaining" n (there's probably a better way to phrase that).

I don't have any interesting benchmarks, but I can confirm that implementing what I've temporarily called try_nth for ops::Range and iter::Chain makes (0..100_000).chain(0..100_000).nth(50_000) run in constant time. So returning Result<Self::Item, usize> indeed composes better. But again, this may not be worth fixing. 🙂