Okey dokes. So about that LinkedList:
A bird's-eye view of iteration code in std::linked_list
Here's a bird's-eye snapshot of all or most of the code involved in iterating through linked lists in the standard library (ignoring unstable features and #[inline]
attributes):
pub struct Iter<'a, T: 'a> {
head: Option<Shared<Node<T>>>,
tail: Option<Shared<Node<T>>>,
len: usize,
marker: PhantomData<&'a Node<T>>,
}
impl<'a, T> Clone for Iter<'a, T> {
fn clone(&self) -> Self {
Iter { ..*self }
}
}
pub struct IterMut<'a, T: 'a> {
list: &'a mut LinkedList<T>,
head: Option<Shared<Node<T>>>,
tail: Option<Shared<Node<T>>>,
len: usize,
}
#[derive(Clone)]
pub struct IntoIter<T> {
list: LinkedList<T>,
}
impl<'a, T> Iterator for Iter<'a, T> { /* 20 lines... */ }
impl<'a, T> DoubleEndedIterator for Iter<'a, T> { /* 13 lines ... */ }
impl<'a, T> ExactSizeIterator for Iter<'a, T> {}
impl<'a, T> Iterator for IterMut<'a, T> { /* 20 lines ... */ }
impl<'a, T> DoubleEndedIterator for IterMut<'a, T> { /* 13 lines ... */ }
impl<'a, T> ExactSizeIterator for IterMut<'a, T> {}
impl<T> Iterator for IntoIter<T> {
type Item = T;
fn next(&mut self) -> Option<T> {
self.list.pop_front()
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.list.len, Some(self.list.len))
}
}
impl<T> DoubleEndedIterator for IntoIter<T> {
fn next_back(&mut self) -> Option<T> {
self.list.pop_back()
}
}
impl<T> ExactSizeIterator for IntoIter<T> {}
impl<T> IntoIterator for LinkedList<T> {
type Item = T;
type IntoIter = IntoIter<T>;
fn into_iter(self) -> IntoIter<T> {
IntoIter { list: self }
}
}
impl<'a, T> IntoIterator for &'a LinkedList<T> {
type Item = &'a T;
type IntoIter = Iter<'a, T>;
fn into_iter(self) -> Iter<'a, T> {
self.iter()
}
}
impl<'a, T> IntoIterator for &'a mut LinkedList<T> {
type Item = &'a mut T;
type IntoIter = IterMut<'a, T>;
fn into_iter(self) -> IterMut<'a, T> {
self.iter_mut()
}
}
That's a lot of code! Can we focus on what's important?
In order for for x in my_list { ... }
to work, this is the minimum that would work:
pub struct IntoIter<T> {
list: LinkedList<T>,
}
impl<T> Iterator for IntoIter<T> {
type Item = T;
fn next(&mut self) -> Option<T> {
self.list.pop_front()
}
}
impl<T> IntoIterator for LinkedList<T> {
type Item = T;
type IntoIter = IntoIter<T>;
fn into_iter(self) -> IntoIter<T> {
IntoIter { list: self }
}
}
type IntoIter = IntoIter<T>
? What?
This line defines the associated type IntoIterator::IntoIter
to be our own iterator, which "just so happens" to also be called IntoIter
(by convention)
The contents of IntoIter:
One can see that LinkedList's IntoIter contains a LinkedList. Funny, right? However, this is not true in general for all data structures!
More generally, IntoIter
should hold the data in whatever form that will allow it to easily consume elements one-by-one. It just so happens that LinkedList
is already a suitable format for iteration! (since it has O(1) retrieval and removal of the first element, via pop_front()
).
What's all that other stuff do, then?
Some of it adds more functionality to the iterator:
Clone: IntoIter
had #[derive(Clone)]
. This is nice because it allows users to save the current state of an iterator. It will also allow the user to call .cycle()
on it.
DoubleEndedIterator: Implementing this on your iterator allows your iterator to be reversed with .rev()
. It requires manually implementing a next_back()
method:
impl<T> DoubleEndedIterator for IntoIter<T> {
fn next_back(&mut self) -> Option<T> {
self.list.pop_back()
}
}
size_hint: This is a method in Iterator which you can optionally implement if you are able to provide lower/upper bounds on the number of elements. It helps give methods like <Vec as FromIterator>::from_iter
an idea of how much memory to allocate, for a small performance boost.
// impl Iterator for IntoIter<T> { ...
fn size_hint(&self) -> (usize, Option<usize>) {
(self.list.len, Some(self.list.len))
}
// }
ExactSizeIterator: This expands on size_hint
by making an explicit promise that the lower bound and upper bound are equal. By providing a (trivial) impl of this trait, users will be able to call .len()
on the iterator:
impl<T> ExactSizeIterator for IntoIter<T> {}
That's it for IntoIter
.
Iter/IterMut
The rest has to do with iter
and iter_mut
:
Iter
and IterMut
are the return types of iter
and iter_mut
. Like IntoIter
, these are iterators, but they borrow or mutate the items instead of consuming them. These are not part of any standard interface, but are often quite useful if they can be provided.
There are also two other IntoIterator
impls, for &LinkedList
and &mut LinkedList
, which return Iter
and IterMut
. These are simply for convenience; they allow users to write for x in &list
as shorthand for for x in list.iter()
.
What's with all the unsafe code?
Right. Iter
and IterMut
have a bunch of unsafe
in their implementation.
This is nothing inherent to iteration in general. Rather, it's like I said: Data structures are a pretty hardcore topic in rust.
Especially linked lists. (seriously, go read that. It's an emotional roller coaster)