Implementing Iterator and IntoIterator in Rust
Tags: rust, beginners, tutorial
Published: 2023-04-25 23:13:22

Iterators are a powerful tool that allow for efficient iteration over data structures, and they are implemented in many programming languages - including Rust. However, Rust's unique ownership system gives rise to interesting differences in how iterators are implemented and used. In this article, we will explore these differences and delve into Rust's features by creating and implementing the most commonly used iterator traits - `Iterator` and `IntoIterator`.
<hr>

Imagine you have a structure like this:
```rust
pub struct Todos {
	pub list: Vec<Todo>,
}
```

The struct above is a `Vec<Todo>`, which is a vector of `Todos`, which have this structure:
```rust
pub struct Todo {
	pub message: String,
	pub done: bool,
}
```

If we wish to iterate over each `Todo` in this `Vec`, we could simply use its `list` property and iterate over its items, right?
But what if we wanted to iterate over `Todos` itself, without exposing its internal properties?
*That's where things start to get interesting...*


## What is an iterator?
An iterator is a pattern that allows you to go through each element in an *iterable* sequentially. Iterators are very useful in loops, allowing you to iterate over items in a neat way.
Let's see a loop without and with iterators, in Javascript:
```js
let array = [1, 2, 3, 4];

// without iterators
for (var i = 0; i < array.length; i++) {
    console.log(array[i]);
}

// with iterators; "item" is the iterator
for (item of array) {
	console.log(item)
}
```

As you can see, they are present in a lot of other languages, as Javascript, Python and so on.

## Iterators in Rust
In Rust, similarly with languages such as Python, iterators are *lazy*. It means that they are effectless unless you iterate over them (a.k.a consume them).

```rust
let numbers = vec![1, 2, 3];
let numbers_iter = numbers.iter();
```

The code above creates an iterator - and does *nothing* with it.
To use the iterator, we should create a for loop, for example as it follows:
```rust
let numbers = vec![1, 2, 3];
let numbers_iter = numbers.iter();

for number in numbers {
	println!("{}", number)
}
```

There are also other ways which we can use to create iterators. For example, every time we use `map()` in Rust we are creating an iterator.


### Iterators vs Iterables
A vector, as seen before, is an iterable. 
It means that we can iterate over them; but more precisely, it means that *we can use a Vec to create an Iterator*. This is the definition of an iterable - some object with which we can create an Iterator. For example, a `Vec<u32>` can produce an iterator - **but is not an iterator itself**.

### Creating an Iterator
Okay, let's go back to our `Todos` struct and see how could we create a way to iterate over its items.
`Todos` has a field `list`, which is a `Vec<Todos>`. 
In Rust, Iterator is a *trait* which has some methods in it, such as `next()`, which is responsible for taking the next element of the collection and returning it, or returning `None` if we've already reached the end of the collection. Its implemention looks roughly like this:
```rust
trait Iterator {
    type Item;

    fn next(&mut self) -> Option<Self::Item>;
}
```

Fine. We could, then, create a way to iterate over the elements of the `list` field of our `Todos`, writing a custom `next()` function. The logic for this is simple - we could do something like this, in pseudocode:
```rust	
function next() {
	if index < list.len() {
		let todo = Some(list[index])
		self.index += 1
		return todo	
	} else {
		return None
	}
}
```
In the logic above, we check for the index of the element and return it, given its index is less than the list length.
*But we have a problem here.* Where to store `index`?

### Storing state
That's when the difference between an iterator and an iterable comes into hand. 
Translating the pseudocode above, one could implement the `next()` function in `Todos` like this, implementing a method from the `Iterator` trait, 
```rust
impl<'a> Iterator for Todos {
    type Item = &'a Todo;
    fn next(&mut self) -> Option<Self::Item> {
        if self.index < self.list.len() {
            let result = Some(&self.list[self.index]);
            self.index += 1;
            result
        } else {
            None
        }
    }
}
```

**But it would require us to change the structure of our `Todos`**: we would need to add a `index` field in it to use every time we call `next()` - which is, every time we iterate over its items through an iterator.

```rust
pub struct Todos {
	pub list: Vec<Todo>,
	index: usize,
}
```

In this logic, we would modify the constructor function in order to always create the struct with `index: 0`.
```rust
pub fn new(list: Vec<Todo>) -> Self {
	Todos { list, index: 0 }
}
```

However, this approach simply *does not feel right...* 
Storing an index field in your *struct* is not ideal; the index is used for storing the current state in an iterator, so it should be part of the *iterator*, not of the *struct*. This is why we are going to create an iterator type - which is going to store the index property - and implement the `Iterator` trait for this type. 

> **The iterator is a type that abstracts the logic of iterating over an iterable; it also stores the current state of iteration, such as the index property.**


# `TodoIterator`
Let's create our iterator then!
First of all, we need to create the type of the iterator:
```rust
struct TodosIterator<'a> {
    todos: &'a Todos,
    index: usize,
}
```

