В предыдущей части мы обсудили самый базовый тип коллекций – массивы. Кроме массивов, существуют ещё специализированные типы, такие как множество, список, дерево, очередь и т.д. Но перед тем, как говорить о них, нужно познакомиться с итераторами.
Итерация – это повторение. Итератор – тот, кто выполняет повторение.
Для того, чтобы перебрать элементы массива по одному, обычно применяют цикл. Цикл это тоже своего рода итератор:
a = [10, 20, 30];
for (i = 0; i < 3; i++) print(a[i]);
Какие допущения здесь используются?
- Элементы массива имеют целочисленные непрерывные смещения: a[0], a[1], a[2]
- Переменная i в цикле также непрерывно принимает значения 0, 1, 2, и значит, когда мы пишем a[i], то получаем доступ к каждому элементу массива по очереди
Но как обсуждалось ранее, массивы-коллекции это не классические массивы. Они могут иметь пропуски в смещениях, они также могут иметь не числовые, а символьные смещения – правильнее называть их уже не смещениями, а ключами.
Стало быть, не каждую коллекцию можно перебрать, просто увеличивая на 1 целочисленное смещение. Чтобы перебирать элементы с произвольными ключами, либо сама коллекция, либо сам язык должны предоставлять интерфейс, называемый "итератор". Такой интерфейс сам знает, как устроена коллекция и как получать доступ к её элементам. А для нас он предоставляет методы вроде "дай следующий элемент".
Давайте посмотрим, как это реализовано в разных языках. Задача – не выучить какой-то конкретный язык, а понять общие закономерности.
1. Некоторые языки имеют специальную форму оператора for или foreach:
Python
collection = [10, 20, 30]
for x in collection: print(x)
PHP
$collection = [10, 20, 30];
foreach ($collection as $x) print $x;
JavaScript
var collection = [10, 20, 30];
for (var key in collection) console.log(collection[key]);
По сути, организуется тот же цикл for, только мы не задаём, с чего его начинать и как продолжать. Мы просто передаём в этот цикл объект-коллекцию, который имеет интерфейс итератора. И цикл сам с ним разбирается.
Эти циклы имеют небольшие отличия, кроме синтаксиса. В Python и в PHP итератор перебирает сами элементы коллекции, то есть переменная x становится равна 10, 20, 30.
В JavaScript итератор перебирает не элементы, а их ключи. Соответственно, переменная key в данном случае будет становиться равной 0, 1, 2, а сами элементы мы будем получать через collection[key]. Пусть вас не обманывают ключи 0, 1, 2, которые ничем не отличаются от смещений классического массива. Просто сейчас так совпало.
2. Некоторые языки имеют оператор next():
Python
x = next(collection)
PHP
$x = next($collection);
Думаю, здесь всё очевидно – данный оператор при каждом его вызове возвращает следующий элемент из коллекции, пока не дойдет до конца. В конце он вернет или false, или какую-нибудь ошибку, которую можно обработать.
3. Итераторы как отдельные объекты
Это самый универсальный способ. Имея коллекцию, мы можем попросить у неё: "дай мне итератор, чтобы я мог перебрать твои элементы". Условно это будет выглядеть так:
iterator = collection.getIterator()
Или ещё проще: коллекция сама по себе может иметь интерфейс итератора, то есть вышеописанный шаг можно пропустить.
А что, если коллекция не может дать нам итератор? А тогда это будет уже не коллекция :)
Теперь, имея объект-итератор, который, само собой, поддерживает интерфейс итератора, мы можем пользоваться этим интерфейсом. Например, там должен быть всё тот же метод next(), выдающий следующий элемент, а также метод hasNext(), который сообщает, остались ли ещё элементы для перебора. С помощью таких методов мы можем организовать собственный цикл перебора:
while(iterator.hasNext()) print(iterator.next())
Мы даже можем написать свою коллекцию со своим собственным итератором, если понадобится. Поэтому понятия коллекций и итераторов относятся не только к готовым возможностям, которые есть в языке. Они общие и универсальные.
Я перечислил только основные методы итераторов, но в каждом языке можно найти подробности про остальные методы. Итераторы могут делать разные вещи, такие как переходить на начало коллекции, удалять или добавлять элементы в коллекции и т.п.
Встретимся в следующем выпуске!