有没有办法在*不可克隆*的迭代器上实现笛卡尔乘积?

Is there a way to implement a cartesian product over iterators that are *not cloneable*?

提问人:Julia Benginow 提问时间:11/16/2023 最后编辑:Julia Benginow 更新时间:11/17/2023 访问量:68

问:

这个想法是,我想要迭代器的笛卡尔乘积,这些迭代器都是 Box<dyn...>,因为我有一个函数,它返回不同类型的迭代器,其中一些必须通过笛卡尔乘积函数运行。但是,鉴于 Box<dyn ..>是不可克隆的。有什么办法可以解决这个问题吗?

代码:

fn cartesian_product<'a>(iterators: &'a mut Vec<Box<dyn Iterator<Item = Sexp> + 'a>>) -> Box<dyn Iterator<Item = Vec<Sexp>> + 'a> {
        if let Some(iter) = iterators.pop() {
            let current_iterator = iter.map(|val| vec![val]);
            let child_iterators = (Self::cartesian_product(iterators));
            let combined_iterators = current_iterator.flat_map(move |vec| { 
                
                let val = child_iterators.map(move |item| 
                    {
                        let mut vec_cloned = vec.clone();
                        let mut item_cloned = item.clone();
                        item_cloned.append(&mut vec_cloned);
                        item_cloned
                    });
                val 
            });
            Box::new(combined_iterators)
        }
        else {
            Box::new(std::iter::empty())
        }
    }

该错误,目前:

cannot move out of `child_iterators`, a captured variable in an `FnMut` closure
move occurs because `child_iterators` has type `Box<dyn Iterator<Item = Vec<sexp::Sexp>>>`, which does not implement the `Copy` trait

我尝试了上述函数,以及一个自定义迭代器,该迭代器也很难使用借用检查器。

需要明确的是,我不想在任何时候调用收集。

rust iterator 借用检查器 笛卡尔积

评论

0赞 Chayim Friedman 11/17/2023
您可以使 Box<dyn Trait> 可克隆

答:

2赞 Chayim Friedman 11/17/2023 #1

可以采用许多策略。

首先,可能最有效的方法是将两个迭代器收集到 s 中,然后 it 并调用它。但是,如果迭代器非常大,这将不起作用。Veciter()cartesian_product()

特别是,只需要一个迭代器,因此您可以收集其中较短的迭代器。Clone

另一种策略是拥有一个自定义特征,该特征具有超特征,但也可以克隆为 .有关如何执行此操作,请参阅如何克隆存储盒装特征对象的结构?Iteratordyn Trait

1赞 Jakub Dóka 11/17/2023 #2

非常被诅咒的代码,但有效

use std::iter;

struct IterRestart<I: Iterator> {
    original: I,
    current: iter::Peekable<I>,
}

impl<I: Clone + Iterator> IterRestart<I>
where
    I::Item: Clone,
{
    fn new(iter: I) -> Self {
        Self {
            original: iter.clone(),
            current: iter.peekable(),
        }
    }

    fn boxed<'a>(iter: I) -> Box<dyn CartesianIterator<Item = I::Item> + 'a>
    where
        I: 'a,
    {
        Box::new(Self::new(iter))
    }
}

impl<I: Iterator> Iterator for IterRestart<I> {
    type Item = I::Item;

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

impl<I: Clone + Iterator> CartesianIterator for IterRestart<I>
where
    I::Item: Clone,
{
    fn restart(&mut self) {
        self.current = self.original.clone().peekable();
    }

    fn current(&mut self) -> Option<Self::Item> {
        self.current.peek().cloned()
    }
}

trait CartesianIterator: Iterator {
    fn restart(&mut self);
    fn current(&mut self) -> Option<Self::Item>;
}

fn cartesian_product<E: Clone>(
    mut iterators: Vec<Box<dyn CartesianIterator<Item = E>>>,
) -> impl Iterator<Item = Vec<E>> {
    let mut buffer = iterators
        .iter_mut()
        .filter_map(|iter| iter.current())
        .collect::<Vec<_>>();
    iter::from_fn(move || {
        if buffer.len() != iterators.len() {
            return None;
        }

        iterators
            .iter_mut()
            .enumerate()
            .rev()
            .find_map(|(i, iter)| {
                iter.next();
                let no_current = iter.current().is_none();
                if no_current {
                    iter.restart();
                }
                buffer[i] = iter.current().unwrap();
                (!no_current).then_some(())
            })?;

        Some(buffer.clone())
    })
}

fn main() {
    let nums = 0..4;
    let stepped_nums = (0..8).step_by(2);
    let eh = vec![0, 17, 26];
    let mut iter = cartesian_product(vec![
        IterRestart::boxed(nums),
        IterRestart::boxed(stepped_nums),
        IterRestart::boxed(eh.into_iter()),
    ]);

    while let Some(pair) = iter.next() {
        println!("{:?}", pair);
    }
}