rust - 创建链表时意外的堆栈溢出

Question

我一直在尝试通过扩展 Rust tutorial 提供的链表示例来找到绕过 Rust 的方法。

我已经编写了一个将通用向量转换为链表的构造函数，但如果向量足够大，使用它会导致堆栈溢出。这让我感到困惑，因为我认为链表是在堆上创建的，因为列表中的每个元素都有一个包含下一个元素的自有框。

Rust 是我使用过的第一种语言，我不得不担心内存管理，所以我有点迷茫。一个解释将不胜感激，一个双重的解决方案。谢谢!

我的代码只截断为相关的 gubbins:

use std::mem::swap;

enum ListItem<T> { 
    Node(T, Box<ListItem<T>>), 
    Cap 
}

impl <T> ListItem<T> {
    fn append(&mut self, x: T) {
        match *self {
            Node(_, ref mut a@box Cap) => *a = box Node(x, box Cap),
            Node(_, ref mut a@box Node(_, _)) => a.append(x),
            Cap => {
                let mut n = Node(x, box Cap);
                swap(&mut n, self);
            }
        };
    }
}

impl <T: Clone> ListItem<T> {
    fn new_from_vec(x: &mut Vec<T>) -> ListItem<T>{
        let mut l = Cap;
        for v in x.iter() {
            l.append((*v).clone());
        }
        return l;
    }
}

fn main() {
    let mut v: Vec<int> = vec![];

    for n in range(1i, 500001) {
        v.push(n);
    }

    println!("Done creating vector.");

    let x = ListItem::new_from_vec(&mut v);

    println!("Done creating linked list.");
}

它打印Done creating vector. , 但随后打印 task '<main>' has overflowed its stack在进入下一个之前 println! .

Answer 1

堆栈溢出通常是递归过深的标志。如果仔细查看代码，您可能会发现递归:

impl <T> ListItem<T> {
    fn append(&mut self, x: T) {
        match *self {
            Node(_, ref mut a@box Cap) => *a = box Node(x, box Cap),
            Node(_, ref mut a@box Node(_, _)) => a.append(x),       // <---
            Cap => {
                let mut n = Node(x, box Cap);
                swap(&mut n, self);
            }
        };
    }
}

这意味着对于每个已经在列表中的元素，您在堆栈上创建一个新的函数框架(除非编译器优化它)，对于足够数量的元素，它会确定性地溢出堆栈。

为避免溢出，您可以切换到迭代版本(带循环)。