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?
Edit 2: So in short, if you can't just rely on slice's implementation, implement Iterator as described here: std::iter - Rust and implement more than just the next operation if your data structure allows for more efficient access.
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.