Основы Rust: разбираем контейнеры, карты и наборы

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

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

В этой части мы последовательно поговорим про Standard Library Containers (SLC) и про стандартную библиотеку Rust (std::*). Также мы обсуждаем карты (maps) и наборы (sets), в заключение напишем для них два подробных тестовых примера.

Чтение документации

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

Поначалу чтение документации по Rust может быть сложным, поэтому в качестве примера я рассмотрю Vec. Полезный совет — поставьте галочку в поле '[-]', чтобы свернуть документацию. Если вы загрузите исходный текст стандартной библиотеки с помощью компонента rustup, добавив rust-src, рядом появится ссылка '[src]'. Это дает вам возможность увидеть все доступные методы с высоты птичьего полета, то есть в режиме обзора.

Первое, что следует заметить, это то, что не все возможные методы определены на базе самого std::vec. Это (в основном) мутабельные методы, которые изменяют вектор, например, push. Некоторые методы реализуются только для векторов, тип которых соответствует какому-либо ограничению.

Например, вы можете вызвать dedup (удаление дубликатов), только если тип действительно является тем, который можно сравнить на равенство. Существует несколько блоков impl, которые определяют Vec для различных ограничений типа.

Кроме того, существуют особые отношения между Vec<T> и &[T]. Любой метод, работающий со срезами, будет также напрямую работать с векторами, без явной необходимости использовать метод as_slice. Эта связь выражается через Deref<Target=[T]>. Это также срабатывает, когда вы передаете вектор по ссылке чему-то, что ожидает срез — это одно из немногих мест, где преобразование между типами происходит автоматически. Поэтому такие методы среза, как first, который, возможно, возвращает ссылку на первый элемент, или last, работают и для векторов.

Многие методы аналогичны соответствующим строковым методам, например, split_at для получения пары срезов, разделенных по индексу, starts_with для проверки, начинается ли вектор с последовательности значений, и contains для проверки, содержит ли вектор определенное значение.

Нет метода поиска индекса конкретного значения, но вот эмпирическое правило: если вы не можете найти метод на контейнере, ищите метод на итераторе:

 let v = vec![10,20,30,40,50];
assert_eq!(v.iter().position(|&i| i == 30).unwrap(), 2);

Знак & используется потому, что это итератор по ссылкам — в качестве альтернативы для сравнения можно сказать *i == 30.

Аналогично, для векторов нет метода map, потому что iter().map(...).collect() выполнит эту работу так же хорошо. Rust не любит выделения без необходимости — часто вам не нужен результат map в качестве фактического выделенного вектора.

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

Методы Vec<T> и &[T] имеют общие черты: векторы умеют делать отладочный показ самих себя (но только если элементы реализуют Debug). Аналогично, они клонируемы, если их элементы клонируемы. Они реализуют Drop, что автоматически происходит, когда векторы окончательно умирают; в таком случае память освобождается, и все элементы также удаляются.

Признак Extend означает, что значения из итераторов могут быть добавлены в вектор без цикла:

v.extend([60,70,80].iter());
let mut strings = vec!["hello".to_string(), "dolly".to_string()];
strings.extend(["you","are","fine"].iter().map(|s| s.to_string()));

Существует также FromIterator, который позволяет строить векторы из итераторов. На это опирается метод iterator collect.

Любой контейнер также должен быть итератором. Напомним, что существует три вида итераторов:

• for x in v {...} // returns T, consumes v
• for x in &v {...} // returns &T
• for x in &mut v {...} // returns &mut T

Оператор for опирается на признак IntoIterator, и действительно существует три его реализации.

Затем происходит индексация, управляемая Index (чтение из вектора) и IndexMut (изменение вектора). Существует множество возможностей, потому что есть также индексация срезов, например v[0..2], возвращающая эти срезы, а также обычная v[0], которая просто возвращает ссылку на первый элемент.

