What is an iterator in Rust

What is an iterator in Rust?
I'm confused. I come from C++ and there iterator is a "something" that points to something. One thing at at time, that is I cannot point at the same time to more than one object with an iterator. Is it the same in rust?

An iterator in Rust is any data structure which implements the Iterator trait. The implementation of the trait consist of a single method (fn next(&mut self) -> Option<Self::Item>), which gets the next item of the iterator (if one exists) and advances it to the next item. Structs which implement the trait can be used with for loops, and they automatically implement a lot of utility methods like map, filter, count and so on, which you'd probably find from std::algorithms in C++.

My understanding is that in C++ iterators are basically fancy pointers that point to an item within a container. In Rust an iterator is essentially just a function which produces elements in a sequence. The advantage of this approach is that you can implement Iterator for basically anything, and efficiently generate items on the fly. For example, ranges (like [0..100]) can be used as iterators without having to actually allocate a 100-item vector.

6 Likes

Correct

So it is a range...

It is not a range. It can be, but it doesn't have to be.

Here is an example of an iterator I just wrote. The next function always returns some data, so the iterator is infinitely long - which is not an issue, because elements are only generated when necessary.

So it is generator...
OK, I get it. In rust it is basically more general, abstract concept.

1 Like

C++ is really an odd duck when it comes to iterators, so you may have a bit to unlearn.

C++ is based on C, and in C there is no such thing as an iterator. When you want to iterate over something, you write a loop. It usually looks something like this:

for (c = begin(); c != end(); ++c) {...}

c could be a pointer, but it might also be an integer. Basically it represents a position in a range. We could call it a cursor.

Cursors are in a sense a lower-level abstraction than iterators. You can use a cursor to iterate over a range, but that's not all you can do. You can advance a cursor by several steps at a time, skipping some values, or you can follow (dereference) the cursor several times without advancing it, processing the same value more than once. Cursors may also be moved backward as well as forward (C++ calls these "bidirectional iterators"). Some cursors can move instantly to any other position in the range without moving through the intermediate positions (C++ calls these "random access iterators"). All these things are reasonable to do in a cursor-based API, but they don't really have anything to do with iteration.

Rust's iterators are firmly grounded in iteration. An iterator is just something that produces items from a sequence one at a time. The sequence can be anything, like "all the odd numbers from 1 to 1000 in increasing order" or "ten million random strings" or "just the number 0.04, repeated forever". But the idea of an iterator is an object that can produce things from a sequence one at a time.

That doesn't mean you can't do a lot of the same stuff with iterators that you can with cursors! For instance, you can skip an item in the sequence by calling next() without using the value it returns, or you can skip a bunch of items by using nth(10). But this is still fundamentally iteration, so calling nth(10) should have the same effect as calling next() 11 times and just discarding the first 10 values. It's not the same as doing i += 10 for a "random access iterator" in C++. Random access falls outside of Rust's concept of iteration.

Rust iterators are more limited than cursors. This is a common pitfall for people coming from C++ because in C++ you always use the iterator API for abstracting over collections, and Rust iterators just don't provide the same control. Often this happens because you're trying to go too abstract too soon. For instance, in C++ you might use a random access iterator where in Rust you should just use a slice, as has come up in your other thread.

10 Likes

It should be noted that it's not just Rust which has iterators like this. Basically every modern language in use except for C++ implements iterators in a similar fashion.

10 Likes

CĀ„ Java kotlin have exactly same as cpp

What do you mean by that? All 3 of them use a next "generator" method (or property) just like Rust does. The iterators in those languages are not just pointers, and there is no requirement that data must be contiguous in memory. Truth be told, I can't name any similarities between C++ and them, except the fact that all can be used for iteration.

4 Likes

I get the idea you are presenting there. But I have never in four decades seen a C 'for' loop written like that.

The way I look at it C only has one array, that is all memory available to your program. So called 'arrays' are just different views of that bigger memory array. Which you are free to do what you like with, inside or outside, as you see fit.

Also, in all of programming there are only three things: Sequence, selection and iteration.

Sequence: Do this, do that, do the other. In that order.

Selection: Do this or do that. Depending on some condition.

Iteration: Do this repeatedly and stop at some condition.

Where 'this', 'that', 'other' can recursively be sequence, selection and iteration.

That fully defines what an iterator can be.

Of course different languages have different ideas as to how to represent these three things.

That's a C++ idiom.

2 Likes

What I meant by that is that C#, Java and Kotlin has exactly the same notion of iterator as C++.
So now your list becomes:
javascript
python
ruby.

Now I get it why range is called iterator in rust.

Yes, I get it. That's exactly what I meant when I said, it is called identical like in C++ but means something different.

Absolutely not.
In those three languages, the next method merely advances iterator to the next element.
Rust has named a range an iterator. As simple as that.

That's exactly what the next() method does on a Rust iterator as well?

I believe that this is not the case. I may be wrong of course. In rust next is a method of a struct/trait that has already all (or infinite) elements accessed. That is, before we can use next we have to first convert the entire collection to iter, like vec.iter() and only then we can use the next so we actually using next on the object that was converted to iter not on the vec itself. In C++ the iterator is just a "cursor" if you like to iterate over vec without converting that vec to anything.

The return value of vec.iter() is also just a sort of cursor. It merely contains a reference into the vector, as well as an index, and calling .next() will increment the index and return the current element.

It is also possible to convert a vector into an iterator, but this is done with vec.into_iter(). The difference is that vec.iter() is an iterator of references into the original vector, whereas vec.into_iter() is an iterator that moves ownership out from the vector.

You see, that's the bit that is poorly named. How can a vector be converted into a "cursor"? I know from the discussion here what is happening but the naming convention in rust is simply confusing.

The vector is converted into an iterator, not a cursor. I use "cursor" only as an analogy.