rust - 展平嵌套结构

Question

寻找解决 Rust 中这个借用检查器/生命周期问题的智慧。我试图将一个通用的嵌套结构展平(变成一个 impl Iterator 或 Vec)。它可能离工作还有几个 &s 和 `s:

fn iter_els(prev_result: Vec<&El>) -> Vec<&El> {
    // Iterate over all elements from a tree, starting at the top-level element.
    let mut result = prev_result.clone();

    for el in prev_result {
        for child in &el.children {
            result.push(&child.clone());
        }
        result.extend(iter_els(&el.children));
    }
    result
}

您会注意到，这引发的直接异常是 iter_els 需要 refs 的 Vec，而不是 ref 本身。当直接解决这个问题时，其他问题就会浮出水面，就像在一场氧化但安全的古怪游戏中一样。

Playground

Answer 1

这个任务有多种解决方案。一种是将结果作为输出参数传递给函数:

fn iter_els<'el>(el_top: &'el El, result: &mut Vec<&'el El>) {
    result.push(el_top);
    for el in &el_top.children {
        iter_els(el, result);
    }
}

fn main() {
    // build top_el as you did
    let mut result = Vec::new();
    iter_els(&top_el, &mut result);
    println!("{:?}", result);
}

恕我直言，调整您原来的方法会导致更复杂的实现:

fn iter_els<'el>(prev_result: &Vec<&'el El>) -> Vec<&'el El> {
    // Iterate over all elements from a tree, starting at the top-level element.
    let mut result = prev_result.clone();

    for el in prev_result {
        for child in &el.children {
            result.push(&child);
        }
        result.extend(iter_els(&el.children.iter().collect()));
    }
    result
}

fn main() {
    // build top_el as you did
    println!("{:?}", iter_els(&vec![&top_el]));
}

或者:

fn iter_els<'el>(prev_result: &'el Vec<El>) -> Vec<&'el El> {
    // Iterate over all elements from a tree, starting at the top-level element.
    let mut result : Vec<_> = prev_result.iter().collect();

    for el in prev_result {
        for child in &el.children {
            result.push(child);
        }
        result.extend(iter_els(&el.children));
    }
    result
}

fn main() {
    // build top_el as you did
    println!("{:?}", iter_els(&vec![top_el]));
}

如您所见，第一种方法仅对不可变的 El 和一个单一结果 Vec 进行操作，而其他实现则无法绕过 clone 和 收集。

理想情况下，你会为​​你的树编写一个自定义的 Iterator，但我认为这可能会变得非常麻烦，因为这个迭代器必须以某种方式跟踪当前状态(也许可以证明我错了并证明它实际上很容易做到)。