Содержание


Rust - новый язык программирования: Часть 11. Векторы и строки. Контейнеры и итераторы.

Comments

В предыдущих статьях цикла был сделан общий обзор языка программирования Rust, обсуждались основы синтаксиса: были описаны простейшие компоненты (переменные, простые типы данных, операторы и расширения), управляющие конструкции и составные структуры данных, функции и деструкторы. Особое внимание было уделено модели памяти в целом, концепции владения объектами, общим принципам управления памятью, использованию собственных и управляемых блоков общей памяти, а также заимствованных указателей. В последней статье рассматривались средства ввода/вывода языка Rust. В данной статье речь пойдёт о векторах и строках, а также о связанных с ними сущностях - контейнерах и итераторах.

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

1. Что нужно знать о векторах и строках в Rust

Вектор (vector) - это непрерывная область памяти, содержащая нуль или большее количество значений одного типа. Как и другие типы в языке Rust, векторы могут быть размещены в стеке, в локальной общей памяти (local heap) или в общей памяти, предназначенной для обмена данными (exchange heap). Конструктор типа данных vector создаёт гомогенный массив значений заданного типа, который имеет фиксированный размер. Операции, подобные vec.push или vec.appen_one, возможны только с собственными (owned) векторами.

Тип вектора может быть задан вместе с определённым размером, то есть, записывается литерал для обозначения, например, целочисленного типа, далее следует символ "звёздочка" и размер: [int * 10]. Такой тип вектора с заданным размером представляет собой first-class-тип, поскольку его размер определён статически. Вектор без указания размера обычно так и обозначают: "вектор неопределённого размера", следовательно он не является first-class-типом. Экземпляр вектора неопределённого размера может быть создан только посредством типа "указатель", то есть: &[T], @[T] или ~[T]. Собственно сам тип вектора зависит от типа его элементов точно так же, как и для других простых структурных (составных) типов.

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

В листинге 1 приведён пример определения переменной типа вектор и её использования.

Листинг 1. Определение вектора и его использование
let v: &[int] = &[7, 5, 3];
let i: int = v[2];
assert!( i == 3 );

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

Заимствованные указатели (borrowed pointers) на векторы также называют срезами (slices).

В листинге 2 показаны примеры определения векторов с различными типами владения.

Листинг 2. Примеры векторов, определяемых в стеке, в локальной общей памяти и в общей памяти для обмена данными
// вектор фиксированного размера, определяемый в стеке
let stack_tech_books: [Books, ..3] = [Programming, Networks, OperatingSystems];

// заимствованный указатель на вектор, размещённый в стеке
let stack_history_books: &[Books] = &[AncientWorld, MiddleAges, WorldWar1, WorldWar2];

// вектор, размещённый в локальной общей памяти (managed heap)
let local_fiction_books: @[Books] = @[Novells, Poetry, Stories];

// вектор, размещённый в общей памяти для обмена данными (exchange heap - owned)
let exchange_science_books: ~[Books] = ~[Mathematics, Physics, Chemistry, Biology];

2. Операции с векторами

Используемый при работе с векторами оператор + обозначает операцию объединения (конкатенации) векторов, как показано в листинге 3.

Листинг 3. Пример операции объединения векторов
let tech_books = ~[Programming, Networks, OperatingSystems];
let fiction_books = ~[Novells, Poetry, Stories];
let science_books = ~[Mathematics, Physics, Chemistry, Biology];

//"сложение" двух векторов для создания нового вектора
let my_library = tech_books + fiction_books;

// функция push_all() добавляет заданный вектор в вектор, помещённый в изменяемый слот
let mut my_library = my_library;
my_library.push_all( science_books );

Следует отметить, что в предыдущем примере в листинге 3 при сложении векторов использовались собственные (owned) векторы. Авторы языка поясняют, что некоторые операции над срезами векторов (заимствованными указателями на векторы и их фрагменты) и над стековыми векторами пока ещё недостаточно хорошо поддерживаются. Поэтому собственные векторы на текущий момент являются наиболее применимыми.

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

Листинг 4. Обращение к элементу вектора по индексу
let tech_books: [Books, ..3] = [Programming, Networks, OperatingSystems];
match tech_books[0] {
  Programming => append_book( tech_books[0] ),
  _ => ()
}

