or:

and:

LINUX

Language

Kernel

Package

Book

Test

Forum

iakovlev.org

Связные списки в Rust

Это перевод документации, которая лежит тут

Исходники к данной статье можно взять тут

Реализация связных списков на расте - не самая простая задача. Для этого нужно разбираться в таких аспектах языка, как:
различные типы указателей: &, &mut, Box, Rc, Arc, *const, *mut
ownership, borrowing, inherited mutability, interior mutability, Copy
struct, enum, fn, pub, impl, use, ...
переключатели, дженерики, деструкторы
тестирование
unsafe

Начнем с того, что создадим проект:

 cargo new lists
 cd lists

Вообще говоря, для коллекций больше подходит вектор, а использование связного списка необходимо не так часто, например, если вы пишете модуль ядра операционной системы или реализуете задачу, в которой присутствует большое количество слияний и разбиений списков. По сравнению с массивами связный список имеет тот недостаток, что ему нужно дополнительное место в памяти для хранения указателей. В связных списках также нужно продумывать стратегию освобождения памяти, особенно в случае, когда сама нода имеет большой размер. В массивах мы можем использовать слайсы, в связных списках не можем. Вы должны отдавать себе отчет в том, на что вы идете и что вам прийдется реализовать для того, чтобы ваш связный список по-настоящему работал.
Связные списки - подходящий обьект для функционального программирования, можно например использовать рекурсию и неограниченно увеличивать размер самого списка. Для совершения различных операций над связными списками, такими, как фильтрация, реверс, конкатенация, используются итераторы.

First.rs

У нас будет несколько версий, первую мы положим в first.rs. Для этого в файле lib.rs мы обьявим публичный доступ к нему:


 // in lib.rs
 pub mod first;

Связный список - это набор нод, которые связаны друг с другом. Определим в нашем списке ноду, которая будет хранить число. Будем использовать растовский тип Box. В данном случае растовский стандартный тип Box<T> - тип указателя для выделения памяти. Например


 let x = Box::new(5);

Здесь мы фактически создаем рекурсивную структуру данных


 enum List {
     Cons(T, Box<List>),
     Nil,
 }

которую можем использовать так:


 fn main() {
     let list: List<i32> = List::Cons(1, Box::new(List::Cons(2, Box::new(List::Nil))));
     println!("{:?}", list);
 }

В результате получим вывод


 Cons(1, Box(Cons(2, Box(Nil))))

Определим наш список с помощью бокса


 // in first.rs
 
 // pub says we want people outside this module to be able to use List
 pub enum List {
     Empty,
     Elem(i32, Box<List>),
 }

Схематично связный список можно представить следующим образом

 [ptr] -> (Elem A, ptr) -> (Elem B, ptr) -> (Elem C, *null*)

У нас есть указатель на начальную ноду, каждая нода хранит в себе число и указатель на следующую ноду. Если мы хотим разбить список на 2 списка

 [ptr] -> (Elem A, ptr) -> (Elem B, *null*)
 [ptr] -> (Elem C, *null*)

Определим базовые структуры. Сделаем публичную структуру List, а детали реализации сделаем приватными:


 pub struct List {
     head: Link,
 }
 
 enum Link {
     Empty,
     More(Box<Node>),
 }
 
 struct Node {
     elem: i32,
     next: Link,
 }

Имплементация списка


 impl List {
     // TODO, make code happen
 }

Вспомним, как в расте обьявляется функция


 fn foo(arg1: Type1, arg2: Type2) -> ReturnType {
     // body
 }

Для начала нам надо проинициализировать список. Поскольку детали мы сделали приватными, напишем внутри имплементации списка функцию


 impl List {
     pub fn new() -> Self {
         List { head: Link::Empty }
     }
 }

Здесь Self - это алиас для создаваемого обьекта. В этой функции мы не ставим return или точку с запятой, это такой стиль в расте - функция и так вернет последнее выражение. Теперь нам нужно написать какой-нибудь метод для списка


 fn foo(self, arg2: Type2) -> ReturnType {
     // body
 }

