提问人:Julia Benginow 提问时间:11/16/2023 最后编辑:Julia Benginow 更新时间:11/17/2023 访问量:68
有没有办法在*不可克隆*的迭代器上实现笛卡尔乘积?
Is there a way to implement a cartesian product over iterators that are *not cloneable*?
问:
这个想法是,我想要迭代器的笛卡尔乘积,这些迭代器都是 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
我尝试了上述函数,以及一个自定义迭代器,该迭代器也很难使用借用检查器。
需要明确的是,我不想在任何时候调用收集。
答:
2赞
Chayim Friedman
11/17/2023
#1
可以采用许多策略。
首先,可能最有效的方法是将两个迭代器收集到 s 中,然后 it 并调用它。但是,如果迭代器非常大,这将不起作用。Vec
iter()
cartesian_product()
特别是,只需要一个迭代器,因此您可以收集其中较短的迭代器。Clone
另一种策略是拥有一个自定义特征,该特征具有超特征,但也可以克隆为 .有关如何执行此操作,请参阅如何克隆存储盒装特征对象的结构?。Iterator
dyn 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);
}
}
评论
Box<dyn Trait>
可克隆。