How to write a Rust function that takes an iterator?
I'd like to write a function that accepts an iterator and returns the results of some operations on it. Specifically, I'm trying to iterate over the values of a HashMap
:
use std::collections::HashMap;
fn find_min<'a>(vals: Iterator<Item=&'a u32>) -> Option<&'a u32> {
vals.min()
}
fn main() {
let mut map = HashMap::new();
map.insert("zero", 0u32);
map.insert("one", 1u32);
println!("Min value {:?}", find_min(map.values()));
}
But alas:
error: the `min` method cannot be invoked on a trait object
--> src/main.rs:4:10
|
4 | vals.min()
| ^^^
error[E0277]: the trait bound `std::iter::Iterator<Item=&'a u32> + 'static: std::marker::Sized` is not satisfied
--> src/main.rs:3:17
|
3 | fn find_min<'a>(vals: Iterator<Item = &'a u32>) -> Option<&'a u32> {
| ^^^^ `std::iter::Iterator<Item=&'a u32> + 'static` does not have a constant size known at compile-time
|
= help: the trait `std::marker::Sized` is not implemented for `std::iter::Iterator<Item=&'a u32> + 'static`
= note: all local variables must have a statically known size
error[E0308]: mismatched types
--> src/main.rs:11:41
|
11 | println!("Min value {:?}", find_min(map.values()));
| ^^^^^^^^^^^^ expected trait std::iter::Iterator, found struct `std::collections::hash_map::Values`
|
= note: expected type `std::iter::Iterator<Item=&u32> + 'static`
found type `std::collections::hash_map::Values<'_, &str, u32>`
I get the same error if I try to pass by reference; if I use a Box
, I get lifetime errors.
You want to use generics here:
fn find_min<'a, I>(vals: I) -> Option<&'a u32>
where
I: Iterator<Item = &'a u32>,
{
vals.min()
}
Traits can be used in two ways: as bounds on type parameters and as trait objects. The book The Rust Programming Language has a chapter on traits and a chapter on trait objects that explain these two use cases.
Additionally, you often want to take something that implements IntoIterator
as this can make the code calling your function nicer:
fn find_min<'a, I>(vals: I) -> Option<&'a u32>
where
I: IntoIterator<Item = &'a u32>,
{
vals.into_iter().min()
}
Since Rust 1.26 impl Trait are available. A less verbose version.
use std::collections::HashMap;
fn find_min<'a>(vals: impl Iterator<Item = &'a u32>) -> Option<&'a u32> {
vals.min()
}
fn main() {
let mut map = HashMap::new();
map.insert("zero", 0u32);
map.insert("one", 1u32);
println!("Min value {:?}", find_min(map.values()));
}
playground
This behaviour is a little unintuitive from those with a Python background rather than, say, a C++ background, so let me clarify a little.
In Rust, values are conceptually stored inside the name that binds them. Thus, if you write
let mut x = Foo { t: 10 };
let mut y = x;
x.t = 999;
y.t
will still be 10
.
So when you write
let x: Iterator<Item=&'a u32>;
(or the same in the function parameter list), Rust needs to allocate enough space for any value of type Iterator<Item=&'a u32>
. Even if this was possible, it wouldn't be efficient.
So what Rust does instead is offer you the option to
Put the value on the heap, eg. with
Box
, which gives Python-style semantics. Then you can take generically with&mut Iterator<Item=&'a u32>
.Specialize each function invocation for each possible type to satisfy the bound. This is more flexible, since a trait reference is a possible specialization, and gives the compiler more opportunities for specialization, but means you can't have dynamic dispatch (where the type can vary dependent on runtime parameters).