Операцию деструктуризации вектора можно выполнить с использованием поиска совпадения с образцом, как показано в листинге 5.

Листинг 5. Деструктуризация вектора посредством сравнения с образцом
let numbers: &[int] = &[1, 2, 3];
let score = match numbers {
  [] => 0,
  [a] => a * 10,
  [a, b] => a * 6 + b * 4,
  [a, b, c, ..rest] => a * 5 + b * 3 + c * 2 + rest.len as int
};

3. Изменяемость/неизменяемость векторов

Как и в случаях применения других типов данных, переменная типа "вектор" по умолчанию является неизменяемой. Элементы вектора наследуют его свойство изменяемости/неизменяемости, и поэтому отдельным элементам не могут быть присвоены новые значения, если вектор расположен в неизменяемом слоте (см. листинг 6).

Листинг 6. Некорректная попытка присваивания нового значения элементу неизменяемого вектора
let science_books ~[Books] = ~[Mathematics, Physics, Chemistry, Biology];

science_books[3] = Psychology; // ОШИБКА: попытка изменения элемента неизменяемого вектора

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

Листинг 7. Перемещение вектора в изменяемый слот с последующим изменением его элемента
let science_books ~[Books] = ~[Mathematics, Physics, Chemistry, Biology];
// передача вектора в изменяемый слот
let mut mtb_science_books = science_books;
// теперь можно изменять элементы вектора
mtb_science_books[3] = Psychology;

В листинге 7 показан простой пример структуры данных языка Rust, используемой в двойном режиме (dual-mode data structure). Два режима использования структур данных также обозначают терминами freezing ("замораживание", невозможность изменения) и thawing ("оттаивание", возможность изменений).

4. Строки

В Rust строки представлены отдельным типом данных str, несмотря на то, что фактически они реализованы через векторы, содержащие элементы типа u8. Поэтому строки обладают практически всеми свойствами, присущими векторам. К строкам применимы те же методы размещения, что и к векторам, но при этом следует учитывать, что строковый литерал без спецсимвола, обозначающего способ размещения, например, "foo", трактуется иначе, нежели сравнимый с ним вектор [foo]. Главное различие состоит в том, что простые векторы по умолчанию размещаются в стеке и имеют фиксированную длину, в то время как обычные строки по умолчанию представлены заимствованными указателями (borrowed pointers) на фрагменты защищённой от записи (статической) памяти. Все строки в Rust являются неизменяемыми. В листинге 8 продемонстрированы различные способы размещения строк в памяти.

Листинг 8. Варианты размещения строк в памяти
// обычная строка, размещаемая в статической памяти
let stack_tech_books: &str = "Programming, Networks, OperatingSystems";

// такой же вариант, но с явным указанием на способ размещения
let stack_history_books: &str = &"AncientWorld, MiddleAges, WorldWar1, WorldWar2";

// размещение строки в локальной управляемой (managed) памяти
let local_fiction_books: @str = @"Novells, Poetry, Stories";

// размещение строки в собственной (owned) памяти
let exchange_science_books: ~str = ~"Mathematics, Physics, Chemistry, Biology";

5. Методы обработки векторов и строк

Для векторов и для строк Rust предоставляет большой набор удобных и полезных методов, определённых в стандартных модулях std::vec и std:str. В листинге 9 приведены примеры применения таких методов.

Листинг 9. Примеры применения методов обработки векторов и строк
let science_books = [Mathematics, Physics, Chemistry, Biology];

// методы проверки длины вектора
assert!( science_books.len() == 4 );
assert!( !science_books.is_empty() );

// последовательная обработка каждого элемента вектора по порядку:
// получение указателя на каждый элемент данного вектора
// (более подробно о конструкции for будет сказано ниже, в следующем разделе)
for sbooks in science_books.iter() {
  let topic_of_scibooks = unwrap_science_books( *sbooks );
  get_list_of_scibooks( topic_of_scibooks );
}

// преобразование (отображение) элементов вектора; здесь - в строки
let scibooks_topics = science_books.map( |v| scibooks_to_str( *v ) );
let key_scibooks_topic = scibooks_topics[0];

// удаление лишних пробелов перед строкой и после неё
let new_key_scibooks_topic = key_scibooks_topic.trim();

if key_scibooks_topic.len() > 4 {
  // получение подстроки заданной длины
  println( key_scibooks_topic.slice_chars( 0, 4 ) );
}

