Как идиоматично написать связанный список с хвостовым указателем?

В качестве учебного проекта для 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 для бесхозных указателей внутри структур данных? На мой взгляд, подсчет ссылок кажется ужасно тяжелым для чего-то такого простого, поэтому я думаю, что я что-то упускаю. (Или, возможно, я просто еще не настроил свой разум на безопасность памяти.)


person GrandOpener    schedule 15.06.2015    source источник
comment
Ты прав; невозможно выразить циклы в безопасном Rust без совместного владения, как это предусмотрено такими вещами, как Rc.   -  person Chris Morgan    schedule 15.06.2015
comment
Это похоже на правильный ответ на мой вопрос, но я тоже не хочу совместной собственности. Думаю, я поиграюсь с std::rc::Weak в дополнение к Rc, так как я только что заметил, что первый существует. Спасибо за быстрый ответ!   -  person GrandOpener    schedule 15.06.2015
comment
На мой взгляд, подсчет ссылок кажется слишком тяжелым для такой простой вещи => когда вы начнете открывать глаза на вопросы владения (кому принадлежит каждый фрагмент данных), вы поймете, что ваше впечатление о простота ошибочна :)   -  person Matthieu M.    schedule 15.06.2015
comment
Ошибочный — это сильно сказано; возможно разные? Это сложное утверждение, потому что поддерживать инварианты хвостового указателя в односвязном списке это очень просто — это обычная тема CS в средней школе. Другое дело — математически доказать, что они сохраняются.   -  person GrandOpener    schedule 16.06.2015


Ответы (1)


Да, если вы хотите написать односвязный список с хвостовым указателем, у вас есть три варианта:

  • Безопасный и изменяемый: используйте NodePtr = Option<Rc<RefCell<Node<T>>>>
  • Безопасный и неизменный: используйте NodePtr = Option<Rc<Node<T>>>
  • Небезопасно и изменчиво: используйте tail: *mut Node<T>

*mut будет более эффективным, и не похоже, что Rc на самом деле предотвратит создание совершенно бессмысленных состояний (как вы правильно поняли). Это просто гарантирует, что они не вызывают segfaults (и с RefCell это все еще может вызывать сбои во время выполнения...).

В конечном счете, любой связанный список, более сложный, чем ванильный односвязный, имеет историю владения, которая слишком сложна для безопасного и эффективного кодирования в системе владения Rust (это не дерево). Я лично предпочитаю просто принять небезопасность в этот момент и полагаться на модульные тесты, чтобы добраться до финиша в целости и сохранности (зачем писать неоптимальную структуру данных...?).

person Alexis Beingessner    schedule 15.06.2015
comment
Это наверняка прозвучит как наводящий вопрос, но уверяю вас, я искренне пытаюсь понять дух Rust. Если от меня требуется принять небезопасность, чтобы писать нетривиальные, не древовидные структуры данных, почему бы мне просто не придерживаться C++, где у меня уже есть многолетний опыт? Подразумевается ли, что большинство хороших структур данных должны быть деревьями? Или есть еще какая-то часть истории, которую я упустил? - person GrandOpener; 15.06.2015
comment
Я бы сказал, что написание коллекций — это не то, чем большинство программ будут заниматься. Они получат готовые структуры данных (вероятно, только из std). Коллекции также по своей сути являются конструкцией низкого уровня. Вам нужно напрямую обращаться к системному распределителю, работать с частично инициализированными данными и поддерживать сложные инварианты. Особенно, если вам нужна производительность. Как только вы создадите свою коллекцию, она должна предоставить полностью безопасный интерфейс, и никому не нужно заботиться о внутренностях. Rust также накладывает большую нагрузку на фундаментальные библиотеки. Приложения получают большую выгоду от безопасности. - person Alexis Beingessner; 15.06.2015
comment
Что касается большинства хороших структур данных, это деревья: нет, большинство хороших структур данных — это массивы. :) - person Alexis Beingessner; 15.06.2015
comment
На заметку, почему не только C++: безопасность Rust модульная и независимая. Например, когда вы решите работать с неинициализированной памятью, вам не придется внезапно беспокоиться о нулевых указателях (к тому же Safe Rust в любом случае имеет действительно потрясающие 100% безопасные способы работы с неинициализированной памятью). Кроме того, вы тратите от 100% до 90% своего времени, не беспокоясь о небезопасности вообще, в зависимости от типа кода, над которым вы работаете. С++? Небезопасность носит всеобъемлющий характер. (Только что понял, что эти ответы могут вас не пинговать, поэтому скопируйте @GrandOpener) - person Alexis Beingessner; 15.06.2015