Алгоритмы и структуры данных на Rust: практическое руководство

Введение в алгоритмы и структуры данных на Rust

Язык программирования Rust завоевал признание разработчиков благодаря своей высокой производительности и строгим гарантиям безопасности памяти. Однако переход на Rust с других языков, таких как Python или JavaScript, может быть непростым, особенно при реализации классических алгоритмов и структур данных. В этой статье мы рассмотрим, как эффективно реализовать базовые структуры данных и алгоритмы на Rust, учитывая особенности системы владения (ownership) и заимствования (borrowing).

Статья предназначена для разработчиков, уже знакомых с основами Rust. Мы сосредоточимся на практических примерах кода, которые можно сразу использовать в реальных проектах. Все примеры будут сопровождаться подробными комментариями.

Реализация связного списка на Rust

Связный список — одна из фундаментальных структур данных. В Rust его реализация требует особого внимания из-за правил владения. Рассмотрим односвязный список с использованием Box для управления памятью.

Базовый односвязный список

Начнём с определения узла и самого списка:

use std::fmt::Display;

#[derive(Debug)]
struct Node<T> {
    value: T,
    next: Option<Box<Node<T>>>,
}

#[derive(Debug)]
struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
    length: usize,
}

impl<T> LinkedList<T> {
    fn new() -> Self {
        LinkedList {
            head: None,
            length: 0,
        }
    }

    fn push_front(&mut self, value: T) {
        let new_node = Box::new(Node {
            value,
            next: self.head.take(),
        });
        self.head = Some(new_node);
        self.length += 1;
    }

    fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            self.head = node.next;
            self.length -= 1;
            node.value
        })
    }

    fn is_empty(&self) -> bool {
        self.head.is_none()
    }

    fn len(&self) -> usize {
        self.length
    }
}

Обратите внимание на использование Option<Box<Node<T>>>. Это стандартный способ создания рекурсивных структур в Rust, так как компилятор требует заранее известный размер. Метод take() позволяет безопасно извлечь значение из Option, заменяя его на None.

Итерация по списку

Реализуем итератор для списка:

impl<T: Clone> LinkedList<T> {
    fn iter(&self) -> LinkedListIterator<T> {
        LinkedListIterator {
            current: self.head.as_deref(),
        }
    }
}

struct LinkedListIterator<T> {
    current: Option<&Node<T>>,
}

impl<T> Iterator for LinkedListIterator<T> {
    type Item = &T;

    fn next(&mut self) -> Option<Self::Item> {
        self.current.take().map(|node| {
            self.current = node.next.as_deref();
            &node.value
        })
    }
}

Бинарное дерево поиска (BST) на Rust

Деревья — ещё одна важная структура. Реализуем бинарное дерево поиска с поддержкой вставки, поиска и обхода.

Структура и базовая вставка

#[derive(Debug)]
struct TreeNode<T> {
    value: T,
    left: Option<Box<TreeNode<T>>>,
    right: Option<Box<TreeNode<T>>>,
}

#[derive(Debug)]
struct BinarySearchTree<T> {
    root: Option<Box<TreeNode<T>>>,
}

impl<T: Ord> BinarySearchTree<T> {
    fn new() -> Self {
        BinarySearchTree { root: None }
    }

    fn insert(&mut self, value: T) {
        let mut current = &mut self.root;
        while let Some(node) = current {
            if value < node.value {
                current = &mut node.left;
            } else if value > node.value {
                current = &mut node.right;
            } else {
                // Значение уже существует, ничего не делаем
                return;
            }
        }
        *current = Some(Box::new(TreeNode {
            value,
            left: None,
            right: None,
        }));
    }
}

Рекурсивная реализация может быть элегантнее, но итеративная версия с while let безопаснее с точки зрения заимствования. Ключевой момент — мы используем изменяемую ссылку на Option, чтобы найти место для вставки.

Поиск и обход дерева

impl<T: Ord> BinarySearchTree<T> {
    fn contains(&self, value: &T) -> bool {
        let mut current = &self.root;
        while let Some(node) = current {
            if *value < node.value {
                current = &node.left;
            } else if *value > node.value {
                current = &node.right;
            } else {
                return true;
            }
        }
        false
    }

    fn inorder_traversal(&self) -> Vec<&T> {
        let mut result = Vec::new();
        Self::inorder_helper(&self.root, &mut result);
        result
    }

    fn inorder_helper(node: &Option<Box<TreeNode<T>>>, result: &mut Vec<&T>) {
        if let Some(ref n) = node {
            Self::inorder_helper(&n.left, result);
            result.push(&n.value);
            Self::inorder_helper(&n.right, result);
        }
    }
}

Рекурсивный обход здесь допустим, так как глубина дерева обычно невелика. Для больших деревьев стоит рассмотреть итеративный подход с использованием стека.

Алгоритмы сортировки на Rust

Рассмотрим три популярных алгоритма сортировки: быструю сортировку (quicksort), сортировку слиянием (merge sort) и встроенную сортировку Rust.

Быстрая сортировка (Quicksort)

fn quicksort<T: Ord>(arr: &mut [T]) {
    if arr.len() <= 1 {
        return;
    }

    let pivot_index = partition(arr);
    quicksort(&mut arr[..pivot_index]);
    quicksort(&mut arr[pivot_index + 1..]);
}

fn partition<T: Ord>(arr: &mut [T]) -> usize {
    let pivot_index = arr.len() - 1;
    let mut i = 0;

    for j in 0..pivot_index