При этом алиас может выступать в одной из трех форм


 self
 &mut self
 &self

Первая форма вернет значение, второе - изменяемую ссылку. третья - глобальную ссылку. В первом случае с возвращаемым значением мы можем делать все что угодно - перемещать, удалять, изменять и т.д. При этом мы создаем копию обьекта, что ни есть хорошо. Вторая форма копию не создает, но позволяет с обьектом делать также все, что угодно. Третья форма не позволяет изменить обьект, она позволяет прочитать его.

Напишем метод, который добавляет ноду в список.


 use std::mem;
 
 impl List { 
 pub fn push(&mut self, elem: i32) {
     let new_node = Box::new(Node {
         elem: elem,
         next: mem::replace(&mut self.head, Link::Empty),
     });
 
     self.head = Link::More(new_node);
   }
 }

Здесь мы создаем новую ноду, добавляем ее в начало списка, но перед этим мы должны поменять указатель на следующую ноду.

Теперь напишем второй метод - pop - удаляющий ноду. В отличие от push, нам нужно что-то вернуть из этой функции. У нас возможны два варианта - список пустой и не пустой.


 pub fn pop(&mut self) -> Option<i32> {
     //TODO
 }

Option<T> - нумератор произвольного типа, т.е. фактически это дженерик


 pub fn pop(&mut self) -> Option<i32> {
     match mem::replace(&mut self.head, Link::Empty) {
         Link::Empty => None,
         Link::More(boxed_node) => {
             let node = *boxed_node;
             self.head = node.next;
             Some(node.elem)
         }
     }
 }

Мы проверяем, пустой ли список. Если пустой, мы возвращаем None, если не пустой, удаляем головную ноду, перемещаем указатель головы на следующую ноду и возвращаем ее.

Теперь нам надо протестировать код.


 // in first.rs
 
 mod test {
     #[test]
     fn basics() {
         // TODO
     }
 }

Для начала выполним команду

 cargo test

Пока тест ничего не делает. Добавим в него макрос assert_eq!


 #[cfg(test)]
 mod test {
     use super::List;
     
     #[test]
     fn basics() {
         let mut list = List::new();
 
         // Check empty list behaves right
         assert_eq!(list.pop(), None);
 
         // Populate list
         list.push(1);
         list.push(2);
         list.push(3);
 
         // Check normal removal
         assert_eq!(list.pop(), Some(3));
         assert_eq!(list.pop(), Some(2));
 
         // Push some more just to make sure nothing's corrupted
         list.push(4);
         list.push(5);
 
         // Check normal removal
         assert_eq!(list.pop(), Some(5));
         assert_eq!(list.pop(), Some(4));
 
         // Check exhaustion
         assert_eq!(list.pop(), Some(1));
         assert_eq!(list.pop(), None);
     }
 }

Следующий шаг - удаление всего списка. Для этого в расте есть деструкторы. Тип в расте имеет деструктор, если в нем имплементирован трэйт(типаж) по имени Drop


 pub trait Drop {
    fn drop(&mut self);
 }

Если в списке три ноды

 list -> A -> B -> C

Если мы попытаемся удалить список, будет запущен рекурсивный механизм, и это плохая идея. Вместо этого варианта мы напишем свою собственную версию Drop


 impl Drop for List {
     fn drop(&mut self) {
         let mut cur_link = mem::replace(&mut self.head, Link::Empty);
         while let Link::More(mut boxed_node) = cur_link {
             cur_link = mem::replace(&mut boxed_node.next, Link::Empty);
         }
     }
 }

