Box 与递归类型

你会学到什么

Box<T> 把值放到堆上,自己只占一个指针大小。
递归类型必须用 Box(或其他指针)打破“无限大小”。
Box 是最简单的智能指针,离开作用域自动释放堆内存。

最小示例

enum List {
    Cons(i32, Box<List>),
    Nil,
}

运行代码

cd examples
cargo run -p rt_22_box
cargo test -p rt_22_box

代码讲解

如果直接写 Cons(i32, List),编译器无法计算 List 的大小——它会无限嵌套。Box<List> 在栈上只是一个指针,大小固定,于是类型成立:

fn sum(list: &List) -> i32 {
    match list {
        Cons(value, rest) => value + sum(rest),
        Nil => 0,
    }
}

Box 还常用于:把大对象移到堆上避免昂贵的栈拷贝、或把不定大小的 trait 对象装箱(Box<dyn Trait>)。

常见错误

定义递归类型时漏了 Box:

enum List {
    Cons(i32, List), // ❌ recursive type has infinite size
    Nil,
}

把递归字段包进 Box 即可。

练习

给链表加一个 push_front 函数,返回新的 List。
实现一个二叉树类型,用 Box 存左右子节点。

小结

Box<T> 是“拥有所有权的堆指针”,让递归类型成为可能,也是其他智能指针的基础。

下一步

当一份数据需要多个所有者时,用 Rc。下一章学习引用计数。

完整示例代码

下面是 examples/22_box/ 的完整源码。无需 clone 仓库，直接在页面上阅读、复制、对照运行。

examples/22_box/src/main.rs

//! Box<T>：把数据放到堆上，支持递归类型。

/// 经典的 cons 链表，递归类型必须用 Box 才能确定大小。
#[derive(Debug, PartialEq)]
enum List {
    Cons(i32, Box<List>),
    Nil,
}

use List::{Cons, Nil};

/// 递归求和。
fn sum(list: &List) -> i32 {
    match list {
        Cons(value, rest) => value + sum(rest),
        Nil => 0,
    }
}

/// 计算链表长度。
fn len(list: &List) -> usize {
    match list {
        Cons(_, rest) => 1 + len(rest),
        Nil => 0,
    }
}

fn main() {
    let list = Cons(1, Box::new(Cons(2, Box::new(Cons(3, Box::new(Nil))))));
    println!("list = {list:?}");
    println!("sum = {}", sum(&list));
    println!("len = {}", len(&list));
}

#[cfg(test)]
mod tests {
    use super::*;

    fn sample() -> List {
        Cons(1, Box::new(Cons(2, Box::new(Cons(3, Box::new(Nil))))))
    }

    #[test]
    fn sums_list() {
        assert_eq!(sum(&sample()), 6);
        assert_eq!(sum(&Nil), 0);
    }

    #[test]
    fn measures_length() {
        assert_eq!(len(&sample()), 3);
        assert_eq!(len(&Nil), 0);
    }
}

examples/22_box/Cargo.toml

[package]
name = "rt_22_box"
version.workspace = true
edition.workspace = true
publish.workspace = true