Is `Iterator::skip()` optimized for struct like `Vec::Iter` (ie. O(1)). Is it possible to do the same for user-defined types?

In C++ there are random_access_iterator who can skip N elements (forward and backward) in constant time. I tried to search for similar concept in Rust without success.

For a type like Vec, vec.iter().nth(N) and vec.iter.skip(N) should be O(1). Is this guaranteed? If I create a user-defined type, can I get such guarantee? How do I get it? Do I need to implement some traits?

I believe it is O(1), yes. As far as I can tell, Vec does not implement iteration itself, but relies on the Iterator implementation of slices. This is the slice implementation of nth: https://github.com/rust-lang/rust/blob/1.45.0/src/libcore/slice/mod.rs#L3324
As you can see it calls post_inc_start: https://github.com/rust-lang/rust/blob/1.45.0/src/libcore/slice/mod.rs#L3253
This method just adds an offset to a pointer, which is O(1).
If your user defined type can dereference to a slice, you don't need to implement Iterator yourself, just take advantage of the implementation on slices. If you need to implement Iterator yourself, this seems to be the default implementation for nth: https://github.com/rust-lang/rust/blob/1.45.0/src/libcore/iter/traits/iterator.rs#L335
So yes, in this case it would be O(n) and you need to overwrite the default implementation if your data structure allows for more efficient access.

Edit: the Iterator implementation of Skip just calls nth internally, so both operations have the same complexity: https://github.com/rust-lang/rust/blob/1.45.0/src/libcore/iter/adapters/mod.rs#L2007

Edit 2: So in short, if you can't just rely on slice's implementation, implement Iterator as described here: https://doc.rust-lang.org/std/iter/index.html#implementing-iterator and implement more than just the next operation if your data structure allows for more efficient access.

3 Likes

I am wrapping the result of Vec::iter() and Vec::iter().rev(), so I can't rely on Slice implementation of iterator. Thanks for the detailed explanation. I will re-implement (by forwarding it) the nth() and skip() functions.

You want to overload nth for your iterator. Skip will use that to skip the number of elements it was told to skip: https://doc.rust-lang.org/src/core/iter/adapters/mod.rs.html#2007-2015

There should be no need to override that one -- it just constructs a type, no need to change what it does.

2 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.