재귀자료 구조에서의 Box

재귀 데이터나 동적크기의 데이터 타입은 Box타입을 사용해야 합니다:

#[derive(Debug)]
enum List<T> {
    Cons(T, Box<List<T>>),
    Nil,
}

fn main() {
    let list: List<i32> = List::Cons(1, Box::new(List::Cons(2, Box::new(List::Nil))));
    println!("{list:?}");
}
힙listCons1Cons2Nil스택

  • 만일 Box를 사용하지 않고 List에 직접 List를 포함하려고 시도한다면, 컴파일러는 구조체의 고정 크기를 계산할 수 없습니다. 컴파일러가 보기에 무한대의 크기로 보일 것입니다.

  • Box는 일반 포인터와 크기가 같기 때문에 크기를 계산하는 데 문제가 없습니다. 다만 힙에 위치한 List의 다음 요소를 가리킬 뿐입니다.

  • List 정의에서 Box를 제거하면 어떤 컴파일러 에러가 나오는지 같이 살펴보세요. “Recursive with indirection”라는 메시지를 보면, 값을 직접 저장하는 대신 Box나 비슷한 다른 종류의 참조 타입이 필요하다는 힌트를 얻을 수 있습니다.