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