Полный список доступных методов обработки векторов и строк с их описаниями можно найти в соответствующих разделах документации по std:vec и std::str.

6. Контейнеры

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

Трэйты, общие для всех контейнеров, определены в модуле std::container.

6.1. Отображения (хэш-таблицы) и множества

Отображения или хэш-таблицы (maps) - это наборы однозначно определённых ключей и соответствующих им значений (таких значений может быть несколько для одного ключа, в этом случае отображение иногда называют мультиотображением). Множество (set) - это набор только однозначно определённых ключей без каких-либо дополнительных соответствующих значений. Трэйты Map и Set в модуле std::container определяют основной обобщённый интерфейс для этих типов.

В стандартной библиотеке представлены также три собственных (owned) типа map/set:

  • std::hashmap::HashMap и std::hashmap::HashSet, требующие ключей с реализацией Eq и Hash
  • std::trie::TrieMap и std::trie::TrieSet, требующие ключей, которые имеют тип uint
  • std::treemap::TreeMap и std::TreeSet, требующие ключей с реализацией TotalOrd

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

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

Каждый экземпляр отображения HashMap содержит случайный 128-битовый ключ для использования в данном экземпляре хэш-таблицы, что позволяет получить случайный порядок расположения набора ключей в этой хэш-таблице. Rust предоставляет реализацию SipHash (семейство псевдослучайных функций, оптимизированных по скорости для коротких сообщений) для любого типа, выполняющего реализацию трэйта IterBytes.

6.2. Очереди с двусторонним доступом

Модуль extra::ringbuf содержит реализацию очередей с двусторонним доступом (double-ended queue), обеспечивающую операции вставки и удаления (со сложностью O(1)) для обоих концов этого контейнера. Содержащиеся в нём элементы не обязательно должны быть копируемыми, поэтому такая очередь может передаваться между задачами, если тип её содержимого допускает возможность передачи. Соответствующий интерфейс Deque определён в модуле extra::collections.

В модуле extra::dlist содержится реализация связного списка с двусторонним доступом (double-ended linked list), также осуществляющего реализацию трэйта Deque, с операциями вставки и удаления на обоих концах списка и с операцией объединения списков. Все перечисленные операции имеют сложность O(1).

6.3. Очереди с приоритетами

Модуль std::priority_queue предоставляет реализацию очереди, упорядоченной по ключевому значению. Аналогично очередям с двусторонним доступом, содержащиеся в приоритетной очереди элементы не обязательно должны быть копируемыми, поэтому такая очередь может передаваться между задачами, если тип её содержимого допускает возможность передачи.

Операции вставки элементов характеризуются сложностью O(log n), но поиск или извлечение наибольшего элемента имеет сложность O(1). Преобразование вектора в очередь с приоритетами может быть выполнено непосредственно за один проход, и эта операция имеет сложность O(n). Очередь с приоритетами также может быть преобразована в отсортированный вектор посредством операции со сложностью O(n log n).

7. Итераторы

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

Общий протокол итерации для любых объектов определён в трэйте Iterator, расположенном в модуле std::iterator. Простейшая, минимальная реализация этого трэйта представлена следующим методом next (см. листинг 10), возвращающим следующий (очередной) элемент из объекта итерации.

Листинг 10. Минимальная реализация метода next
// бесконечный поток нулей
struct ZeroStream;

impl Iterator<int> for ZeroStream {
  fn next ( &mut self ) -> Option<int> {
    Some(0)
  }
}

Условие завершения итерации, то есть, условие при котором итератор обнаруживает, что содержимое объекта исчерпано, и сообщает об этом, определяется посредством возврата значения None вместо значения Some(item). Реализация такого условия показана в листинге 11.

Листинг 11. Реализация итератора с условием завершения
// последовательность заданного количества нулей
struct ZeroStream {
  priv remaining: uint
}

impl ZeroStream {
  fn new( n: uint ) -> ZeroStream {
    ZeroStream { remaining: n }
  }
}

impl Iterator<int> for ZeroStream {
  fn next( &mut self ) -> Option<int> {
    if self.remaining == 0 {
      None
    } else {
      self.remaining -= 1;
      Some(0)
    }
  }
}

Но, вообще говоря, нельзя полагаться на "правильное" поведение метода next() после того, как он вернул значение None. Некоторые итераторы могут не возвращать None. Поведение других итераторов может быть различным, и точно не определено.