**Note the lifetime annotations here.**
`TodosIterator` has a field `todos`, which *references* a `Todos`. As we are dealing with a *reference*, we need to ensure that this field points to something valid - and here lifetime parameters come at hand. The struct `TodosIterator` is generic over this lifetime, `'a'`.
Basically, we are using this notation to specify that the `todos` field of the iterator needs to have *the same lifetime* as the data it is pointing to. This way, we ensure that it cannot reference a `Todos` struct that has been dropped.

## Implementing Iterator for `TodosIterator`

```rust
// ps: it could be done using .get() as well, however I wanted to use this approach to make it a bit more clear how Options are returned in this context 
impl<'a> Iterator for TodosIterator<'a> {
	type Item = &'a Todo;
	
	fn next(&mut self) -> Option<Self::Item> {
		if self.index < self.todos.list.len() {
			let result = Some(&self.todos.list[self.index]);
			self.index += 1;
			result
		} else {
			None
		}
	}
}
```

*Now*, we are doing it right.
In the implementation of this trait, we specify the same lifetime used for the struct. It means that **the implementation is tied to the lifetime of the struct** - which is necessary because we are returning a reference in the `next()` method.
### How to use this iterator?
Now we have already created the `TodoIterator` struct as well as implemented the `Iterator` trait for this struct, how do we use it to iterate over `Todos`?
The answer lies on the `iter()` method. This method takes a reference of our `Todos` and uses it to create an iterator, which we can use to iterate!

```rust
impl Todos {
    pub fn iter(&self) -> TodosIterator {
        TodosIterator {
            todos: self,
            index: 0,
        }
    }
}

// Now we can iterate:
for todo in todos.iter() {
    println!("{}", todo); // each todo is a &Todo, and is immutable
}
```


## IntoIterator
IntoIterator is a bit different from the `Iterator` trait. Its single method, `into_iter()`, returns an iterator over some data and **makes it possible to iterate over data in a generic way, regardless of its actual type**. It happens because *all types that implement `IntoIterator` can be converted into an iterator.* 

Let's understand its implementation:
```rust
pub trait IntoIterator {
    type Item;
    type IntoIter: Iterator<Item = Self::Item>;

    fn into_iter(self) -> Self::IntoIter;
}
```

Some important points here:
1 - The `Item` type parameter is the type of the elements that the iterator will yield.
2 - The `IntoIter` type parameter is the type of the iterator that will be returned by the `into_iter` method. **This type must implement the `Iterator` trait, and the type of its `Item` must be the same as the `Item` of `IntoIterator`.**
3 - The `into_iter` method takes `self` as an argument, meaning **it consumes the original object** and returns an iterator over its elements.

Ok, how to implement it?
You may think we could *reuse* the `TodosIterator` - however, we can't since it takes a `&Todos`, and we need to *take ownership* of the iterable. So let's create another iterator that does it:
```rust
pub struct TodosIntoIterator {
	todos: Todos
}
```
The difference between `TodosIntoIterator` and `TodosIterator` is that here we are not using a _reference_, but taking ownership and returning each item itself - that why we also don't need the lifetime annotations anymore. And also there's no index to keep the state, we soon are going to see why.

Following the definition of the trait `IntoIterator`, we can implement it for `Todos`:
```rust
impl IntoIterator for Todos {
    type Item = Todo;
    type IntoIter = TodosIntoIterator;

    fn into_iter(self) -> TodosIntoIterator {
        TodosIntoIterator { todos: self }
    }
}
```

However, before doing it, we need to implement `Iterator` for `TodosIntoIterator` (remember the type parameters?) to describe how we are going to iterate over it. 

```rust
impl Iterator for TodosIntoIterator {
    type Item = Todo;

    fn next(&mut self) -> Option<Self::Item> {
        if self.todos.list.len() == 0 {
            return None;
        }
        let result = self.todos.list.remove(0);
        Some(result)
    }
}
```
This implementation is a bit different from what we've done for `TodosIterator`. We are taking advantage of the `remove()` method that exists for `Vec`s in Rust. This method removes the item at the position `n` and returns it to us, giving the ownership (which is necessary to return a `Todo` instead of a `&Todo`). Due to how this method works, we can always use "0" to return the first element, instead of storing a state and increasing it sequentially.
Using `remove` also guarantees that we are going to yield each value exactly once while also not keeping values already returned in the state of the iterator.


And now, we are done! These two implementations make it possible for us to iterate over a `Todos` in two different ways:
- By reference (&Todos)
```rust
for todo in todo_list.iter() {
    println!("{}", todo);// todo is a &Todo
}

// we can reuse todo_list, since it's not consumed
```

- Taking ownership:
```rust
for todo in todo_list {
    println!("{}", todo); // todo is a Todo
}

// we cannot reuse todo_list, since the for loop consumes it
```