如何在不调用collect()的情况下为新类型vec实现IntoIterator？

Question

这是我制作的一个小示例程序：

type Index = usize;
type ValType = u32;

#[derive(Debug)]
pub struct NewVec(pub Vec<ValType>);

impl IntoIterator for NewVec {
    type Item = (Index, ValType);
    type IntoIter = <Vec<(Index, ValType)> as IntoIterator>::IntoIter;

    fn into_iter(self) -> Self::IntoIter {
        self.0
            .into_iter()
            .enumerate()
            .collect::<Vec<_>>()
            .into_iter()
    }
}

fn main() {
    let v = vec![100];
    let new_v = NewVec(v.clone());
    
    println!("Vec::into_iter:    {:?}", v.into_iter());
    println!("NewVec::into_iter: {:?}", new_v.into_iter());
    
}

该程序正确运行，并生成以下输出：

Vec::into_iter:    IntoIter([100])
NewVec::into_iter: IntoIter([(0, 100)])

然而 NewVec::into_iterator 调用collect()来创建一个新的Vec，然后调用它的into_iter()。

我的目标是消除对collect()的调用并直接返回一个迭代器。我希望避免不必要的分配。

这可能吗？

请注意，如果我们删除对 .collect() 的调用，我们会收到此错误：

error[E0308]: mismatched types
  --> src/main.rs:12:9
   |
11 |       fn into_iter(self) -> Self::IntoIter {
   |                             -------------- expected `std::vec::IntoIter<(usize, u32)>` because of return type
12 | /         self.0
13 | |             .into_iter()
14 | |             .enumerate()
15 | |             .into_iter()
   | |________________________^ expected `IntoIter<(usize, u32)>`, found `Enumerate<IntoIter<u32>>`
   |
   = note: expected struct `std::vec::IntoIter<(usize, u32)>`
              found struct `Enumerate<std::vec::IntoIter<u32>>`

但我不知道如何将 an 转换Enumerate为 a std::vec::IntoIter，或者这是否可能。

查看游乐场

Answer 1

既然.enumerate()提供了迭代器，我就直接返回它。我们只需要进行调整Self::IntoIter以匹配确切的类型（编译器的错误消息对我们有很大帮助）。

impl IntoIterator for NewVec {
    type Item = (Index, ValType);
    type IntoIter = std::iter::Enumerate<std::vec::IntoIter<ValType>>;

    fn into_iter(self) -> Self::IntoIter {
        self.0.into_iter().enumerate()
    }
}

这里是评论里的建议，用拳击+动态调度。

impl IntoIterator for NewVec {
    type Item = (Index, ValType);
    type IntoIter = Box<dyn Iterator<Item = Self::Item>>;

    fn into_iter(self) -> Self::IntoIter {
        Box::new(self.0.into_iter().enumerate())
    }
}

...

for e in new_v.into_iter() {
    println!("{:?}", e);
}

Answer 2

有几种方法可以实现这一点。我将尽力展示我所知道的尽可能多的内容并解释它们的优缺点，以便您可以选择最适合您的用例的一种。在我的所有示例中，我都使用了IndexVec通用的 overVec元素。

IntoIter方案一：直接在关联类型中命名迭代器类型

这非常简单。由于您所做的只是调用into_iteraVec然后将其包装在枚举中，因此您可以直接命名此类型。

use std::iter::Enumerate;
use std::vec::IntoIter as StdVecIntoIter;

pub struct IndexVec<T>(pub Vec<T>);

impl<T> IntoIterator for IndexVec<T> {
    type Item = (usize, T);
    type IntoIter = Enumerate<StdVecIntoIter<T>>;

    fn into_iter(self) -> Self::IntoIter {
        self.0.into_iter().enumerate()
    }
}

优点：

• 非常简单的解决方案，适用于稳定的锈迹
• 很少的样板代码

缺点：

• 非封装友好（如果您想更改底层实现，则必须更改IntoIter类型，这将是重大更改）
• 迭代器类型可能变得非常复杂，有些是无法命名的（例如带有传递闭包的Filter ）

解决方案 2：使用自定义包装类型

我们可以为迭代器创建自定义包装类型，就像我们为Vec. 这允许封装实现，但会导致大量的样板文件。这只是完整实现的草稿，因为对于生产代码，您还希望实现FusedIterator、ExactSizeIterator和DoubleEndedIterator for IndexVecIter.

如果您还想迭代借用的内容，IndexVec则必须再创建两个包装器，这将使样板文件的数量增加三倍。

use std::iter::Enumerate;
use std::vec::IntoIter as StdVecIntoIter;

pub struct IndexVec<T>(pub Vec<T>);

impl<T> IntoIterator for IndexVec<T> {
    type Item = (usize, T);
    type IntoIter = IndexVecIter<T>;

    fn into_iter(self) -> Self::IntoIter {
        IndexVecIter(self.0.into_iter().enumerate())
    }
}

pub struct IndexVecIter<T>(Enumerate<StdVecIntoIter<T>>);

impl<T> Iterator for IndexVecIter<T> {
    type Item = (usize, T);

    fn next(&mut self) -> Option<Self::Item> {
        self.0.next()
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.0.size_hint()
    }
}

优点：

• 允许您封装您的实现（您可以稍后更改它而无需引入制动更改）

缺点：

• 非常大的样板
• 与之前的解决方案一样，您可能会遇到精确命名迭代器类型的问题

方案三：动态调度

为了避免需要准确命名迭代器类型，我们可以使用动态调度。这将导致分配和指针间接，但在许多情况下，这种成本不是问题。

pub struct IndexVec<T>(pub Vec<T>);

impl<T> IntoIterator for IndexVec<T>
where
    T: 'static,
{
    type Item = (usize, T);
    type IntoIter = Box<dyn Iterator<Item = Self::Item>>;

    fn into_iter(self) -> Self::IntoIter {
        Box::new(self.0.into_iter().enumerate())
    }
}

优点：

• 非常简单的解决方案，适用于稳定的锈迹
• 很少的样板文件
• 部分封装（您可以更改内部迭代器，但Box<dyn Iterator>它是接口的一部分）

缺点：

• 堆分配和动态分派的额外运行时成本
• 仅适用于T: 'static

解决方案4：impl Trait

使用当前 ( rustc 1.73.0) 不可用的功能，impl_trait_in_assoc_type您可以指定关联的类型IntoIter是impl Iterator。这与impl Trait返回位置的工作原理类似。编译器将在编译期间推断具体类型，并且能够执行其所有优化，但对于调用者来说，该类型是隐藏的，调用者唯一能做的就是使用特征的接口。因为无论如何这正是IntoIter所提供的，所以这是一个完美的选择！

尽管此功能尚未稳定，但已非常接近稳定，并且可能会在Rust 2024 edition.

#![feature(impl_trait_in_assoc_type)]

pub struct IndexVec<T>(pub Vec<T>);

impl<T> IntoIterator for IndexVec<T> {
    type Item = (usize, T);
    type IntoIter = impl Iterator<Item = Self::Item>;

    fn into_iter(self) -> Self::IntoIter {
        self.0.into_iter().enumerate()
    }
}

优点：

• 非常简单的解决方案
• 很少的样板文件
• 全封装
• 在底层实现中使用不可命名类型的能力

缺点：

• 还不稳定