是否有类似于slice::chunks/windows的迭代器等价物，可以循环遍历成对、三元组等？

Question

是否有类似于slice::chunks/windows的迭代器等价物，可以循环遍历成对、三元组等？

51

同时迭代多个变量可以很有用，可以重叠（slice::windows），也可以不重叠（slice::chunks）。

这仅适用于切片；是否可能对使用元组方便的迭代器执行此操作？

可以编写类似以下内容的代码：

for (prev, next) in some_iter.windows(2) {
    ...
}

如果不行，那么它是否可以作为现有迭代器的特性来实现？

- ideasman42

2

如果你决定在末尾没有足够的项时该怎么做，那么你可以很容易地执行iter_pairs、iter_triples，但目前在Rust中还没有通用的“任意大小元组”函数。 - Chris Emerson

1

如果数量不足，则不会执行任何操作，就像切片函数一样。 - ideasman42

1

这个问题在IRC上被指出：https://docs.rs/itertools/*/itertools/trait.Itertools.html#method.tuple_windows。在发布答案之前，我想先查看它的代码。 - ideasman42

3个回答

31

TL;DR: 在任意迭代器/集合上实现 chunks 和 windows 的最佳方法是先将其 collect 到一个 Vec 中，然后对其进行迭代。

在 Rust 中，精确的语法是不可能的。

问题在于，在 Rust 中，函数签名依赖于类型而不是值。虽然存在 Dependent Typing，但只有少数语言实现了它（这很难）。

这就是为什么 chunks 和 windows 返回子切片的原因；&[T] 中的元素数量不是类型的一部分，因此可以在运行时决定。

假设您要求：for slice in some_iter.windows(2)。

那么存储支持该切片的内容应该在哪里呢？

它不能在：

原始集合中，因为 LinkedList 没有连续的存储空间
迭代器中，因为 Iterator::Item 的定义中没有可用的生命周期

所以，不幸的是，只有在支持切片的存储空间中才能使用切片。

如果接受动态分配，则可以将 Vec<Iterator::Item> 作为分块迭代器的 Item。

struct Chunks<I: Iterator> {
    elements: Vec<<I as Iterator>::Item>,
    underlying: I,
}

impl<I: Iterator> Chunks<I> {
    fn new(iterator: I, size: usize) -> Chunks<I> {
        assert!(size > 0);

        let mut result = Chunks {
           underlying: iterator, elements: Vec::with_capacity(size)
        };
        result.refill(size);
        result
    }

    fn refill(&mut self, size: usize) {
        assert!(self.elements.is_empty());

        for _ in 0..size {
            match self.underlying.next() {
                Some(item) => self.elements.push(item),
                None => break,
            }
        }
    }
}

impl<I: Iterator> Iterator for Chunks<I> {
    type Item = Vec<<I as Iterator>::Item>;

    fn next(&mut self) -> Option<Self::Item> {
        if self.elements.is_empty() {
            return None;
        }

        let new_elements = Vec::with_capacity(self.elements.len());
        let result = std::mem::replace(&mut self.elements, new_elements);

        self.refill(result.len());

        Some(result)
    }
}

fn main() {
    let v = vec!(1, 2, 3, 4, 5);

    for slice in Chunks::new(v.iter(), 2) {
        println!("{:?}", slice);
    }
}

将返回：

[1, 2]
[3, 4]
[5]

细心的读者会发现，我悄悄地从windows转换到了chunks。

windows更难一些，因为它会多次返回相同的元素，需要将该元素Clone。此外，由于每次需要返回完整的Vec，因此它需要在内部保持一个Vec<Vec<Iterator::Item>>。

这留给读者作为练习。

最后，关于性能的说明：所有这些分配都会对性能产生影响（特别是在windows情况下）。

最佳的分配策略通常是分配一块单独的内存，然后依靠它来生存（除非量真的很大，否则需要流式传输）。

在Rust中，它被称为collect::<Vec<_>>()。

由于Vec具有chunks和windows方法（通过实现Deref<Target=[T]>），因此您可以使用它们代替：

for slice in v.iter().collect::<Vec<_>>().chunks(2) {
    println!("{:?}", slice);
}

for slice in v.iter().collect::<Vec<_>>().windows(2) {
    println!("{:?}", slice);
}

有时候，最好的解决方案就是最简单的。

- Matthieu M.

4

很抱歉给你点踩，但"在Rust中无法实现所要求的确切语法"这种说法是不正确的；请查看我的答案。尽管如此，你对大部分其他内容的分析都是合理的。 - Shepmaster

2

