May 20th, 2010

Про итераторы

С тех пор, когда вообще додумались до того, что последовательность действий можно оформить в алгоритм, который к тому же выполнять не вручную, а отдать на выполнение компьютеру, утекло весьма много времени. И придумали в области написания программ преизрядно всякого. В том смысле, что не смотря на активный массовый быдлокодинг, отдельным гражданам всё-таки мечталось завязать с написанием одного и того же кода по сто раз на дню, от чего те стремились с нижних, близких железу уровней к уровням высоким, где накал абстракций особенно силён. И хотя такие абстракции зачастую сходу понять сложнее, чем if-else какой, в результате, после тренировки с ними всё равно как-то проще. И писать и думать. А ещё не только проще, но и меньше вдобавок.

Я, правда, в терминах машины Тьюринга никогда размышлять не пытался, да и ассемблер не жалую, поэтому в интуитивности машинного кода сильно неуверен, однако if-else в бейсиках, сях, да и вообще везде, есть мнение, однозначно интуитивней наследования объектов и всего такого прочего. С другой стороны, я даже представить себе не могу, каково это: написать, скажем, Ворд в терминах таких интуитивно понятных ифов и элсов. Вот в объектных терминах — да, представляю.

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

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

Список или, ещё лучше, коллекция — это набор условно однотипных элементов. Таких, которые хоть что-то общее хоть на каком-то уровне иерархии имеют. То есть, имеется хотя бы одна операция, которую можно проделать с каждым из них. Любая относительно длинная программа на каком угодно языке наверняка будет опираться на ненулевое число коллекций. Экстра важная штука.

Сейчас какой язык ни возьми, везде в той или иной мере будут представлены списки. Есть даже язык, которые чуть не только за ради списков был разработан — Lisp. Он сам себе список и списком при этом погоняет. Читать, правда, очень неудобно, поскольку запись инопланетная, но, тем не менее, изрядным прорывом он был. А так, даже в Бейсиках этих ваших уже были массивы — частный случай коллекции.

А если есть коллекция, то есть и действия над ней. Точнее, не столько над ней, сколько над её элементами и, иногда, над их взаимным расположением (что, впрочем, обычно сводится к сортировке). Раз так, нужен способ каким-то образом все элементы «обходить». И способ сей, по счастью, сейчас общеизвестен: итератор.

Итератор — суть абстракция, обладающая тремя свойствами:


  1. Его можно связать с интересующим нас множеством
  2. Ему можно говорить «дай следующий элемент»
  3. И его можно спрашивать «есть ли следующий элемент?», чем, вкупе с п. 2, не исключено, добиться посещения всех элементов этого множества


Как это обычно выглядит в Java Collapse )