Итерация структур данных с помощью цикла for-of и их распространение с помощью оператора распространения (…).

Итераторы и генераторы существуют уже давно. Они изменили способ перебора значений объекта. Раньше мы использовали цикл for-in для итерации значений, но не было гарантии порядка, в котором будут повторяться значения. Кроме того, это было довольно громоздко, потому что нам приходилось использовать ключи из цикла for-in для получения значений. Генератор и итераторы избавляют от необходимости повторять объекты. Чтобы объект был итеративным, он просто должен соответствовать протоколам итераций. В этом посте дается краткий обзор генераторов и итераторов / итераций, а также объясняется, как сделать общие структуры данных повторяемыми.

Протоколы итераций

С появлением ES5 в JavaScript появилось два итерационных протокола: Iterable Protocol и Iterator Protocol.

Итерационный протокол

Чтобы объект был итерируемым, он должен иметь метод итератора. Метод итератора определяется с помощью ключа @@iterator, т.е. константы Symbol.iterator. Метод итератора может быть любой функцией javascript, которая принимает нулевые аргументы и возвращает объект, соответствующий протоколу итератора (скоро будет обсуждаться). Вот пример кода, если вы запутались в жаргоне.

Протокол итератора

Протокол итератора определяет стандартный способ создания последовательности значений (конечных или бесконечных) и, возможно, возвращаемого значения, когда все значения были сгенерированы. ~ MDN

Чтобы объект стал объектом итератора, он должен реализовать метод next, который удовлетворяет следующим критериям:

  1. Не должно быть аргументов. Хотя вы можете передавать аргументы в next, и не будет никаких ошибок, но вы не должны вызывать, когда ваш итерируемый объект будет использоваться с оператором spread или for-of циклом, вы не сможете передавать какие-либо аргументы.
  2. Он должен возвращать объект, по крайней мере, с одним из двух свойств.
  • value: любое значение javascript, которое мы хотим вернуть нашим итератором.
  • done: логический флаг, указывающий, достигли ли мы конца последовательности или нет.

Вот пример быстрого итератора диапазона, заимствованный из MDN.

Генераторы

Иногда явное поддержание внутреннего состояния итераторов и возврат повторяемого объекта - это слишком большая работа. Генераторы сокращают этот объем работы и предоставляют альтернативный подход, позволяющий сделать объект итерируемым с помощью ключевого слова yield. Функции генераторов имеют особый синтаксис. Они записываются как function *. Вы можете прочитать подробнее о генераторах здесь.

Вот наш предыдущий пример, переписанный с помощью генераторов.

Хорошо, хватит об итераторах и генераторах. Давайте использовать их с общими структурами данных, такими как LinkedList, Stack, BinaryTree.

LinkedList

LinkedList - это линейные структуры данных, в которых каждый узел / элемент содержит данные и указатель на следующий узел. Начало и конец списка называются head и tail. Вот реализация связанного списка.

Нам нужно добавить итератор, чтобы сделать связанный список повторяемым. Наша функция итератора будет иметь внутреннюю переменную состояния с именем current (которая изначально относится к head), представляющая текущий узел, на котором мы находимся. Каждый вызов next будет возвращать данные узла current и перемещать узел current на узел next. Когда метод next завершает обход всех узлов, он возвращает done как true, чтобы остановить итерацию.

Генераторная версия вышеперечисленного.

Вы можете найти полный код здесь.

Куча

Стек - это линейная структура данных, которая следует шаблону Last In First Out (LIFO), что означает, что элементы, вставленные в стек последними, будут отсортированы первыми. Чтобы все было СУХИМ, мы будем использовать нашу более раннюю структуру данных Linked List для реализации Stack. Мы также будем использовать его метод итератора, чтобы сделать наш стек повторяемым.

Двоичное дерево

Двоичное дерево - это подкласс структуры данных Tree. В двоичном дереве каждый узел может иметь максимум 2 дочерних элемента, называемых left и right. Вы можете прочитать больше о двоичных деревьях в моем посте Немного о двоичных деревьях. Поскольку деревья представляют собой нелинейную структуру данных, их можно перемещать разными способами. Мы реализуем их обход уровня или первого порядка ширины в нашем методе итератора. Вот класс, который представляет BinaryTreeNode для нашего BinaryTree.

И, наконец, BinaryTree с методом итератора.

Что ж, это все о структурах данных с итерабельным протоколом. Я создал git-репозиторий примеров, использованных в этом посте. Надеюсь, они вам пригодятся. Спасибо за чтение 🙏🏻.