构造大树时“线程'

'已溢出其堆栈”

我实现了一个树结构：

use std::collections::VecDeque;
use std::rc::{Rc, Weak};
use std::cell::RefCell;

struct A {
    children: Option<VecDeque<Rc<RefCell<A>>>>
}

// I got thread '<main>' has overflowed its stack
fn main(){
    let mut tree_stack: VecDeque<Rc<RefCell<A>>> = VecDeque::new();

    // when num is 1000, everything works
    for i in 0..100000 {
        tree_stack.push_back(Rc::new(RefCell::new(A {children: None})));
    }

    println!("{:?}", "reach here means we are not out of mem");
    loop {
        if tree_stack.len() == 1 {break;}

        let mut new_tree_node = Rc::new(RefCell::new(A {children: None}));
        let mut tree_node_children: VecDeque<Rc<RefCell<A>>> = VecDeque::new();

        // combine last two nodes to one new node
        match tree_stack.pop_back() {
            Some(x) => {
                tree_node_children.push_front(x);
            },
            None => {}
        } 
        match tree_stack.pop_back() {
            Some(x) => {
                tree_node_children.push_front(x);
            },
            None => {}
        } 

        new_tree_node.borrow_mut().children = Some(tree_node_children);
        tree_stack.push_back(new_tree_node);
    }
}

婴儿围栏链接 http://is.gd/0RF6SR

但它崩溃了

thread '<main>' has overflowed its stack

我该如何解决这个问题？

您遇到的问题是因为您有一个巨大的节点链表。当该列表被删除时，第一个元素首先尝试释放结构体的所有成员。这意味着第二个元素执行相同的操作，依此类推，直到列表末尾。这意味着您将拥有一个与列表中元素数量成正比的调用堆栈！

这是一个小复制品：

struct A {
    children: Option<Box<A>>
}

fn main() {
    let mut list = A { children: None };

    for _ in 0..1_000_000 {
        list = A { children: Some(Box::new(list)) };
    }
}

修复方法如下：

impl Drop for A {
    fn drop(&mut self) {
        if let Some(mut child) = self.children.take() {
            while let Some(next) = child.children.take() {
                child = next;
            }
        }
    }
}

此代码使用迭代覆盖默认的递归删除实现。它撕裂了children从节点中取出，用终端项替换它（None）。然后它允许节点正常删除，但不会有递归调用。

代码有点复杂，因为我们不能放弃自己，所以我们需要跳一段两步舞来忽略第一个项目，然后吃掉所有的孩子。

也可以看看：

• 如何为结构的可变引用中的字段交换新值？ https://stackoverflow.com/q/27098694/155423
• 如何移出作为选项的结构体字段？ https://stackoverflow.com/q/52031002/155423