Теперь можно подвести итог и представить первую версию кода first.rs:


 use std::mem;
 
 pub struct List {
     head: Link,
 }
 
 enum Link {
     Empty,
     More(Box<Node>),
 }
 
 struct Node {
     elem: i32,
     next: Link,
 }
 
 impl List {
     pub fn new() -> Self {
         List { head: Link::Empty }
     }
 
     pub fn push(&mut self, elem: i32) {
         let new_node = Box::new(Node {
             elem: elem,
             next: mem::replace(&mut self.head, Link::Empty),
         });
 
         self.head = Link::More(new_node);
     }
 
     pub fn pop(&mut self) -> Option<i32> {
         match mem::replace(&mut self.head, Link::Empty) {
             Link::Empty => None,
             Link::More(node) => {
                 let node = *node;
                 self.head = node.next;
                 Some(node.elem)
             }
         }
     }
 }
 
 impl Drop for List {
     fn drop(&mut self) {
         let mut cur_link = mem::replace(&mut self.head, Link::Empty);
         while let Link::More(mut boxed_node) = cur_link {
             cur_link = mem::replace(&mut boxed_node.next, Link::Empty);
         }
     }
 }
 
 #[cfg(test)]
 mod test {
     use super::List;
 
     #[test]
     fn basics() {
         let mut list = List::new();
 
         // Check empty list behaves right
         assert_eq!(list.pop(), None);
 
         // Populate list
         list.push(1);
         list.push(2);
         list.push(3);
 
         // Check normal removal
         assert_eq!(list.pop(), Some(3));
         assert_eq!(list.pop(), Some(2));
 
         // Push some more just to make sure nothing's corrupted
         list.push(4);
         list.push(5);
 
         // Check normal removal
         assert_eq!(list.pop(), Some(5));
         assert_eq!(list.pop(), Some(4));
 
         // Check exhaustion
         assert_eq!(list.pop(), Some(1));
         assert_eq!(list.pop(), None);
     }
 }

Second.rs

Далее, во вторую версию списка мы добавим возможность хранить любой тип, не только числовой. Будут добавлены итераторы.
В библиотеке мы пропишем вторую версию


 // in lib.rs
 
 pub mod first;
 pub mod second;

Для начала мы перепишем структуру


 enum Link {
     Empty,
     More(Box),
 }

в виде


 type Link = Option<Box<Node>>;

Это упростит нашу вторую по счету реализацию, например далее везде вместо Link::Empty мы будем писать просто None. Заменим следующую синтаксическую идиому


 next: mem::replace(&mut self.head, Link::Empty),

на


 next: self.head.take()

Мы перепишем функцию pop. Если рассмотреть конструкцию


 match option { None => None, Some(x) => Some(y) }

она представляет из себя обертку над функцией map. Функция map берет x, что-то делает в Some(x) и производит Some(y). Мы перепишем функцию pop, возьмем анонимную функцию и передадим ее в качестве праметра в map:


 pub fn pop(&mut self) -> Option<i32> {
     self.head.take().map(|node| {
         let node = *node;
         self.head = node.next;
         node.elem
     })
 }

Теперь добавим возможность произвольно менять тип данных, которые хранятся в ноде


 pub struct List<T> {
     head: Link<T>,
 }
 
 type Link = Option<Box<Node<T>>>;
 
 struct Node<T> {
     elem: T,
     next: Link<T>,
 }
 
 impl<T> List<T> {
     pub fn new() -> Self {
         List { head: None }
     }
 
     pub fn push(&mut self, elem: T) {
         let new_node = Box::new(Node {
             elem: elem,
             next: self.head.take(),
         });
 
         self.head = Some(new_node);
     }
 
     pub fn pop(&mut self) -> Option<T> {
         self.head.take().map(|node| {
             let node = *node;
             self.head = node.next;
             node.elem
         })
     }
 }
 
 impl<T> Drop for List<T> {
     fn drop(&mut self) {
         let mut cur_link = self.head.take();
         while let Some(mut boxed_node) = cur_link {
             cur_link = boxed_node.next.take();
         }
     }
 }

Добавим функцию, возвращающую ссылку на головную ноду


 pub fn peek(&self) -> Option<&T> {
     self.head.as_ref().map(|node| {
         &node.elem
     })
 }

либо так


 pub fn peek_mut(&mut self) -> Option<&mut T> {
     self.head.as_mut().map(|node| {
         &mut node.elem
     })
 }