Существует несколько реализаций признака From. Например, Vec::from("hello".to_string()) даст вам вектор байтов строки Vec<u8>. В String уже есть метод into_bytes, так зачем городить лишнее? Да, кажется запутанным иметь несколько способов сделать одно и то же. Но это необходимо, потому что явные трейты делают возможными общие методы.

Иногда ограничения системы типов Rust делают вещи неуклюжими. Примером может служить то, что PartialEq отдельно определен для массивов размером до 32! (Это будет улучшено.) Это позволяет удобно напрямую сравнивать векторы с массивами, но помните об ограничении размера!

Есть и скрытые жемчужины, зарытые глубоко в документации. Как говорит Кароль Кучмарски: «Потому что, давайте будем честными: никто не прокручивает экран так далеко». Как вам возможность обрабатывать ошибки прямо в итераторе?

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

fn main() {
let nums = ["5","52","65"];
let iter = nums.iter().map(|s| s.parse::<i32>());
let converted: Vec<_> = iter.collect();
println!("{:?}",converted);
}
//[Ok(5), Ok(52), Ok(65)]

Справедливо, но теперь вам придется разворачивать эти ошибки — осторожно! Но Rust уже знает, как поступить правильно, если вы попросите, чтобы вектор содержался в Result — то есть был либо вектором, либо ошибкой:

let converted: Result<Vec<_>,_> = iter.collect();
//Ok([5, 52, 65])

