rust - 将 Iterator<(A,B)> 拆分为 Iterator 和 Iterator

Question

我想拆分实现 Iterator<(A,B)> 的对象的输出分为两个实现 Iterator<A> 的对象和 Iterator<B> .由于其中一个输出的迭代次数可能比另一个多，因此我需要缓冲 Iterator<(A,B)> 的输出。 (因为我不能依赖 Iterator<(A,B)> 是可克隆的。)问题是迭代器可能是无限的，所以我不能简单地将迭代器的输出收集到两个缓冲区中并在两个缓冲区上返回迭代器。

看来我需要保留 A 的缓冲区和 B对象，只要其中一个缓冲区为空，我就会用 Iterator<(A,B)> 中的样本填充它目的。这意味着我需要两个可迭代结构，它们具有对输入迭代器的可变引用(因为它们都需要在输入上调用 next() 来填充缓冲区)，这是不可能的。

那么，有什么方法可以安全地完成这个任务吗？

Answer 1

这是可能的。正如您所确定的，您需要从两个句柄对基本迭代器的可变引用，这可以使用 a type with "internal mutability" 来实现。 ，即使用 unsafe 的一个内部代码公开一个安全的 API 来获取 &mut到可别名数据(即包含在 & 中)通过动态强制执行编译器通常在编译时在 unsafe 之外强制执行的不变量.

我假设您愿意将两个迭代器保持在一个线程上¹，因此，在这种情况下，我们需要一个 RefCell 。 .我们还需要能够访问 RefCell来自两个句柄，需要存储 &RefCell<...>或 Rc<RefCell<...>> .前者限制太多，因为它只允许我们在 RefCell 所在的栈帧中和栈帧下方使用一对迭代器。被创建，而我们希望能够自由地传递迭代器，所以 Rc 是的。

总而言之，我们基本上要存储一个 Rc<RefCell<Iterator<(A,B)>>> ，只有缓冲的问题。适合这里工作的工具是 RingBuf 因为我们想要在前面和后面进行高效的 p​​ush/pop。因此，我们共享的内容(即在 RefCell 中)可能如下所示:

struct SharedInner<A, B, It> {
    iter: It,
    first: RingBuf<A>,
    second: RingBuf<B>,
}

我们可以将实际共享的类型缩写为type Shared<A, B, It> = Rc<RefCell<SharedInner<A, B, It>>>; ，它允许我们定义迭代器:

struct First<A, B, It> {
    data: Shared<A, B, It>
}
impl Iterator<A> for First<A,B,It> {
    fn next(&mut self) -> Option<A> {
        // ...
    }
}

实现next首先要做的是获得 &mut到 SharedInner , 通过 self.data.borrow_mut(); .然后从中取出一个元素:检查正确的缓冲区，或者从 iter 中取出一个新元素。 (记得缓冲剩余的 B ):

let mut inner = self.data.borrow_mut();

inner.first.pop_front().or_else(|| {
    inner.iter.next().map(|(a,b)| {
        inner.second.push(b);
        a
    })
})

文档: RingBuf.pop_front , Option.or_else .

另一边的迭代器是类似的。总计:

use std::cell::RefCell;
use std::collections::{Deque, RingBuf};
use std::rc::Rc;

struct SharedInner<A, B, It> {
    iter: It,
    first: RingBuf<A>,
    second: RingBuf<B>
}

type Shared<A, B, It> = Rc<RefCell<SharedInner<A, B, It>>>;

struct First<A, B, It> {
    data: Shared<A, B, It>
}

impl<A,B, It: Iterator<(A,B)>> Iterator<A> for First<A, B, It> {
    fn next(&mut self) -> Option<A> {
        let mut inner = self.data.borrow_mut();

        // try to get one from the stored data
        inner.first.pop_front().or_else(|| 
            // nothing stored, we need a new element.
            inner.iter.next().map(|(a, b)| {
                inner.second.push(b);
                a
            }))
    }
}

struct Second<A, B, It> {
    data: Shared<A, B, It>
}
impl<A,B, It: Iterator<(A,B)>> Iterator<B> for Second<A,B,It> {
    fn next(&mut self) -> Option<B> {
        let mut inner = self.data.borrow_mut();

        inner.second.pop_front().or_else(|| {
            inner.iter.next().map(|(a, b)| {
                inner.first.push(a);
                b
            })
        })
    }
}

fn split<A, B, It: Iterator<(A,B)>>(it: It) -> (First<A, B, It>, 
                                                Second<A, B, It>) {
    let data = Rc::new(RefCell::new(SharedInner { 
        iter: it,
        first: RingBuf::new(),
        second: RingBuf::new(),
    }));

    (First { data: data.clone() }, Second { data: data })
}

fn main() {
    let pairs = range(1u32, 10 + 1).map(|x| (x, 1.0 / x as f64));

    let (mut first, mut second) = split(pairs);

    println!("first:");
    for x in first.by_ref().take(3) {
        println!("  {}", x);
    }

    println!("second:");
    for y in second.by_ref().take(5) {
        if y < 0.2 { break }
        println!("  {}", y);
    }

    let a = first.collect::<Vec<u32>>();
    let b = second.collect::<Vec<f64>>();

    println!("a {}\nb {}", a, b);
}

打印

first:
  1
  2
  3
second:
  1
  0.5
  0.333333
  0.25
  0.2
a [4, 5, 6, 7, 8, 9, 10]
b [0.166667, 0.142857, 0.125, 0.111111, 0.1]

playpen .

有多种方法可以对此进行优化，例如在 First 中获取时, 只缓冲剩下的 B如果 Second句柄存在。

¹ 如果您希望在单独的线程中运行它们，只需替换 RefCell用 Mutex 和 Rc用 Arc , 并添加必要的界限。