В качестве учебного проекта для Rust у меня есть очень простая (работающая, хотя и неполная) реализация односвязного списка. Объявление структур выглядит так:
type NodePtr<T> = Option<Box<Node<T>>>;
struct Node<T> {
data: T,
next: NodePtr<T>,
}
pub struct LinkedList<T> {
head: NodePtr<T>,
}
Реализация size
и push_front
была достаточно простой, хотя итеративное выполнение размера требовало некоторой «борьбы с проверкой заимствования».
Следующее, что я хотел попробовать, это добавить указатель tail
к структуре LinkedList
. для обеспечения эффективной работы push_back
. Здесь я столкнулся с небольшой стеной. Сначала я пытался использовать Option<&Box<Node<T>>>
, а затем Option<&Node<T>>
. И то, и другое привело к разбросу 'a
повсюду, но в конечном итоге все еще не удалось пообещать средству проверки срока службы, что tail
будет действительным.
С тех пор я пришел к предварительному выводу, что с этими определениями это невозможно: нет никакого способа гарантировать компилятору, что tail
будет допустимым в тех местах, где я считаю его допустимым. Единственный способ добиться этого — сделать так, чтобы все мои указатели были Rc<_>
или Rc<RefCell<_>>
, потому что это единственные безопасные способы, чтобы две вещи указывали на один и тот же объект (конечный узел).
Мой вопрос: это правильный вывод? В более общем плане: каково идиоматическое решение Rust для бесхозных указателей внутри структур данных? На мой взгляд, подсчет ссылок кажется ужасно тяжелым для чего-то такого простого, поэтому я думаю, что я что-то упускаю. (Или, возможно, я просто еще не настроил свой разум на безопасность памяти.)
Rc
. - person Chris Morgan   schedule 15.06.2015std::rc::Weak
в дополнение кRc
, так как я только что заметил, что первый существует. Спасибо за быстрый ответ! - person GrandOpener   schedule 15.06.2015