Ходят слухи, что если вы попросите новичков внедрить двусвязный список в Rust, они навсегда обойдут Rust стороной. Давайте разберемся в этом.
Прежде всего, само собой разумеется, что в отличие от C++ все итераторы `std` в Rust являются однонаправленными. Хотя Rust не одинок в этой игре, например, Python идет по тому же пути, первопричины находятся на расстоянии многих миль друг от друга. Во всем виноваты правила использования ссылок.
В любой момент времени у вас может быть либо одна изменяемая ссылка, либо любое количество неизменяемых ссылок.
Справедливо, если у вас есть двусвязный список, у вас будет по две ссылки на каждый элемент. Следовательно, они никогда не могут быть изменяемыми. Какой смысл в такой конструкции, если вы не можете даже пополнить его, не говоря уже об обновлении его значений.
По сути, именно поэтому на первый взгляд это безнадежное дело, и оно может разочаровать новичка. Тем не менее, еще не все потеряно. Как говорится, если вам это не нравится, вы не можете просто создать это. Так что давайте создадим это.
Справедливо будет сказать, что есть два возможных способа добиться этого. Самый простой, основанный на `Arc<RwLock<T>>` и более сложный. Несмотря на то, что первый вариант является довольно простой со словом "безопасный", которое может использоваться в обоих направлениях, это может быть не самый эффективный вариант, поскольку он накладывает избыточные ограничения. Все остальные базовые контейнеры не должны быть многопоточными "из коробки", поскольку это связано со счетчиком ссылок в `Arc` и мьютексом в `RwLock` . Это не способствует повышению производительности и является избыточным в случае однопоточного режима. Кроме того, полезно различать различные задачи и реализовывать их составным способом в соответствии с шаблоном SOLID.
Есть ли что-то еще, помимо `Arc<RwLock<T>>`? Да! `NonNull<T>` и `Pin<T>` всегда готовы помочь.
Что они такое?
`std::ptr::NonNull<T>` - это оболочка над необработанным указателем для сохранения ненулевого указателя на некоторые данные типа `T`, тогда как `std::pin::Pin<T>` дает обещание всегда сохранять данные в одном и том же месте в памяти. Конечно, последний - хитрый парень, но его внутренности не являются главной темой этой статьи. На данный момент было бы достаточно просто иметь в виду тот факт, что это предотвращает перемещение базовых данных в памяти. Грубо говоря, это похоже на `Box<T>`, но он может предотвратить разворачивание с помощью `.into_inner()`, чтобы сдержать обещание не разрешать перемещение данных (до тех пор, пока не сделать `!Unpin`).
Доказательство полезности пудинга заключается в том, что его едят.
Поскольку список находится под пристальным нашим вниманием, он и его элементы должны быть объявлены.
Идея прибегнуть к `NonNull<T>` заключается в том, чтобы избежать игры по правилам ссылок. Поскольку это не ссылка, она не учитывается, и существует только одно ограничение на ее использование. Это необходимость только предоставления надежных методов из модуля.
Элементы должны быть поддающимися созданию, не так ли?
Кроме того, они должны быть изменяемыми.
Кроме того, они должны быть повторяемы в обоих направлениях.
Теперь, когда объявлен `BiListElement<T>`, пришло время реализовать сам `BiList<T>`.
Чтобы не слишком раздувать эту статью, я собираюсь реализовать только одну функцию `push`, но этого определенно достаточно, чтобы уловить суть реализации любого другого обычного обработчика.
Очевидно, что это почти то же самое, что и в C / C++, с одной лишь разницей, что C / C++ полностью небезопасен, тогда как в Rust можно инкапсулировать проработанные / запутанные части, предоставляя посторонним только надежные методы.
Последнее, что осталось сделать, это поместить приведенный выше код в отдельный модуль, и дело сделано.
Возможно, отныне каждый читатель этой статьи согласится с утверждением, что реализовать это не так уж сложно, всего ~ 100 строк. Если вы знаете свое дело, вам потребуется не более 15 минут, чтобы реализовать двусвязный список. Единственное, что вам нужно сделать, чтобы это осуществить, - это освоиться с его работой, вот и все. Как только вы этому научитесь, это сослужит вам хорошую службу.
Статья на list-site.
