Интрузивные алгоритмы-эквиваленты в Rust
Я смотрю на язык программирования Rust и пытаюсь преобразовать свое мышление в C ++ в Rust. Общие структуры данных, такие как списки и деревья, ранее были реализованы с помощью указателей в C ++, и я не уверен, как реализовать точные эквиваленты в Rust. Структуры данных, которые меня интересуют, представляют собой навязчивые алгоритмы, аналогичные тем, которые можно найти в интрузивных библиотеках Boost, и они полезны для встроенного / системного программирования.
Пример связанного списка в Rust (Dlist) довольно прост, но он использует тип контейнера, где фактический тип находится внутри контейнера. Алгоритм навязчивости, который я ищу, немного наоборот: у вас есть основной тип, в котором узел списка вставляется или наследуется.
Кроме того, знаменитый связанный список в Linux является еще одним примером, где данные списка находятся в членах структур. Это похоже на вариант члена интрузивных алгоритмов Boost. Это позволяет вам использовать ваш тип в нескольких списках / деревьях много раз. Как это будет работать с Rust?
Поэтому я не уверен, как преобразовать такие шаблоны проектирования в Rust, к которым я привык в C / C ++. Кто-нибудь, кто имел успех, понимал это?
Решение
Руст хочет, чтобы вы думали о владении и жизни. Кому принадлежат участники и как долго они будут жить?
В вопросе о Dlist ответом является «контейнер». С навязчивыми алгоритмами нет четкого ответа. Члены одного списка могут быть повторно использованы в другом списке, в то время как другие уничтожаются первым списком. В конечном счете, вы, вероятно, хотите использовать подсчет ссылок (станд :: синхронизации :: Arc).
Другие решения
Я думаю, что есть два способа сделать что-то подобное в Rust. Давайте посмотрим на реализацию графиков, которые обычно используют навязчивые ссылки.
Первый подход основан на Rc<RefCell<Node>>, Вы можете найти более подробную информацию здесь: Графики и распределение арены
Второй подход основан на векторных индексах. Вы можете найти больше информации здесь: Моделирование графиков в Rust с использованием векторных индексов.
Я считаю, что второй подход лучше, но я не проводил никаких испытаний.