首页 文章

创建链接列表时意外的堆栈溢出

提问于
浏览 次
1

我一直试图通过扩展Rust tutorial提供的链表示例来找到我的方法 .

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

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. ，但在进入下一个 println! 之前打印 task '<main>' has overflowed its stack .

rust

2 回答

  • 2

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

    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);
            }
        };
    }
}

    这意味着对于列表中已有的每个元素，您将在堆栈上创建一个新的函数框架（除非编译器对其进行优化），对于足够数量的元素，这将确定性地溢出堆栈 .

    为避免溢出，您可以切换到迭代版本（带循环） .

    回复于
  • 2

    不幸的是Rust没有tail call optimizations这意味着你不能依赖递归进行迭代繁重的操作 .

    根据this ticket，他们似乎不太可能在将来添加此功能 .

    我担心你必须将你的代码转换为常规循环 .

    回复于

相关问题