Rust 迭代器（Iterator trait ）的要诀和技巧

niqin.com

发布于 2022-06-30 16:47:32

7670

发布于 2022-06-30 16:47:32

最近，敲 Rust 代码的过程中，对于其中迭代器（Iterator trait ）的使用，遇到了一些不明所以的问题，求助于万能的搜索引擎，找到了一些资料。因此，对于 Rust 中迭代器（Iterator trait ）的使用，有了一些新的认知。特此写文以记之。

主要参考自 Robin Moussu 的博客文章，以及他的 github 仓库。

要诀1：为自定义集合（collection）添加 `iter()` 函数

如果您要创建自己的集合，例如一个封装动态数组 Vec 的结构体，那么，您可能需要为其提供一个 iter() 函数。这样，集合的使用者，就可以访问集合的元素，而不会暴露集合的实现细节。当然，您也可以创建一个新类型，为其实现 Iterator trait，但客观地讲，即使实现 Iterator trait 并不复杂，但也有诸多需要特别注意的细节！幸运的是，还有一种更简单的方法：

struct MyCollection {
    data: Vec<i32>, // 或者其它自身具有 `iter()` 方法的类型
    // ...
}

impl MyCollection {
    fn iter(&self) -> impl Iterator {
        self.data.iter()
    }
    // ...
}

上述代码可以吗？跑一跑看看有没有问题。

error[E0759]: `self` has an anonymous lifetime `'_` but it needs to satisfy a `'static` lifetime requirement
 --> src/lib.rs:8:19
  |
7 |     fn iter(&self) -> impl Iterator {
  |             ----- this data with an anonymous lifetime `'_`...
8 |         self.data.iter()
  |         --------- ^^^^
  |         |
  |         ...is captured here...
  |
note: ...and is required to live as long as `'static` here
 --> src/lib.rs:7:23
  |
7 |     fn iter(&self) -> impl Iterator {
  |                       ^^^^^^^^^^^^^
help: to declare that the `impl Trait` captures data from argument `self`, you can add an explicit `'_` lifetime bound
  |
7 |     fn iter(&self) -> impl Iterator + '_ {
  |                                     ^^^^

根据编译器的提示，是因为我忘了为 iter() 的返回类型设置生命周期标记 '_。我们来解决这个问题：

fn iter(&self) -> impl Iterator + '_ {
    self.data.iter()
}

这称之为生命周期省略，对于省略的详细描述，可以参考文档。这段代码，和如下代码是等价的：

fn iter<'a>(&'a self) -> impl Iterator + 'a {
    self.data.iter()
}

幸运的是，编译器足够聪明，能够理解匿名生存期 '_，并可以将其绑定到唯一引用 &self 的生命周期。

如果你不想自己编写上述代码，请移步 Rust 官方演练场（Playground）。

要诀2：从不同类型的多个迭代器中，返回其中之一

如果您熟悉其它高级编程语言，您可能会尝试创建如下函数：

fn forward_or_backward<T>(v: &Vec<T>, forward: bool) -> impl Iterator + '_
{
    if forward {
        v.iter()
    } else {
        v.iter().rev()
    }
}

v.iter() 和 v.iter().rev()，各自都返回一个实现了 Iterator trait 的类型。这段代码跑的通吗？

任何条件表达式（如 if、match、任何类型的循环等）的所有分支，其具体类型必须匹配。

我寄希望于编译器，希望它足够聪明，能够自动创建一个新类型，但目前情况并非如此。不过 Rust 语言团队已经在开发更重要、更令人兴奋的特性。

让我们看看编译器怎么说：

error[E0308]: `if` and `else` have incompatible types
 --> src/main.rs:6:9
  |
3 | /     if forward {
4 | |         v.iter()
  | |         -------- expected because of this
5 | |     } else {
6 | |         v.iter().rev()
  | |         ^^^^^^^^^^^^^^ expected struct `std::slice::Iter`, found struct `Rev`
7 | |     }
  | |_____- `if` and `else` have incompatible types
  |
  = note: expected type `std::slice::Iter<'_, _>`
           found struct `Rev<std::slice::Iter<'_, _>>`
help: you could change the return type to be a boxed trait object
  |
1 | fn forward_or_backward<T>(v: &Vec<T>, forward: bool) -> Box<dyn Iterator<Item=&T> + '_>
  |                                                         ^^^^^^^                       ^
help: if you change the return type to expect trait objects, box the returned expressions
  |
