将迭代器<(A，B)>拆分为迭代器和迭代<A>器<B>

Question

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

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

那么，有什么方法可以安全地实现这一点吗？

Answer 1

这是可能的。正如您所确定的，您需要从两个句柄对基本迭代器进行可变引用，这可以使用具有"内部可变性"的类型，即在内部使用unsafe代码，通过动态强制编译器在unsafe外部的编译时通常强制执行的不变量，向可别名数据（即包含在&中）公开安全的API以获取&mut。

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

总之，我们基本上要存储一个Rc<RefCell<Iterator<(A,B)>>>，只是缓冲的问题。这里适合这项工作的工具是RingBuf，因为我们希望在前部和后部进行高效的推/弹出。因此，我们共享的东西（即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，首先要做的是通过self.data.borrow_mut();将&mut获取到SharedInner。然后从中取出一个元素：检查右边的缓冲区，或者从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中提取时，如果存在Second句柄，则仅缓冲剩余的B。

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