arrays - 使用通用迭代器而不是特定的列表类型

Question

我对Rust很陌生，来自C#/Java/类似语言。

在C#中，我们有IEnumerable<T>，可用于迭代几乎任何类型的数组或列表。 C#还具有yield关键字，您可以使用该关键字返回惰性列表。这是一个例子

// Lazily returns the even numbers out of an enumerable
IEnumerable<int> Evens(IEnumerable<int> input)
{
    foreach (var x in input)
    {
        if (x % 2 == 0)
        {
            yield return x;
        }
    }
}

当然，这是一个愚蠢的例子。我知道我可以用Rust的map函数来做到这一点，但是我想知道如何创建自己的方法来接受和返回通用迭代器。

据我所知，Rust具有可以类似使用的通用迭代器，但它们超出了我的理解。我在文档中看到了Iter，IntoIterator，Iterator类型以及可能更多的内容，但是没有很好的理解它们的方法。

任何人都可以提供有关如何创建上述内容的清晰示例吗？谢谢!

P.S.惰性方面是可选的。我更关心的是远离特定列表和数组类型的抽象。

Answer 1

首先，忘记IntoIterator和其他特征或类型。 Rust的核心迭代特征是Iterator。它的精简定义如下:

trait Iterator {
    type Item;  // type of elements returned by the iterator
    fn next(&mut self) -> Option<Self::Item>;
}

您可能知道，您可以将迭代器视为某种结构内的游标。 next()方法使此光标向前移动，返回其先前指向的元素。自然，如果集合用完了，就没有任何要返回的内容，因此next()返回的是Option<Self::Item>，而不仅仅是Self::Item。
Iterator是一个特征，因此可以通过特定类型来实现。请注意，Iterator本身不是适合用作返回值或函数参数的类型-您必须使用实现此特征的具体类型。

上面的声明听起来太严格了-那么如何使用任意迭代器类型呢？ -但是由于泛型，事实并非如此。如果要让函数接受任意迭代器，只需在相应的参数中使其泛型，并在相应的类型参数上添加Iterator即可:

fn iterate_bytes<I>(iter: I) where I: Iterator<Item=u8> { ... }

从函数返回迭代器可能很困难，但请参见下文。

例如，&[T]上有一个名为iter()的方法，该方法返回一个迭代器，该迭代器将对切片的引用产生。该迭代器是this结构的一个实例。您可以在该页面上看到Iterator如何实现Iter:

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<&'a T> { ... }
    ...
}

该结构保留了对原始切片及其内部某些迭代状态的引用。它的next()方法更新此状态并返回下一个值(如果有)。

任何类型实现Iterator的值都可以在for循环中使用(for循环实际上与IntoIterator一起使用，但请参见下文):

let s: &[u8] = b"hello";
for b in s.iter() {
    println!("{}", b);   // prints numerical value of each byte
}

现在，Iterator特性实际上比上述特性更复杂。它还定义了许多转换方法，这些方法消耗调用它们的迭代器并返回一个新的迭代器，该迭代器以某种方式转换或过滤原始迭代器中的值。例如，enumerate()方法返回一个迭代器，该迭代器从原始迭代器产生值以及元素的位置编号:

let s: &[u8] = b"hello";
for (i, b) in s.iter().enumerate() {
    println!("{} at {}", b, i);   // prints "x at 0", "y at 1", etc.
}

enumerate()的定义如下:

trait Iterator {
    type Item;
    ...
    fn enumerate(self) -> Enumerate<Self> {
        Enumerate {
            iter: self,
            count: 0
        }
    }
    ...
}

Enumerate只是一个结构，其中包含一个迭代器和一个计数器，并实现Iterator<Item=(usize, I::Item)>:

struct Enumerate<I> {
    iter: I,
    count: usize
}

impl<I> Iterator for Enumerate<I> where I: Iterator {
    type Item = (usize, I::Item);

    #[inline]
    fn next(&mut self) -> Option<(usize, I::Item)> {
        self.iter.next().map(|a| {
            let ret = (self.count, a);
            self.count += 1;
            ret
        })
    }
}

这就是大多数迭代器转换的实现方式:每个转换都是一个包装结构，该结构包装原始迭代器并通过委派给原始迭代器并以某种方式转换结果值来实现Iterator特性。例如，上例中的s.iter().enumerate()返回类型为Enumerate<Iter<'static, u8>>的值。

