rust 将RecursiveStruct1转换为RecursiveStruct2而不使用递归？

nwo49xxi 于 2023-11-19 发布在其他

关注(0)|答案(2)|浏览(99)

pub struct Source {
    pub name: String,
    pub child: Vec<Source>
}
pub struct Target {
    pub id: String,
    pub nested: Vec<Target>
}

字符串
我可以使用递归轻松地将Source转换为Target，但这并不安全，因为Source结构是用户输入的数据，它可能导致堆栈溢出。
有没有简单的方法可以将Source转换为Target，而无需递归和克隆？我尝试过DFS，但由于所有权问题而失败。

rust

来源：https://stackoverflow.com/questions/77465368/convert-recursivestruct1-to-recursivestruct2-without-recursion

2条答案

按热度按时间

wkftcu5l1#

对于所有的递归算法，你可以通过自己保留一个手动堆栈来迭代：

impl From<Source> for Target {
    fn from (other: Source) -> Target {
        let mut stack = vec![];
        let mut t = Target {
            id: other.name,
            nested: vec![],
        };
        let mut it = other.child.into_iter();
        loop {
            if let Some (c) = it.next() {
                // "Recurse" to process children
                stack.push ((t, it));
                t = Target {
                    id: c.name,
                    nested: vec![],
                };
                it = c.child.into_iter();
            } else if let Some ((mut t1, it1)) = stack.pop() {
                // No more children, "return" from the current recursion level
                t1.nested.push (t);
                t = t1;
                it = it1;
            } else {
                // Stack is empty, we're done, return
                return t;
            }
        }
    }
}

字符串
Playground

赞(0）回复(0）举报 2023-11-19

c86crjj02#

来自@Jmb的答案是正确的，但有时使用递归解决方案更方便。在这种情况下，如果数据太大，可以使用stacker来增长堆栈。

赞(0）回复(0）举报 2023-11-19