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.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
As you can see it calls
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
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.
Iterator implementation of
Skip just calls
nth internally, so both operations have the same complexity:
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.
I am wrapping the result of
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
You want to overload
nth for your iterator.
Skip will use that to skip the number of elements it was told to skip:
There should be no need to override that one -- it just constructs a type, no need to change what it does.
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.