@Shepmaster：您的回答也没有完全按照所要求的语法。请求是 for (prev, next) in some_iter.windows(2)，其中 2 是运行时参数，我理解为我可以传递 3 并且有 for (n0, n1, n2) in some_iter.windows(3)，但这是不可能的。您选择关注 (prev, next) 并忽略了运行时参数，这可能对 OP 来说没问题，但就我而言，这不是他们要求的（我不会读心术）。 - Matthieu M.

一个很好的观点。特别是如果存在不匹配，指定元组大小和“windows”的参数都没有意义。我建议你在回答中明确指出这一点 - 也许添加一个例子？ - Shepmaster

@Shepmaster：我不太确定你指的是什么样的例子；我已经引用了类型不能依赖于值，除非使用Dependent Typing，而且说实话，我不知道如何说明它。也许这并不重要，因为你的答案显然更好。 - Matthieu M.

你的回答很有道理，但我仍然感到迭代器缺少“块”和“窗口”的问题。正如你已经说过的那样，使用动态分配只有c个元素（其中c是块的大小）实际上非常容易实现“块”；相比之下，使用“collect :: <Vec <_>>”然后分块意味着我们需要动态分配n个元素，其中n是迭代器产生的元素的总数。你的“块”示例可以进行单次分配优化，因此性能不会受到影响。 - kccqzy

1

这个问题留给读者自己去解决。这里描述的 windows 功能正是我所需要的，但我不确定如何实现它，因为我还是 Rust 的新手。有示例吗？ - user5359531

20

在夜间版本中

现在可以在夜间版本中使用名为array_chunks的版本。

#![feature(iter_array_chunks)]

for [a, b, c] in some_iter.array_chunks() {
    ...
}

而且它能很好地处理余数：

#![feature(iter_array_chunks)]

for [a, b, c] in some_iter.by_ref().array_chunks() {
    ...
}

let rem = some_iter.into_remainder();

在稳定版本中

自Rust 1.51以来，使用常量泛型可以实现迭代器产生任意N大小的常量数组[T; N]。

我构建了两个独立的crate来实现这一点：

iterchunks提供array_chunks()
iterwindows提供array_windows()

use iterchunks::IterChunks; // 0.2

for [a, b, c] in some_iter.array_chunks() {
    ...
}

use iterwindows::IterWindows; // 0.2

for [prev, next] in some_iter.array_windows() {
    ...
}

使用 Itertools 答案中给出的示例：

use iterchunks::IterChunks; // 0.2

fn main() {
    let some_iter = vec![1, 2, 3, 4, 5, 6].into_iter();

    for [prev, next] in some_iter.array_chunks() {
        println!("{}--{}", prev, next);
    }
}

这会输出：

1--2
3--4
5--6

大多数情况下，数组大小可以被推断出来，但您也可以明确指定它。此外，任何合理的大小 N 都可以使用，没有像 Itertools 的限制。

use iterwindows::IterWindows; // 0.2

fn main() {
    let mut iter = vec![1, 2, 3, 4, 5, 6].into_iter().array_windows::<5>();
    println!("{:?}", iter.next());
    println!("{:?}", iter.next());
    println!("{:?}", iter.next());
}

这将输出：

Some([1, 2, 3, 4, 5])
Some([2, 3, 4, 5, 6])
None

注意：array_windows() 使用 clone 来多次生成元素，因此最适合用于引用和易于复制的类型。

- Ross MacArthur

1

请注意，如果不可被给定块大小整除，这将删除任何剩余条目。 - Bots Fab

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Shepmaster · Accepted Answer

可以使用Itertools::tuples从迭代器中获取一些块，最多可达到4个元组：

use itertools::Itertools; // 0.9.0

fn main() {
    let some_iter = vec![1, 2, 3, 4, 5, 6].into_iter();

    for (prev, next) in some_iter.tuples() {
        println!("{}--{}", prev, next);
    }
}

(playground)

1--2
3--4
5--6

如果您不知道您的迭代器是否完全适合块中，您可以使用Tuples::into_buffer来访问任何剩余部分：

use itertools::Itertools; // 0.9.0

fn main() {
    let some_iter = vec![1, 2, 3, 4, 5].into_iter();

    let mut t = some_iter.tuples();
    for (prev, next) in t.by_ref() {
        println!("{}--{}", prev, next);
    }
    for leftover in t.into_buffer() {
        println!("{}", leftover);
    }
}

(playground)

1--2
3--4
5

使用Itertools::tuple_windows，也可以使用4元组窗口：

use itertools::Itertools; // 0.9.0

fn main() {
    let some_iter = vec![1, 2, 3, 4, 5, 6].into_iter();

    for (prev, next) in some_iter.tuple_windows() {
        println!("{}--{}", prev, next);
    }
}

(playground)

1--2
2--3
3--4
4--5
5--6

如果您需要获取部分块/窗口，可以使用以下方式：