7.1. Итераторы для контейнеров

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

  • iter() - для неизменяемых ссылок на элементы
  • mut_iter() - для изменяемых ссылок на элементы
  • move_iter() - для перемещения элементов (по значению)

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

Все перечисленные выше методы-итераторы представляют минимальный обычный набор реализации для типового изменяемого контейнера.

7.2. Циклы for

Конструкция цикла for является одним из основных инструментов работы с итераторами для контейнеров. В циклах for наиболее часто употребляются функции range() и range_inclusive(), позволяющие просто пройти по заданному диапазону значений, как показано в листинге 12.

Листинг 12. Примеры простых циклов for
for i in range( 0, 5 ) {   // функция range() импортирована по умолчанию
  print!( "{} ", i )   // выводит "0 1 2 3 4"
}

for i in std::iter::range_inclusive( 0, 5 ) {  // требуется явное импортирование
  print!( "{} ", i )   // выводит "0 1 2 3 4 5"
}

Цикл for может быть использован для работы с любым итератором, что демонстрирует код в листинге 13.

Листинг 13. Использование цикла for совместно с итератором для вектора
let xs = [2u, 3, 5, 7, 11, 13, 17];

// вывод всех элементов вектора
for x in xs.iter() {
  println( x.to_str() )
}

// пропуск первых 3 элементов вектора и вывод остальных
for x in xs.iter().skip(3) {
  println( x.to_str() )
}

В предыдущем примере в цикле for используется временный неизменяемый объект-итератор. Такое сочетание встречается чаще всего. Тем не менее, можно задействовать цикл for для более изощрённых операций, например, для работы с итератором, размещённым в изменяемой локации, как показано в листинге 14.

Листинг 14. Использование цикла for для работы с изменяемым объектом-итератором
let xs = [1, 2, 3, 4, 5];
let ys = ["one", "two", "three", "four"];

// создание изменяемого итератора, выдающего кортежи из элементов обоих векторов
let mut it = xs.iter().zip( ys.iter() );

// вывод пар элементов, пока не встретится пара (&3, &"three")
for (x, y) in it {
  println!( "{} {}", *x, *y );
  if *x == 3 {
    break;
  }
}

// получить и вывести самую последнюю пару элементов из итератора
println!( "last: {:?}", it.next() );

// проверить, завершил ли итератор работу полностью (все ли элементы обработаны)
assert!( it.next().is_none() );

7.3. Итераторы с произвольным доступом к контейнерам

В трэйте RandomAccessIterator представлен итератор, обеспечивающий произвольный доступ к любому элементу, содержащемуся в объекте-контейнере. Метод indexable() позволяет получить номер (индекс) элемента, а метод idx() обеспечивает доступ к элементу по его индексу. В листинге 15 показан пример работы итератора с произвольным доступом к элементам векторов.

Листинг 15. Использование итератора с произвольным доступом к содержимому векторов
let xs = [1, 2, 3, 4, 5];
let ys = ~[7, 9, 11];
let mut it = xs.iter().chain( ys.iter() );
println!( "{:?}", it.idx(0) );   // выводит "Some(&1)"
println!( "{:?}", it.idx(5) );   // выводит "Some(&7)"
println!( "{:?}", it.idx(7) );   // выводит "Some(&11)"
println!( "{:?}", it.idx(8) );   // выводит "None"

// извлечение двух элементов из начала объекта и одного с конца объекта
it.next();
it.next();
it.next_back();
// изменился диапазон работы итератора
println!( "{:?}", it.idx(0) );   // выводит "Some(&3)"
println!( "{:?}", it.idx(4) );   // выводит "Some(&9)"
println!( "{:?}", it.idx(6) );   // выводит "None"

В данном примере использован так называемый метод-адаптерchain(), выполняющий объединение объектов итерации. Такие методы-адаптеры итераторов часто используются для реализации различных алгоритмов обработки. Более подробно о методах-адаптерах можно узнать из документации.

Заключение

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


Ресурсы для скачивания


Похожие темы


Комментарии

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

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=40
Zone=Linux, Open source
ArticleID=951816
ArticleTitle=Rust - новый язык программирования: Часть 11. Векторы и строки. Контейнеры и итераторы.
publish-date=11052013