请注意，虽然enumerate()是直接在Iterator特性中定义的，但它也可以是独立函数:

fn enumerate<I>(iter: I) -> Enumerate<I> where I: Iterator {
    Enumerate {
        iter: iter,
        count: 0
    }
}

该方法的工作原理非常相似-它只使用隐式Self类型参数，而不使用显式命名的参数。

您可能想知道IntoIterator特性是什么。好吧，这只是一个便利转换特征，可以用任何可以转换为迭代器的类型来实现:

pub trait IntoIterator where Self::IntoIter::Item == Self::Item {
    type Item;
    type IntoIter: Iterator;

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

例如，&'a [T]可以转换为Iter<'a, T>，因此它具有以下实现:

impl<'a, T> IntoIterator for &'a [T] {
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;

    fn into_iter(self) -> Iter<'a, T> {
        self.iter()  // just delegate to the existing method
    }
}

对于大多数容器类型和对这些类型的引用都实现了此特征。实际上，它由for循环使用-可以在IntoIterator子句中使用实现in的任何类型的值:

let s: &[u8] = b"hello";
for b in s { ... }

从学习和阅读的角度来看，这非常好，因为它具有较少的噪音(采用类似iter()的方法的形式)。它甚至允许这样的事情:

let v: Vec<u8> = ...;

for i in &v { /* i is &u8 here, v is borrowed immutably */ }
for i in &mut v { /* i is &mut u8 here, v is borrowed mutably */ }
for i in v { /* i is just u8 here, v is consumed */ }

这是可能的，因为IntoIterator，&Vec<T>和&mut Vec<T>的实现方式不同。

每个Vec<T>实现的Iterator都会执行身份转换(IntoIterator只是返回调用它的迭代器)，因此您也可以在into_iter()循环中使用Iterator实例。

因此，在通用函数中使用for是有意义的，因为它将使API对用户更加方便。例如，上面的IntoIterator函数可以这样重写:

fn enumerate<I>(source: I) -> Enumerate<I::IntoIter> where I: IntoIter {
    Enumerate {
        iter: source.into_iter(),
        count: 0
    }
}

现在，您将看到如何使用泛型轻松实现具有静态类型的转换。 Rust没有C#/Python enumerate()之类的东西(但是它是最想要的功能之一，因此有一天它可能会出现在语言中!)，因此您需要显式地包装源迭代器。例如，您可以编写类似于上面的yield结构的代码来完成所需的任务。

但是，最惯用的方法是使用现有的组合器为您完成工作。例如，您的代码可能编写如下:

let iter = ...;  // iter implements Iterator<Item=i32>
let r = iter.filter(|&x| x % 2 == 0);  // r implements Iterator<Item=i32>
for i in r {
    println!("{}", i);  // prints only even items from the iterator
}

但是，当您想编写自定义组合器函数时，使用组合器可能会很丑陋，因为许多现有的组合器函数都接受闭包(例如，上面的Enumerate一个)，但是Rust中的闭包是作为匿名类型的值实现的，所以这是没有办法的编写返回迭代器的函数签名:

fn filter_even<I>(source: I) -> ??? where I: IntoIter<Item=i32> {
    source.into_iter().filter(|&x| x % 2 == 0)
}

有几种解决方法，其中一种是使用trait对象:

fn filter_even<'a, I>(source: I) -> Box<Iterator<Item=i32>+'a>
    where I: IntoIterator<Item=i32>, I::IntoIter: 'a
{
    Box::new(source.into_iter().filter(|&x| x % 2 == 0))
}

在这里，我们将filter()返回的实际迭代器类型隐藏在特征对象的后面。请注意，为了使该函数完全通用，我必须添加一个生存期参数以及对filter()特质对象和Box关联类型的相应绑定(bind)。这是必需的，因为I::IntoIter可能在其中包含任意生存期(就像上面的I::IntoIter类型一样)，并且我们必须在trait对象类型中指定它们(否则会丢失生存期信息)。

从Iter<'a, T>特性创建的特征对象本身实现了Iterator，因此您可以像往常一样继续使用这些迭代器:

let source = vec![1_i32, 2, 3, 4];
for i in filter_even(source) {
    println!("{}", i);  // prints 2 and 4
}