我正在尝试在Rust中对树结构进行深度优先迭代。我以为我对此有一个非常好的简洁解决方案，但我无法对其进行编译。从概念上讲，这很简单:遍历子级，首先获得每个子级的深度迭代器，然后将它们展平，然后将当前节点的元数据迭代器链接到该子级。
#[derive(Debug, Eq, PartialEq)]
struct Node {
metadata: Vec<i64>,
children: Vec<Box<Node>>,
}
impl Node {
fn depth_first_metadata_iter(&self) -> impl Iterator<Item = &i64> + '_ {
self.children
.iter()
.map(|child| child.depth_first_metadata_iter())
.flatten()
.chain(self.metadata.iter())
}
}
fn main() {
let tree = Node {
metadata: vec![1, 2, 3],
children: vec![
Box::new(Node {
metadata: vec![4, 5],
children: vec![],
}),
Box::new(Node {
metadata: vec![6, 7],
children: vec![],
}),
],
};
println!(
"{:?}",
tree.depth_first_metadata_iter().collect::<Vec<&i64>>()
);
}
但是，当我对此进行编译时，出现以下错误:
error[E0275]: overflow evaluating the requirement `impl std::iter::Iterator`
|
= help: consider adding a `#![recursion_limit="128"]` attribute to your crate
(您可以在playground上自行检查)。
这是有道理的，因为我正在
depth_first_metadata_iter内进行递归调用，该调用返回嵌套的迭代器，但是如果类似这样的代码可以在无需实现自定义迭代器的情况下工作，那将是非常不错的。我所见过的
E0275错误的所有其他解决方案(例如this，this，this)似乎都在策略上将类型注释放置在某处-在这里是否可能这样，还是我尝试“不可能”？ 最佳答案
取决于您的意思。这是相似的，可以运行，并且不需要自定义迭代器。从而满足您的所有要求:
fn depth_first_metadata_iter(&self) -> Box<Iterator<Item = &i64> + '_> {
Box::new({
self.children
.iter()
.flat_map(|child| child.depth_first_metadata_iter())
.chain(self.metadata.iter())
})
}
从本质上讲，这是与图1中所示相同的问题。
让自己陷入编译器的困境。您的原始代码说:“我将返回一个具体的迭代器类型，但我不会说确切的类型”。编译器仍然必须能够找出该类型，所以让我们成为编译器:
let a = self.children.iter();
// std::slice::Iter<'_, Box<Node>>
let cls = |child| child.depth_first_metadata_iter();
// Fn(&Box<Node>) -> ?X?
let b = a.flat_map(cls);
// FlatMap<Iter<'_, Box<Node>>, ?X?, Fn(&Box<Node>) -> ?X?>
let d = self.metadata.iter();
// std::slice::Iter<'_, i64>
b.chain(d);
// Chain<FlatMap<Iter<'_, Box<Node>>, ?X?, Fn(&Box<Node>) -> ?X?>, Iter<'_, i64>>
这个最终结果是返回值，因此我们得到了等式:
Chain<FlatMap<Iter<'_, Box<Node>>, ?X?, Fn(&Box<Node>) -> ?X?>, Iter<'_, i64>> === ?X?
AFAIK，无法执行类型级代数来解决
?X?，因此会出现错误。将返回类型更改为盒装特征对象会使所需的所有逻辑短路，并强制使用特定的具体类型。
我认为情况并非如此。如果是这样，那意味着代数是可解的，但是编译器不够聪明来解决它。虽然在其他情况下无疑是正确的，但我认为并非如此。
我认为这不是一个很好的解决方案，因为这将涉及很多微小的分配。我假设(但尚未测试)使用堆栈数据结构的自定义迭代器会更有效。
一个中间立场是建立整个节点集:
impl Node {
fn depth_first_metadata_iter(&self) -> impl Iterator<Item = &i64> + '_ {
self.x().into_iter()
}
fn x(&self) -> Vec<&i64> {
fn x_inner<'a>(node: &'a Node, v: &mut Vec<&'a i64>) {
for c in &node.children {
x_inner(c, v)
}
v.extend(&node.metadata);
}
let mut v = Vec::new();
x_inner(self, &mut v);
v
}
}