Теперь можно протестировать


 #[test]
 fn peek() {
     let mut list = List::new();
     assert_eq!(list.peek(), None);
     assert_eq!(list.peek_mut(), None);
     list.push(1); list.push(2); list.push(3);
 
     assert_eq!(list.peek(), Some(&3));
     assert_eq!(list.peek_mut(), Some(&mut 3));
 }

Итерацию в растовской коллекции можно сделать с помощью типажа Iterator


 pub trait Iterator {
     type Item;
     fn next(&mut self) -> Option<Self::Item>;
 }

Мы добавили тип Item. В расте нет оператора yield, как в питоне например, и прийдется изобретать велосипед. В коллекции может быть три типа итераторов

 1 T
 2 &mut T
 3 &T

Первая версия


 // Tuple structs are an alternative form of struct,
 // useful for trivial wrappers around other types.
 pub struct IntoIter<T>(List<T>);
 
 impl<T> List<T> {
     pub fn into_iter(self) -> IntoIter<T> {
         IntoIter(self)
     }
 }
 
 impl<T> Iterator for IntoIter<T> {
     type Item = T;
     fn next(&mut self) -> Option<Self::Item> {
         // access fields of a tuple struct numerically
         self.0.pop()
     }
 }

Напишем тест


 #[test]
 fn into_iter() {
     let mut list = List::new();
     list.push(1); list.push(2); list.push(3);
 
     let mut iter = list.into_iter();
     assert_eq!(iter.next(), Some(3));
     assert_eq!(iter.next(), Some(2));
     assert_eq!(iter.next(), Some(1));
 }

В следующей - 3-й версии итератора мы будем хранить указатель на текущую ноду, а yield будем применять для следующей. При этом указатель next должен переместиться на текущую ноду.


 pub struct Iter<'a, T:'a> {
     next: Option<&'a Node<T>>,
 }
 
 impl<T> List<T> {
     pub fn iter<'a>(&'a self) -> Iter<'a, T> {
         Iter { next: self.head.as_ref().map(|node| &**node) }
     }
 }
 
 impl<'a, T> Iterator for Iter<'a, T> {
     type Item = &'a T;
 
     fn next(&mut self) -> Option<Self::Item> {
         self.next.map(|node| {
             self.next = node.next.as_ref().map(|node| &**node);
             &node.elem
         })
     }
 }

Тестируем


 #[test]
 fn iter() {
     let mut list = List::new();
     list.push(1); list.push(2); list.push(3);
 
     let mut iter = list.iter();
     assert_eq!(iter.next(), Some(&3));
     assert_eq!(iter.next(), Some(&2));
     assert_eq!(iter.next(), Some(&1));
 }

Здесь мы применили конструкцию


 fn foo<'a>(&'a A) -> &'a B

