Подходит ли Rust для структур данных и алгоритмов?
Чтобы пользоваться ими, очень: стандартные коллекции быстрые и хорошо документированы, sort сортирует устойчиво, а безопасный Rust исключает висячие указатели и гонки данных ещё на этапе компиляции, без сборщика мусора. Писать структуры на указателях в нём сложнее, чем на C или Java, потому что владение не допускает общих изменяемых ссылок, если вы явно не выберете Rc и RefCell, а двусвязный список или дерево со ссылками на родителя состоят как раз из таких ссылок. Эта сложность и есть урок: когда вы умеете писать их на Rust, вы точно знаете, кто чем владеет.
Какие коллекции Rust каким структурам данных соответствуют?
Vec<T> представляет собой динамический массив и ваш стек, VecDeque<T> устроен как кольцевой буфер и служит очередью, HashMap и HashSet построены на хеш-таблицах (по умолчанию с SipHash, который защищает от намеренных коллизий ценой некоторой потери скорости), BTreeMap и BTreeSet устроены как упорядоченные B-деревья, BinaryHeap<T> реализует max-кучу, а LinkedList<T> представляет собой двусвязный список, который вам редко понадобится вместо Vec или VecDeque. Типа для префиксного дерева или графа нет: их вы пишете сами.
Почему связный список так сложно написать на Rust?
Потому что у каждого значения ровно один владелец. Односвязный список вписывается в это правило: каждый узел владеет следующим через Option<Box<Node>>. Двусвязный список или дерево со ссылками на родителя не вписываются, поскольку к каждому узлу ведут два указателя, поэтому вы берёте Rc<RefCell<Node>> с Weak для обратных ссылок или храните узлы в Vec и связываете их по индексам. Руководство Learning Rust With Entirely Too Many Linked Lists появилось именно потому, что очень многие застревают на этом месте.
Как получить min-кучу в Rust?
BinaryHeap<T> реализует max-кучу, поэтому оборачивайте каждый элемент в std::cmp::Reverse: добавьте Reverse(x), и первым выйдет наименьший x. Для алгоритма Дейкстры добавляйте Reverse((distance, node)), и кортеж будет сравниваться сначала по расстоянию. Когда вы сами напишете кучу на втором шаге, развернуть её порядок станет очевидным делом.
Какие курсы этого пути не преподаются на Rust?
Три: динамическое программирование и серия по интервью на Python преподаются на Python, а битовые операции на C++. Они перечислены после шагов, каждый со ссылкой, которая открывает курс на его собственном языке. Таблица мемоизации в Rust представляет собой Vec или HashMap, а переполнение целого числа в отладочной сборке вызывает панику, поэтому битовый трюк, который рассчитывает на циклическое переполнение, прописывает это явно через wrapping_add или wrapping_mul.
Нужно ли знать Rust, прежде чем начинать этот путь?
Как минимум владение, заимствование, структуры, перечисления и Option; Box и трейты пригодятся. Если это для вас новое, курс Rust от Coddy сначала бесплатно доведёт вас до этого уровня, а этот путь начинается там, где он заканчивается.
