Есть ли разница между связанным списком, реализованным с помощью Box <T>и & 'a T? - PullRequest
Новая
       26

Есть ли разница между связанным списком, реализованным с помощью Box <T>и & 'a T?

1 голос
/ 14 марта 2019

Я пытаюсь понять разницу между этими двумя реализациями связанного списка.Эта первая версия представлена ​​в книге Rust с использованием Box<T>: 

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

Это другая реализация, о которой я думал: 

enum List<'a> {
    Cons(i32, &'a List<'a>),
    Nil,
}

Есть ли какое-то важное отличие?между двумя, или они эквивалентны в этом случае?

1 Ответ

4 голосов
/ 14 марта 2019

Любая из этих реализаций будет технически работать, но есть некоторые большие компромиссы.

A Box выделяет в куче, а затем владеет данными. Это довольно удобно и гибко по сравнению с управлением ссылками.

Чтобы построить список второго типа, используя ссылки &, вам нужно где-то владеть данными. Таким образом, вам нужно управлять произвольным количеством узлов и следить за тем, чтобы они не выходили за рамки. Это может быть очень ограничительным. Например, не очень легко создать функцию, которая создает список и затем возвращает его: 

fn make_list<'a>() -> List<'a> {
    let node1 = List::Nil;
    let node2 = List::Cons(1, &node1);
    let node3 = List::Cons(2, &node2);
    node3
    // node1 and node2 go out of scope here...
}

Это не будет работать, потому что оно ссылается на локальные переменные функции, которые выходят из области видимости, когда функция возвращается. Версия, использующая Box, будет работать, потому что Box становится владельцем данных.

...