The standard library is so full of optimizations that it’s sometimes hard to spot the relevant parts.
This applies especially to the Vec::from_iter
implementation. Essentially it boils down to it2.collect()
being implemented (mostly) by one call to it2.for_each(…)
. Then, for_each
is a story of its own… there is a default implementation in terms of .next()
for every iterator that doesn’t override it, but Filter
does because that results in slightly more optimal code.
Either way, if you interpret it2.collect()
to be essentially implemented either as
let mut coll = vec![];
for item in it2 {
coll.push(item);
}
or
let mut coll = vec![];
it2.for_each(|item| coll.push(item);
and it2
is of type Filter
, we are close to seeing the place where the closure |e| e % 2 == 0
closure is called. The for
loop uses .next()
calls in a loop, the for_each
is its own method, either way we can look at the implementation of Iterator
for Filter
and try to spot the call to the closure.
The Filter
type by the way simply bundles up the inner iterator and the predicate closure
pub struct Filter<I, P> {
iter: I,
predicate: P,
}
And the next
method looks like
fn next(&mut self) -> Option<I::Item> {
self.iter.find(&mut self.predicate)
}
Well… that uses find
now, doesn’t it? But if it didn’t: this code is mostly equivalent to something like
fn next(&mut self) -> Option<I::Item> {
while let Some(item) = self.iter.next() {
if (self.predicate)(&item) {
return item; // stops the loop, returns from the function
} // otherwise, continue with the next
}
// in case that no more matching items are found:
None
}
For the actual find
implementation: impl Iterator
for Filter
does not define find
itself, so the default is used. It calls back to a call to a method called try_fold
… I mean, if you want, go study it’s signature, I’m trying to go too deep into detail here, which is why many code examples will merely paraphrase the gist/implementation idea of stuff, not literally what the standard library uses. try_fold
is a lot like a for_each
method, but additionally with the possibility of passing along owned state, and also with the possibility of “failure”/early-termination (which is crucial for implementing find
). Fun-fact: try_fold
is so general that you could even implement .next()
in terms of try_fold
, too. Now, as you can see in the linked implementation, Filter
also implements try_fold
itself as well as fold
, but unlike what I claimed above, it actually does not directly override for_each
, since its so similar to fold
. So for_each
has a default implementation in terms of fold
that is used.
To give a simplified view of how a for_each
implementation of Filter
could look like and what its benefits are: This is a possible for_each
implementation, quite similar to the actual try_fold
implementation:
fn for_each<F>(self, f: F)
where
Self: Sized,
F: FnMut(Self::Item),
{
self.iter.for_each(|item| if self.predicate(&item) {
f(item)
});
}
Compare this to using a default-implementation for for_each
which would use next
in a loop
fn for_each<F>(self, f: F)
where
Self: Sized,
F: FnMut(Self::Item),
{
while let Some(item) = self.next() {
f(item);
}
}
Now, with the .next()
implementation above, which itself is a loop, too, using this default for_each
would result in a loop inside a loop. The manually implemented implementation on the other hand is simply an if statement inside a loop, the latter is slightly more straightforward, and could be thus more performant. More relevant even: The if-statement-in-a-loop approach only loops a single time through the inner iterator without any breaks, whereas the .find
-based implementation of next
called in a loop will stop and re-start iteration on the inner iterator a lot of times. There are a few iterator types (e.g. Chain
, which needs to check which half of the chain it’s in for every time iteration is paused and resumed) where looping in one go is significantly better than calling next
(or try_fold
) a bunch of times in a row, and that’s a main reason why implementing more than just .next
for the Iterator for Filter<…>
implementation is beneficial for performance.