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.