Основы Rust: обсуждаем структуры (Struct)

В нашей последовательной серии материалов мы рассмотрим базовые основы новомодного языка Rust. А во второй части цикла на основе изученного попробуем написать самые простые смарт-контракты для таких блокчейн-проектов, как Solana. В этом туториале будет много примеров, мало теории и быстрый темп продвижения.

Этот пост — вольный перевод на русский вот этой оригинальной статьи (с нашими дополнениями в местах, где это показалось нужным), которую написал Стив Донован. Начало можно найти вот здесь, а оглавление всей серии — вот тут.

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

Структуры с динамическими данными

Наиболее мощной техникой является структура, которая содержит ссылки на саму себя. Вот с нее мы и начнем.

Вот основной строительный блок двоичного дерева, выраженный на всем понятном языке C.

struct Node {
        const char *payload;
        struct Node *left;
        struct Node *right;
    };

Нельзя сделать это в реальном коде, непосредственно включая поля Node внутрь структуры, потому что тогда размер Node зависит от размера Node… короче, это просто не вычисляется. Поэтому мы используем указатели на структуры Node, поскольку размер указателя заранее всегда известен.

Если left не NULL, такой узел будет иметь left, указывающий на другой узел, и так до бесконечности.

Rust не делает NULL (по крайней мере, небезопасно), так что это явно работа для Option. Но нельзя просто поместить Node в этот Option, потому что мы не знаем размер Node (и так далее). Это работа для Box, поскольку он содержит выделенный указатель на данные и всегда имеет фиксированный размер.

Вот эквивалент в Rust, использующий type для создания псевдонима:

type NodeBox = Option<Box<Node>>;

#[derive(Debug)]
struct Node {
    payload: String,
    left: NodeBox,
    right: NodeBox
}

В этом отношении Rust достаточно гибок — нет необходимости в прямых объявлениях.

Короче, с теорией вроде все ясно. Вот наша первая тестовая программа:

impl Node {
    fn new(s: &str) -> Node {
        Node{payload: s.to_string(), left: None, right: None}
    }

    fn boxer(node: Node) -> NodeBox {
        Some(Box::new(node))
    }

    fn set_left(&mut self, node: Node) {
        self.left = Self::boxer(node);
    }

    fn set_right(&mut self, node: Node) {
        self.right = Self::boxer(node);
    }

}


fn main() {
    let mut root = Node::new("root");
    root.set_left(Node::new("left"));
    root.set_right(Node::new("right"));

    println!("arr {:#?}", root);
}

Вывод на удивление красив, и все благодаря "{:#?}" ("#" означает «расширенный режим»).

root Node {
    payload: "root",
    left: Some(
        Node {
            payload: "left",
            left: None,
            right: None
        }
    ),
    right: Some(
        Node {
            payload: "right",
            left: None,
            right: None
        }
    )
}

А что произойдет, когда корень дерева будет сброшен?

Все поля удаляются, а если удаляются «ветви» дерева, они удаляют свои поля и так далее по цепочке. Box::new может быть самым близким к new ключевым словом, но нам не потребуются ни delete, ни free.

Теперь надо найти применение этому дереву. Обратите внимание, что строки могут быть упорядочены: 'bar' < 'foo', 'abba' > 'aardvark'; это так называемый «алфавитный порядок» (хотя, строго говоря, это лексический порядок, поскольку человеческие языки очень разнообразны и подчас имеют свои странные правила).

Вот метод, который вставляет узлы в лексическом порядке строк. Мы сравниваем новые данные с текущим узлом — если они меньше, то пытаемся вставить слева, иначе пытаемся вставить справа. Слева может не быть узла, тогда делаем set_left и так далее.

fn insert(&mut self, data: &str) {
        if data < &self.payload {
            match self.left {
                Some(ref mut n) => n.insert(data),
                None => self.set_left(Self::new(data)),
            }
        } else {
            match self.right {
                Some(ref mut n) => n.insert(data),
                None => self.set_right(Self::new(data)),
            }
        }
    }

    ...
    fn main() {
        let mut root = Node::new("root");
        root.insert("one");
        root.insert("two");
        root.insert("four");

        println!("root {:#?}", root);
    }

Обратите внимание на соответствие — мы извлекаем мутабельную ссылку на box, если Option равна Some, также применяем метод insert. В противном случае нам нужно создать новый Node для левой стороны и так далее. Box — это умный указатель, поэтому обратите внимание, что для вызова методов Node на нем не потребовалось «распаковывать ящик»!

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

root Node {
    payload: "root",
    left: Some(
        Node {
            payload: "one",
            left: Some(
                Node {
                    payload: "four",
                    left: None,
                    right: None
                }
            ),
            right: None
        }
    ),
    right: Some(
        Node {
            payload: "two",
            left: None,
            right: None
        }
    )
}

Строки, которые «меньше» других строк, помещаются на левую сторону, в противном случае — на правую.

Время для посещения (функция fn visit). Это обход в порядке следования — мы посещаем левую часть, делаем что-то на узле, а затем посещаем правую.

fn visit(&self) {
        if let Some(ref left) = self.left {
            left.visit();
        }
        println!("'{}'", self.payload);
        if let Some(ref right) = self.right {
            right.visit();
        }
    }
    ...
    ...
    root.visit();
    // 'four'
    // 'one'
    // 'root'
    // 'two'

Итак, мы посещаем строки по порядку! Обратите внимание на повторное появление ref — if let использует точно такие же правила, как и match.

Общие структуры

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

Итак, вот наш общий Node с параметром типа T.

type NodeBox<T> = Option<Box<Node<T>>>;

#[derive(Debug)]
struct Node<T> {
    payload: T,
    left: NodeBox<T>,
    right: NodeBox<T>
}

Реализация показывает разницу между языками. Основной операцией над полезной нагрузкой является сравнение, поэтому T должен быть сравним с <, то есть он реализует PartialOrd.

Параметр типа должен быть объявлен в блоке impl со своими ограничениями:

impl <T: PartialOrd> Node<T> {
    fn new(s: T) -> Node<T> {
        Node{payload: s, left: None, right: None}
    }

    fn boxer(node: Node<T>) -> NodeBox<T> {
        Some(Box::new(node))
    }

    fn set_left(&mut self, node: Node<T>) {
        self.left = Self::boxer(node);
    }

    fn set_right(&mut self, node: Node<T>) {
        self.right = Self::boxer(node);
    }

    fn insert(&mut self, data: T) {
        if data < self.payload {
            match self.left {
                Some(ref mut n) => n.insert(data),
                None => self.set_left(Self::new(data)),
            }
        } else {
            match self.right {
                Some(ref mut n) => n.insert(data),
                None => self.set_right(Self::new(data)),
            }
        }
    }
}


fn main() {
    let mut root = Node::new("root".to_string());
    root.insert("one".to_string());
    root.insert("two".to_string());
    root.insert("four".to_string());

    println!("root {:#?}", root);
}

Таким образом, родовым структурам нужен (нужны) параметр(ы) типа, указанный(ые) в угловых скобках, как в C++.

Rust обычно достаточно умен, чтобы определить этот параметр типа прямо из контекста — он знает, что у него есть Node<T>, и знает, что его методу insert передается T. Первый вызов insert прибивает T к String. А вот если последующие вызовы будут непоследовательными, он будет жаловаться.

Но вы должны соответствующим образом заранее ограничить этот тип!

Продолжение следует…