展开嵌套结构

Question

我正在寻找有关在Rust中解决borrow-checker / lifetime问题的智慧。我正在尝试将通用嵌套结构（转换为impl迭代器或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期望的是一个Vec的引用，而不是一个引用本身。直接解决这个问题时，其他问题也会出现，就像玩氧化但安全的打地鼠游戏一样。

Playground

- Turtles Are Cute

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和collect。理想情况下，您可以为树编写自定义Iterator，但我认为这可能会变得非常麻烦，因为这个迭代器必须以某种方式跟踪当前状态（也许可以证明我是错的，并展示它其实很容易）。

- phimuemue