А если бы было плохое преобразование? Тогда вы бы просто получили Err с первой встретившейся ошибкой. Это хороший пример того, насколько гибким является collect. Нотация здесь может быть пугающей — Vec<_> означает «это вектор, вычислите фактический тип для меня», а Result<Vec<>,>`, кроме того, просит Rust вычислить и тип ошибки.

Так что в документации много полезных деталей. Но она определенно яснее, чем то, что говорится в документации C++ о std::vector.

Требования, предъявляемые к элементам, зависят от фактических операций, выполняемых над контейнером. Обычно требуется, чтобы тип элемента был полным типом и удовлетворял требованиям Erasable, но многие функции-члены предъявляют более строгие требования.

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

Я бы посоветовал вам получить исходный текст с помощью компонента rustup, добавив rust-src, поскольку исходный текст стандартной библиотеки очень читабелен, а реализации методов обычно не так страшны, как их декларации.

Карты (Maps)

Карты (иногда называемые ассоциативными массивами или кубиками) позволяют искать значения, связанные с ключом. Это не очень сложная концепция, и ее можно реализовать самостоятельно с помощью массива кортежей:

let entries = [("one","eins"),("two","zwei"),("three","drei")];

if let Some(val) = entries.iter().find(|t| t.0 == "two") {
assert_eq!(val.1,"zwei");
}

Это хорошо подходит для небольших карт и требует только определения равенства для ключей, но поиск занимает линейное время — пропорциональное размеру карты.

HashMap работает гораздо лучше, когда нужно перебрать много пар ключ/значение:

use std::collections::HashMap;

let mut map = HashMap::new();
map.insert("one","eins");
map.insert("two","zwei");
map.insert("three","drei");

assert_eq! (map.contains_key("two"), true);
assert_eq! (map.get("two"), Some(&"zwei"));

Обратила внимание странная конструкция &"zwei"? Это происходит потому, что get возвращает ссылку на значение, а не само значение. Здесь тип значения &str, поэтому мы получаем &&str. В общем случае это должна быть ссылка, потому что мы не можем просто переместить значение из его собственного типа.

get_mut похож на get, но возвращает возможную изменяемую ссылку. Здесь у нас есть карта из строк в целые числа, и мы хотим обновить значение для ключа ‘two‘:

let mut map = HashMap::new();
map.insert("one",1);
map.insert("two",2);
map.insert("three",3);

println!("before {}", map.get("two").unwrap());

{
let mut mref = map.get_mut("two").unwrap();
*mref = 20;
}

println!("after {}", map.get("two").unwrap());
// before 2
// after 20

Обратите внимание, что получение записываемой ссылки происходит в отдельном блоке — в противном случае у нас было бы мутабельное заимствование, длящееся до конца, и тогда Rust не позволит вам снова заимствовать из map с помощью map.get("two"). Он не может разрешить ссылки на чтение, когда в области видимости уже есть записываемая ссылка. Если бы он это сделал, то не смог бы гарантировать, что эти ссылки на чтение останутся действительными.

Поэтому решение состоит в том, чтобы убедиться, что заимствование mutable не длится очень долго.

Это не самый элегантный API из возможных, но мы не можем отбрасывать возможные ошибки. Python выдаст исключение, а C++ просто создаст значение по умолчанию. Это удобно, но подло — легко забыть, что цена того, что a_map["two"] всегда возвращает целое число, заключается в том, что мы не можем отличить ноль от «не найдено», плюс создается дополнительная запись!

И никто не называет просто unwrap, за исключением примеров. Однако большинство кода Rust, который вы видите, состоит из маленьких отдельных примеров. Гораздо больше шансов, что совпадение произойдет:

if let Some(v) = map.get("two") {
let res = v + 1;
assert_eq!(res, 3);
}
...
match map.get_mut("two") {
Some(mref) => *mref = 20,
None => panic!("_now_ we can panic!")
}

Мы можем перебирать пары ключ/значение, но не в определенном порядке.

for (k,v) in map.iter() {
println!("key {} value {}", k,v);
}
// key one value eins
// key three value drei
// key two value zwei

Существуют также методы keys и values, возвращающие итераторы над ключами и значениями соответственно, что упрощает создание векторов значений.

Пример: Подсчет слов

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

Поэтому слова должны быть определены как состоящие только из буквенных символов. И слова должны сравниваться как написанные в нижнем регистре.

Выполнение изменяемого поиска по карте — дело простое, но и обработка случая, когда поиск не удался, немного неудобна. К счастью, существует элегантный способ обновления значений карты:

let mut map = HashMap::new();

for s in text.split(|c: char| ! c.is_alphabetic()) {
let word = s.to_lowercase();
let mut count = map.entry(word).or_insert(0);
*count += 1;
}

Если нет существующего count, соответствующего слову, то создадим новую запись, содержащую ноль для этого слова, и вставим ее в map. Это именно то, что делает карта в C++, только делается это явно, а не тайно как в Rust.

В этом фрагменте есть только один явный тип, и это char, необходимый из-за причуды свойства string Pattern, используемого в split. Но мы можем сделать вывод, что тип ключа — String, а тип значения — i32.

Используя для нашего теста книгу «Приключения Шерлока Холмса» от Project Gutenberg, мы можем проверить это более тщательно. Общее количество уникальных слов (map.len()) составляет 8071.

Как найти двадцать самых распространенных слов? Сначала преобразуйте карту в вектор кортежей (ключ, значение). Для этого используется карта, так как мы использовали функцию into_iter.

let mut entries: Vec<_> = map.into_iter().collect();

Далее мы можем сортировать в порядке убывания. sort_by ожидает результат метода cmp, который приходит из свойства Ord, реализованного типом целочисленного значения:

entries.sort_by(|a,b| b.1.cmp(&a.1));

И, наконец, выведите первые двадцать записей:

for e in entries.iter().take(20) {
println!("{} {}", e.0, e.1);
}

Ну, вы можете просто перебрать 0…20 и проиндексировать вектор здесь — это не неправильно, просто немного не идиоматично — и потенциально более дорого для больших итераций.

Итак, вот итоговый список топовых слов в книге:

38765
the 5810
and 3088
i 3038
to 2823
of 2778
a 2701
in 1823
that 1767
it 1749
you 1572
he 1486
was 1411
his 1159
is 1150
my 1007
have 929
with 877
as 863
had 830

Небольшой сюрприз — что это за пустое слово? Это потому, что split работает с односимвольными разделителями, поэтому любая пунктуация или лишние пробелы вызывают новое разделение.

Наборы

Наборы (sets) — это карты, в которых вам важны только ключи, а не связанные с ними значения. Поэтому insert принимает только одно значение, а contains используется для проверки того, входит ли значение в набор.

Как и все контейнеры, вы можете создать HashSet из итератора. Именно это и делает collect, как только вы зададите ему необходимую подсказку типа:

// set1.rs
use std::collections::HashSet;

fn make_set(words: &str) -> HashSet<&str> {
words.split_whitespace().collect()
}

fn main() {
let fruit = make_set("apple orange pear orange");

println!("{:?}", fruit);
}
// {"orange", "pear", "apple"}

Обратите внимание (как и ожидалось), что повторные вставки одного и того же ключа не имеют эффекта, а порядок значений в наборе не важен.

Они не были бы наборами без обычных операций:

let fruit = make_set("apple orange pear");
let colours = make_set("brown purple orange yellow");

for c in fruit.intersection(&colours) {
println!("{:?}",c);
}
// "orange"

Все они создают итераторы, и вы можете использовать collect, чтобы превратить их в наборы.

Вот краткое описание, как мы определили для векторов:

use std::hash::Hash;

trait ToSet<T> {
fn to_set(self) -> HashSet<T>;
}

impl <T,I> ToSet<T> for I
where T: Eq + Hash, I: Iterator<Item=T> {

fn to_set(self) -> HashSet<T> {
self.collect()
}
}

...

let intersect = fruit.intersection(&colours).to_set();

Как и в случае со всеми генериками Rust, вам необходимо ограничить типы — это может быть реализовано только для типов, которые понимают равенство (Eq) и для которых существует хэш-функция (Hash). Помните, что типа с названием Iterator не существует, поэтому I представляет любой тип, реализующий Iterator.

Эта техника реализации собственных методов на стандартных библиотечных типах может показаться слишком мощной, но, опять же, существуют Правила. Мы можем делать это только для наших собственных трейтов. Если и struct, и trait происходят из одного и того же крейта (в частности, из stdlib), то такая реализация не будет разрешена. Таким образом, вы избавляетесь от создания путаницы.

Прежде чем поздравить себя с таким умным и удобным сокращением будущего кода, вы должны знать о последствиях. Если make_set был написан так, что это наборы принадлежащих строк, то фактический тип intersect может оказаться неожиданным:

fn make_set(words: &str) -> HashSet<String> {
words.split_whitespace().map(|s| s.to_string()).collect()
}
...
// intersect is HashSet<&String>!
let intersect = fruit.intersection(&colours).to_set();

Иначе и быть не может, поскольку Rust не начнет внезапно создавать копии принадлежащих строк. intersect содержит единственную &String, позаимствованную у fruit. Я могу обещать, что это создаст вам проблемы позже, когда вы начнете исправлять время жизни!

Лучшее решение — использовать метод cloned итератора для создания копий принадлежащих строк intersect.

// intersect is HashSet<String> - much better
let intersect = fruit.intersection(&colours).cloned().to_set();

Более надежным определением to_set может быть self.cloned().collect(), что я и предлагаю вам далее опробовать.

 

Пример: Интерактивная обработка команд

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

Естественной реализацией является карта из имен команд в замыкании. Но как хранить замыкания, учитывая, что все они будут иметь разные размеры? Вставка скопирует их в кучу:

Вот первая попытка:

let mut v = Vec::new();
v.push(Box::new(|x| x * x));
v.push(Box::new(|x| x / 2.0));

for f in v.iter() {
let res = f(1.0);
println!("res {}", res);
}

При втором нажатии мы получаем вполне определенную ошибку:

= note: expected type `[[email protected]:4:21: 4:28]`
= note: found type `[[email protected]:5:21: 5:28]`
note: no two closures, even if identical, have the same type

rustc вывел слишком специфический тип, поэтому необходимо заставить этот вектор иметь тип boxed trait, прежде чем все заработает:

let mut v: Vec<Box<Fn(f64)->f64>> = Vec::new();

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

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

Поэтому закрытиям передается мутабельная ссылка в качестве аргумента, плюс кусочек строк (&[&str]), представляющих аргументы команды. Они будут возвращать некоторый результат — сначала мы будем использовать ошибки String.

D — это тип данных, который может быть чем угодно с любым размером.

type CliResult = Result<String,String>;

struct Cli<'a,D> {
data: D,
callbacks: HashMap<String, Box<Fn(&mut D,&[&str])->CliResult + 'a>>
}

impl <'a,D: Sized> Cli<'a,D> {
fn new(data: D) -> Cli<'a,D> {
Cli{data: data, callbacks: HashMap::new()}
}

fn cmd<F>(&mut self, name: &str, callback: F)
where F: Fn(&mut D, &[&str])->CliResult + 'a {
self.callbacks.insert(name.to_string(),Box::new(callback));
}

cmd передается как имя и любое замыкание, соответствующее нашей сигнатуре, которое помещается в крейт и вводится в карту. Fn означает, что наши замыкания заимствуют свое окружение, но не могут его изменять. Это один из тех общих методов, где декларация страшнее, чем фактическая реализация!

Забвение явного времени жизни является здесь распространенной ошибкой — Rust не позволит нам забыть, что эти замыкания имеют время жизни, ограниченное их окружением!

Теперь о чтении и выполнении команд:

fn process(&mut self,line: &str) -> CliResult {
let parts: Vec<_> = line.split_whitespace().collect();
if parts.len() == 0 {
return Ok("".to_string());
}
match self.callbacks.get(parts[0]) {
Some(callback) => callback(&mut self.data,&parts[1..]),
None => Err("no such command".to_string())
}
}

fn go(&mut self) {
let mut buff = String::new();
while io::stdin().read_line(&mut buff).expect("error") > 0 {
{
let line = buff.trim_left();
let res = self.process(line);
println!("{:?}", res);

}
buff.clear();
}
}

Все это достаточно просто — разбиваем строку на слова в виде вектора, ищем первое слово в карте и вызываем закрытие с нашими сохраненными мутабельными данными и остальными словами.

Пустая строка игнорируется и не считается ошибкой.

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

fn ok<T: ToString>(s: T) -> CliResult {
Ok(s.to_string())
}

fn err<T: ToString>(s: T) -> CliResult {
Err(s.to_string())
}

И вот, наконец, главная программа. Посмотрите, как работает ok(answer) — ведь целые числа умеют преобразовывать себя в строки!

use std::error::Error;

fn main() {
println!("Welcome to the Interactive Prompt! ");

struct Data {
answer: i32
}

let mut cli = Cli::new(Data{answer: 42});

cli.cmd("go",|data,args| {
if args.len() == 0 { return err("need 1 argument"); }
data.answer = match args[0].parse::<i32>() {
Ok(n) => n,
Err(e) => return err(e.description())
};
println!("got {:?}", args);
ok(data.answer)
});

cli.cmd("show",|data,_| {
ok(data.answer)
});

cli.go();
}

Обработка ошибок здесь немного неуклюжая, и позже мы увидим, как использовать оператор вопросительного знака в подобных случаях. По сути, конкретная ошибка std::num::ParseIntError реализует трейт std::error::Error, который мы должны привести в область видимости, чтобы использовать метод описания — Rust не позволяет трейтам работать, если они не видны.

И в действии:

Welcome to the Interactive Prompt!
go 32
got ["32"]
Ok("32")
show
Ok("32")
goop one two three
Err("no such command")
go 42 one two three
got ["42", "one", "two", "three"]
Ok("42")
go boo!
Err("invalid digit found in string")

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

Во-первых, если мы передадим cmd три аргумента, причем второй будет строкой помощи, то мы сможем хранить эти строки помощи и автоматически реализовать команду ‘help‘. Во-вторых, очень удобно иметь возможность редактирования команд и истории, поэтому используйте rustyline crate из Cargo.

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