что означает, что время жизни входящих параметров должно быть таким же, как и выходных, т.е. и те и другие должны находиться в одной области видимости или определения. Финальная версия second.rs


 pub struct List<T> {
     head: Link<T>,
 }
 
 type Link = Option<Box<Node<T>>>;
 
 struct Node<T> {
     elem: T,
     next: Link<T>,
 }
 
 pub struct IntoIter<T>(List<T>);
 
 pub struct Iter<'a, T:'a> {
     next: Option<&'a Node<T>>,
 }
 
 pub struct IterMut<'a, T: 'a> {
     next: Option<&'a mut Node>,
 }
 
 
 
 impl List<T> {
     pub fn new() -> Self {
         List { head: None }
     }
 
     pub fn push(&mut self, elem: T) {
         let new_node = Box::new(Node {
             elem: elem,
             next: self.head.take(),
         });
 
         self.head = Some(new_node);
     }
 
     pub fn pop(&mut self) -> Option<T> {
         self.head.take().map(|node| {
             let node = *node;
             self.head = node.next;
             node.elem
         })
     }
 
     pub fn peek(&self) -> Option<&T> {
         self.head.as_ref().map(|node| {
             &node.elem
         })
     }
 
     pub fn peek_mut(&mut self) -> Option<&mut T> {
         self.head.as_mut().map(|node| {
             &mut node.elem
         })
     }
 
     pub fn into_iter(self) -> IntoIter<T> {
         IntoIter(self)
     }
 
     pub fn iter(&self) -> Iter<T> {
         Iter { next: self.head.as_ref().map(|node| &**node) }
     }
 
     pub fn iter_mut(&mut self) -> IterMut<T> {
         IterMut { next: self.head.as_mut().map(|node| &mut **node) }
     }
 }
 
 impl<T> Drop for List<T> {
     fn drop(&mut self) {
         let mut cur_link = self.head.take();
         while let Some(mut boxed_node) = cur_link {
             cur_link = boxed_node.next.take();
         }
     }
 }
 
 impl<T> Iterator for IntoIter<T> {
     type Item = T;
     fn next(&mut self) -> Option<Self::Item> {
         self.0.pop()
     }
 }
 
 impl<'a, T> Iterator for Iter<'a, T> {
     type Item = &'a T;
 
     fn next(&mut self) -> Option<Self::Item> {
         self.next.map(|node| {
             self.next = node.next.as_ref().map(|node| &**node);
             &node.elem
         })
     }
 }
 
 impl<'a, T> Iterator for IterMut<'a, T> {
     type Item = &'a mut T;
 
     fn next(&mut self) -> Option<Self::Item> {
         self.next.take().map(|node| {
             self.next = node.next.as_mut().map(|node| &mut **node);
             &mut node.elem
         })
     }
 }
 
 
 #[cfg(test)]
 mod test {
     use super::List;
 
     #[test]
     fn basics() {
         let mut list = List::new();
 
         // Check empty list behaves right
         assert_eq!(list.pop(), None);
 
         // Populate list
         list.push(1);
         list.push(2);
         list.push(3);
 
         // Check normal removal
         assert_eq!(list.pop(), Some(3));
         assert_eq!(list.pop(), Some(2));
 
         // Push some more just to make sure nothing's corrupted
         list.push(4);
         list.push(5);
 
         // Check normal removal
         assert_eq!(list.pop(), Some(5));
         assert_eq!(list.pop(), Some(4));
 
         // Check exhaustion
         assert_eq!(list.pop(), Some(1));
         assert_eq!(list.pop(), None);
     }
 
     #[test]
     fn peek() {
         let mut list = List::new();
         assert_eq!(list.peek(), None);
         assert_eq!(list.peek_mut(), None);
         list.push(1); list.push(2); list.push(3);
 
         assert_eq!(list.peek(), Some(&3));
         assert_eq!(list.peek_mut(), Some(&mut 3));
     }
 
     #[test]
     fn into_iter() {
         let mut list = List::new();
         list.push(1); list.push(2); list.push(3);
 
         let mut iter = list.into_iter();
         assert_eq!(iter.next(), Some(3));
         assert_eq!(iter.next(), Some(2));
         assert_eq!(iter.next(), Some(1));
     }
 
     #[test]
     fn iter() {
         let mut list = List::new();
         list.push(1); list.push(2); list.push(3);
 
         let mut iter = list.iter();
         assert_eq!(iter.next(), Some(&3));
         assert_eq!(iter.next(), Some(&2));
         assert_eq!(iter.next(), Some(&1));
     }
 
     #[test]
     fn iter_mut() {
         let mut list = List::new();
         list.push(1); list.push(2); list.push(3);
 
         let mut iter = list.iter_mut();
         assert_eq!(iter.next(), Some(&mut 3));
         assert_eq!(iter.next(), Some(&mut 2));
         assert_eq!(iter.next(), Some(&mut 1));
     }
 }

В оригинальной версии далее идет реализация еще трех вариантов. В третьем добавляется функции append, tail, а также делается ставка на многопоточность. В четвертой версии появляется двойной связный список. В пятой версии делается упор на unsafe.

Оставьте свой комментарий !

Ваше имя:
Комментарий:
Оба поля являются обязательными

Автор Комментарий к данной статье