Как написать функцию Rust, которая принимает итератор?

Я хотел бы написать функцию, которая принимает итератор и возвращает результаты некоторых операций над ним. В частности, я пытаюсь выполнить итерацию значений 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()));
}

Но увы:

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>`

Я получаю ту же ошибку, если попытаюсь пройти по ссылке; если я использую Box, я получаю ошибки времени жизни.

Ответы

Ответ 1

Вы хотите использовать дженерики здесь:

fn find_min<'a, I>(vals: I) -> Option<&'a u32>
where
    I: Iterator<Item = &'a u32>,
{
    vals.min()
}

Черты могут использоваться двумя способами: как границы параметров типа и как объекты черт. В книге The Rust Programming Language есть глава о чертах и глава об объектах черт, которые объясняют эти два варианта использования.

Кроме того, вы часто хотите взять что-то, что реализует IntoIterator как это может сделать код, вызывающий вашу функцию лучше:

fn find_min<'a, I>(vals: I) -> Option<&'a u32>
where
    I: IntoIterator<Item = &'a u32>,
{
    vals.into_iter().min()
}

Ответ 2

Это поведение немного неинтуитивно для тех, у кого есть фон Python, а не, скажем, фон С++, поэтому позвольте мне немного пояснить.

В Rust значения концептуально хранятся внутри имени, которое их связывает. Таким образом, если вы пишете

let mut x = Foo { t: 10 };
let mut y = x;
x.t = 999;

y.t по-прежнему будет 10.

Итак, когда вы пишете

let x: Iterator<Item=&'a u32>;

(или то же самое в списке параметров функции), Rust необходимо выделить достаточно места для любого значения типа Iterator<Item=&'a u32>. Даже если это было возможно, это было бы неэффективно.

Итак, что делает Rust вместо этого предлагает вам возможность

Поместите значение в кучу, например. с Box, который дает семантику в стиле Python. Тогда вы можете взять в целом &mut Iterator<Item=&'a u32>.
Специализируйте каждый вызов функции для каждого возможного типа, чтобы выполнить оценку. Это более гибко, так как ссылка на характер является возможной специализацией и дает компилятору больше возможностей для специализации, но означает, что вы не можете иметь динамическую отправку (где тип может варьироваться в зависимости от параметров времени выполнения).

Ответ 3

Проще всего использовать impl Trait, impl Iterator:

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()));
}

детская площадка