4 |         Box::new(v.iter())
5 |     } else {
6 |         Box::new(v.iter().rev())

编译器的建议并不难读懂，但是为什么我们要为动态内存分配和动态调度付出代价呢？如果我们使用静态调度呢？让我们来实现它：

首先，我们需要一个枚举来存储所有分支。在这里，我们完全可以使用类似于 either crate 的库来实现。但是，为了解释实现细节，我们将自己实现。

enum Either<Left, Right> {
    Left(Left),
    Right(Right),
}

现在，我们要为新类型实现 Iterator trait。当然，我们只能在枚举元素 Left 和 Right 都是迭代器的情况下，才能这样做。这两个迭代器必须产生相同类型的元素。

impl <Left, Right, Item> Iterator for Either<Left, Right>
where
    Left: Iterator<Item=Item>,
    Right: Iterator<Item=Item>,
{
    type Item = Item;
    fn next(&mut self) -> Option<Self::Item> {
        match self {
            Self::Left(it) => it.next(),
            Self::Right(it) => it.next(),
        }
    }
}

我们应该实现 nth() 和 fold() 方法吗？

文档是这样讲的：

需要注意到，迭代器提供了一个默认的方法实现，比如 nth 和 fold，它们在内部调用 next。
但是，如果迭代器不调用 next，就可以更有效地进行计算。那么，也可以自定义 nth 和 fold 的实现。

所以，nth() 和 fold() 方法的实现不是必需的。但是，将对 nth() 和 fold() 方法的调用，委托给 Left 和 Right 的实现，可能是个好主意，就像我们对 next() 方法所做的那样。因为 Iterator trait 的任何方法，都可以被专门实现为 Left 和 Right 类型。所以，最好对所有函数都这样做。

同样的逻辑，也可以应用于如 DoubleEndedIterator、ExactSizeIterator，和 FusedIterator 等 trait。

让我们以 ExactSizeIterator trait 为例，我们希望将实现转发给基础类型：

impl<Left, Right> ExactSizeIterator for Either<Left, Right>
where
    Left: ExactSizeIterator,
    Right: ExactSizeIterator,
{
    fn len(&self) -> usize {
        match self {
            Self::Left(it) => it.len(),
            Self::Right(it) => it.len(),
        }
    }
    fn is_empty(&self) -> bool {
        match self {
            Self::Left(it) => it.is_empty(),
            Self::Right(it) => it.is_empty(),
        }
    }
}

代码是否正确？我们跑一下，看看编译器怎么说：

error[E0271]: type mismatch resolving `<Right as Iterator>::Item == <Left as Iterator>::Item`
  --> src/main.rs:50:19
   |
50 | impl<Left, Right> std::iter::ExactSizeIterator for Either<Left, Right>
   |      ----  -----  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected type parameter `Right`, found type parameter `Left`
   |      |     |
   |      |     expected type parameter
   |      found type parameter
   |
   = note: expected associated type `<Right as Iterator>::Item`
              found associated type `<Left as Iterator>::Item`
   = note: a type parameter was expected, but a different one was found; you might be missing a type parameter or trait bound
   = note: for more information, visit https://doc.rust-lang.org/book/ch10-02-traits.html#traits-as-parameters
   = note: required because of the requirements on the impl of `Iterator` for `Either<Left, Right>`

编译器检查后告知，应当明确指出，Right 和 Left 都是产生相同类型的迭代器。我们做些小修改：

impl<Left, Right, T> std::iter::ExactSizeIterator for Either<Left, Right>
where
    Left: std::iter::ExactSizeIterator + Iterator<Item=T>,
    Right: std::iter::ExactSizeIterator + Iterator<Item=T>,

好像该做的都做了？我们开始测试。

fn main() {
    let v = vec![0, 1, 3, 7];

    let forward: Vec<_> = forward_or_backward(&v, true).collect();
    let backward: Vec<_> = forward_or_backward(&v, false).collect();
    println!("forward: {:?}", forward); // 0, 1, 3, 7
    println!("backward: {:?}", backward); // 7, 3, 1, 0
}

又出错了：

error[E0277]: `<impl Iterator as Iterator>::Item` doesn't implement `Debug`
  --> src/main.rs:87:31
   |
87 |     println!("forward: {:?}", forward); // 0, 1, 3, 7
   |                               ^^^^^^^ `<impl Iterator as Iterator>::Item` cannot be formatted using `{:?}` because it doesn't implement `Debug`
   |
   = help: the trait `Debug` is not implemented for `<impl Iterator as Iterator>::Item`
   = note: required because of the requirements on the impl of `Debug` for `Vec<<impl Iterator as Iterator>::Item>`
   = note: required by `std::fmt::Debug::fmt`
   = note: this error originates in a macro (in Nightly builds, run with -Z macro-backtrace for more info)

太奇怪了，我们是对整数进行迭代，整数本身就实现了调试特性的，为什么这儿不起作用呢？

让我们想一想……

当我们实现 forward_or_backward() 时，我们并没有对迭代项的类型进行转发。我们上面的代码是：

fn forward_or_backward<T>(v: &Vec<T>, forward: bool) -> impl Iterator + '_

可以看到，迭代器产生项的类型是未知的。如果我们在收集 vector 的值时，不使用类型推断。那么，很明显：

let forward: Vec<i32> = forward_or_backward(&v, true).collect();

error[E0277]: a value of type `Vec<i32>` cannot be built from an iterator over elements of type `<impl Iterator as Iterator>::Item`
  --> src/main.rs:85:59
   |
85 |     let forward: Vec<i32> = forward_or_backward(&v, true).collect();
   |                                                           ^^^^^^^ value of type `Vec<i32>` cannot be built from `std::iter::Iterator<Item=<impl Iterator as Iterator>::Item>`
   |
   = help: the trait `FromIterator<<impl Iterator as Iterator>::Item>` is not implemented for `Vec<i32>`

所以，我们仅需要修改 forward_or_backward 的声明：

fn forward_or_backward<T>(v: &Vec<T>, forward: bool) -> impl Iterator<Item=T> + '_

现在，代码正确了。

如果你不想自己编写上述代码，请移步 Rust 官方演练场（Playground）。

关于迭代器，还有很多要掌握的，它是 Rust 中最有用的 trait 之一，但今天就到此为止。

谢谢您的阅读！

原文链接：Rust iterators tips and tricks

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-04-05，如有侵权请联系 cloudcommunity@tencent.com 删除

ide

rust

java

本文分享自 Rust 生态与实践微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

ide

rust

java

登录后参与评论

0 条评论

热度