I would like to write an iterator for objects that implement a trait that allows accessing items by index. Something like this:
trait Collection {
fn get_item(&self, index: usize) -> &Item;
fn get_item_mut(&mut self, index: usize) -> &mut Item;
}
I know how to implement next()
function for both Iter
and IterMut
. My question is which other Iterator
methods do I need to implement to make the iterators as efficient as possible. What I mean by this is that for example nth()
goes directly to the item, not calling next()
until it reaches it. I'd like to know the minimum amount of functions I need to implement to make it work as fast as a slice iterator.
I've googled about this but can't find anything concrete on this topic.
On nightly, you can implement advance_by()
. This will give you an efficient nth()
for free, as well as other code that uses it in the standard library.
On stable, you need to implement nth()
. And of course, ExactSizeIterator
and size_hint()
. For extra bit of performance you can also implement TrustedLen
on nightly, allowing e.g. collect::<Vec<_>>()
to take advantage of the fact that the amount of items yielded is guaranteed.
Unfortunately, you can never be as efficient as slice iterators, because they implement various std-private traits (e.g. TrustedRandomAccess
) and libstd uses those traits with various specializations to make them more efficient in various situations.