在Rust中创建一个返回迭代器的迭代器方法。

Question

我希望定义一个懒惰的square()方法，避免不必要的运行时开销（没有dyn关键字），该方法可在任何Iterable<Item = u8>上调用并返回另一个Iterable<Item = u8>，如下所示：

fn main() {
    vec![1, 2, 3, 4, 5]
        .iter()
        .filter(|x| x > 1)
        .squared()
        .filter(|x| x < 20);
}

我知道如何定义一个独立的函数squared():

fn squared<I: Iterator<Item = u8>>(iter: I) -> impl Iterator<Item = u8> {
    iter.map(|x| x * x)
}

要在Iterator<Item = u8>上定义该方法，我需要首先定义一个trait。但这里遇到了困难——特征无法在返回值中使用impl关键字。我正在寻找像下面这样的解决办法，但它不能工作：

trait Squarable<I: Iterator<Item = u8>> {
    fn squared(self) -> I;
}

impl<I, J> Squarable<I> for J
where
    I: Iterator<Item = u8>,
    J: Iterator<Item = u8>,
{
    fn squared(self) -> I {
        self.map(|x| x * x)
    }
}

我曾多次尝试解决这个问题，包括将squared的返回类型更改为Map<u8，fn(u8) -> u8>并调整IntoIterable，但到目前为止都没有成功。非常感谢您提供的任何帮助！

- Marcel

---

从技术上讲，虽然它不包含“dyn”，但仍然必须在运行时遵循函数指针，除非编译器可以将其优化掉。 - trent

Answer 1

首先，您的输出迭代器应该是一个关联类型而不是特质参数，因为该类型是特质的一个输出（它不是调用方可以控制的内容）。

trait Squarable {
    type Output: Iterator<Item = u8>;
    fn squared(self) -> I;
}

---

话虽如此，解决这个问题有几种不同的可能方法，每种方法都有不同的优缺点。

使用特征对象

第一种方法是使用特征对象，例如dyn Iterator<Item = u8>，在运行时擦除类型。虽然会稍微增加运行时成本，但在当前稳定版本的Rust中，这绝对是最简单的解决方案：

trait Squarable {
    fn squared(self) -> Box<dyn Iterator<Item = u8>>;
}

impl<I: 'static + Iterator<Item = u8>> Squarable for I {
    fn squared(self) -> Box<dyn Iterator<Item = u8>> {
        Box::new(self.map(|x| x * x))
    }
}

使用自定义迭代器类型

从trait使用者的角度来看，在稳定版的rust中，这绝对是最清晰的方式，但是需要更多的代码实现，因为你需要编写自己的迭代器类型。然而，对于简单的map迭代器来说，这相当简单明了:

trait Squarable: Sized {
    fn squared(self) -> SquaredIter<Self>;
}

impl<I: Iterator<Item = u8>> Squarable for I {
    fn squared(self) -> SquaredIter<I> {
        SquaredIter(self)
    }
}

struct SquaredIter<I>(I);

impl<I: Iterator<Item = u8>> Iterator for SquaredIter<I> {
    type Item = u8;
    fn next(&mut self) -> Option<u8> {
        self.0.next().map(|x| x * x)
    }
}

使用显式的Map类型

<I as Iterator>::map(f) 的类型为 std::iter::Map<I, F>，因此如果映射函数的类型F已知，我们可以显式地使用该类型，而不会带来运行时成本。但是，这会将特定类型作为函数返回类型的一部分暴露出来，这使得在不破坏相关代码的情况下更换它变得更加困难。在大多数情况下，函数也不会被知道；在这种情况下，我们可以使用 F = fn(u8) -> u8，但是由于函数不保留任何内部状态（但通常这不起作用）。

trait Squarable: Sized {
    fn squared(self) -> std::iter::Map<Self, fn(u8) -> u8>;
}

impl<I: Iterator<Item = u8>> Squarable for I {
    fn squared(self) -> std::iter::Map<Self, fn(u8) -> u8> {
        self.map(|x| x * x)
    }
}

使用关联类型

与上述方法的替代方案是给trait一个关联类型。仍然有一个限制，即函数类型必须已知，但是它更加通用，因为Map<...>类型与trait本身没有直接关联，而是与其实现相关。

trait Squarable {
    type Output: Iterator<Item = u8>;
    fn squared(self) -> Self::Output;
}

impl<I: Iterator<Item = u8>> Squarable for I {
    type Output = std::iter::Map<Self, fn(u8) -> u8>;
    fn squared(self) -> Self::Output {
        self.map(|x| x * x)
    }
}

在关联类型中使用impl

这类似于上面的“使用关联类型”，但是除了它是迭代器之外，您可以完全隐藏实际类型。我个人认为这是更可取的解决方案，但不幸的是它仍然不稳定（它取决于type_alias_impl_trait功能），因此您只能在夜间版本的Rust中使用它。

#![feature(type_alias_impl_trait)]

trait Squarable {
    type Output: Iterator<Item = u8>;
    fn squared(self) -> Self::Output;
}

impl<I: Iterator<Item = u8>> Squarable for I {
    type Output = impl Iterator<Item = u8>;
    fn squared(self) -> Self::Output {
        self.map(|x| x * x)
    }
}

- Frxstrem