Как RecursiveIteratorIterator работает в PHP?

88

Как RecursiveIteratorIteratorработает?

В руководстве по PHP нет ничего особо документированного или объясненного. В чем разница между IteratorIteratorи RecursiveIteratorIterator?

варуог
источник
2
есть пример на php.net/manual/en/recursiveiteratoriterator.construct.php, а также есть Введение на php.net/manual/en/class.iteratoriterator.php - не могли бы вы указать, что именно у вас есть проблемы с пониманием . Что должно содержаться в Руководстве, чтобы его было легче понять?
Гордон
1
Если вы спросите, как RecursiveIteratorIteratorработает, вы уже поняли, как IteratorIteratorработает? Я имею в виду, что это в основном одно и то же, только интерфейс, который они используют, отличается. И вас больше интересуют некоторые примеры или вы хотите увидеть разницу в базовой реализации кода C?
hakre
@Gordon, я не был уверен, как один цикл foreach может проходить по всем элементам в древовидной структуре
varuog
@hakra Теперь я пытаюсь изучить все встроенные интерфейсы, а также реализацию интерфейса spl и итератора. Мне было интересно узнать, как это работает в фоновом режиме с циклом forach с некоторыми примерами.
varuog 07
@hakre На самом деле они оба очень разные. IteratorIteratorкарты Iteratorи IteratorAggregateв Iterator, где REcusiveIteratorIteratorиспользуется для обратного ходаRecursiveIterator
Адам

Ответы:

251

RecursiveIteratorIterator- это конкретная Iteratorреализация обхода дерева . Он позволяет программисту перемещаться по объекту-контейнеру, реализующему RecursiveIteratorинтерфейс. Общие принципы, типы, семантика и шаблоны итераторов см. В разделе « Итератор» в Википедии .

В отличие от IteratorIteratorконкретного Iteratorреализуемого обхода объекта в линейном порядке (и по умолчанию принимающего любой тип Traversableв своем конструкторе), RecursiveIteratorIteratorпозволяет выполнять цикл по всем узлам в упорядоченном дереве объектов, а его конструктор принимает RecursiveIterator.

Вкратце: RecursiveIteratorIteratorпозволяет перебирать дерево, IteratorIteratorпозволяет перебирать список. Я покажу это на некоторых примерах кода ниже.

Технически это работает путем выхода из линейности путем обхода всех дочерних узлов (если таковые имеются). Это возможно, потому что по определению все дочерние элементы узла снова являются RecursiveIterator. Затем верхний уровень Iteratorвнутренне складывает различные RecursiveIterators по их глубине и сохраняет указатель на текущий активный подпрограмм Iteratorдля обхода.

Это позволяет посещать все узлы дерева.

Основные принципы такие же, как и в случае IteratorIterator: интерфейс определяет тип итерации, а базовый класс итератора является реализацией этой семантики. Сравните с примерами ниже, для линейного цикла foreachвы обычно не задумываетесь о деталях реализации, если вам не нужно определять новый Iterator(например, когда какой-то конкретный тип сам по себе не реализуется Traversable).

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

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

Кратко о технических отличиях:

  • Хотя для линейного обхода IteratorIteratorтребуется любое Traversable, RecursiveIteratorIteratorтребуется более конкретное RecursiveIteratorдля циклического обхода дерева.
  • Где IteratorIteratorпредоставляет свое основное переходное Iteratorотверстие getInnerIerator(), RecursiveIteratorIteratorпредоставляет текущий активный вспомогательный Iteratorтолько через этот метод.
  • Хотя IteratorIteratorсовершенно ничего не известно о родителях или детях, но также RecursiveIteratorIteratorзнает, как получить и пересечь детей.
  • IteratorIteratorне нуждается в стеке итераторов, RecursiveIteratorIteratorимеет такой стек и знает активный суб-итератор.
  • Где IteratorIteratorимеет свой порядок из-за линейности и отсутствия выбора, RecursiveIteratorIteratorимеет выбор для дальнейшего обхода и должен решать для каждого узла (определяется с помощью режима perRecursiveIteratorIterator ).
  • RecursiveIteratorIteratorимеет больше методов, чем IteratorIterator.

Подводя итог: RecursiveIteratorэто конкретный тип итерации (цикл по дереву), который работает на собственных итераторах, а именно RecursiveIterator. Это тот же основной принцип, что и с IteratorIerator, но тип итерации другой (линейный порядок).

В идеале вы также можете создать свой собственный набор. Единственное, что необходимо, это чтобы ваш итератор реализовал то, Traversableчто возможно через Iteratorили IteratorAggregate. Тогда вы можете использовать его с foreach. Например, некоторый вид рекурсивного объекта итерации обхода троичного дерева вместе с соответствующим интерфейсом итерации для объекта (ов) контейнера.


Давайте рассмотрим несколько примеров из реальной жизни, которые не являются настолько абстрактными. Между интерфейсами, конкретными итераторами, контейнерными объектами и семантикой итераций это, возможно, не такая уж плохая идея.

В качестве примера возьмем список каталогов. Предположим, у вас есть следующее дерево файлов и каталогов на диске:

Дерево каталогов

В то время как итератор с линейным порядком просто перемещается по папке и файлам верхнего уровня (один листинг каталогов), рекурсивный итератор также проходит по вложенным папкам и перечисляет все папки и файлы (список каталогов со списками его подкаталогов):

Non-Recursive        Recursive
=============        =========

   [tree]            [tree]
    ├ dirA            ├ dirA
    └ fileA           │ ├ dirB
                      │ │ └ fileD
                      │ ├ fileB
                      │ └ fileC
                      └ fileA

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

Сначала очень простой пример с микросхемой DirectoryIterator, реализующий Traversableкоторый позволяет foreachдля итерации над ним:

$path = 'tree';
$dir  = new DirectoryIterator($path);

echo "[$path]\n";
foreach ($dir as $file) {
    echo " ├ $file\n";
}

Примерный результат для структуры каталогов выше:

[tree]
 ├ .
 ├ ..
 ├ dirA
 ├ fileA

Как видите, здесь еще не используется IteratorIteratorили RecursiveIteratorIterator. Вместо этого он просто использует foreachто, что работает с Traversableинтерфейсом.

Поскольку foreachпо умолчанию известен только тип итерации с именем linear order, мы могли бы явно указать тип итерации. На первый взгляд это может показаться слишком многословным, но для демонстрационных целей (и чтобы разница была RecursiveIteratorIteratorболее заметной позже), давайте укажем линейный тип итерации, явно указав IteratorIteratorтип итерации для списка каталогов:

$files = new IteratorIterator($dir);

echo "[$path]\n";
foreach ($files as $file) {
    echo " ├ $file\n";
}

Этот пример почти идентичен первому, разница в том, что $filesтеперь это IteratorIteratorтип итерации для Traversable $dir:

$files = new IteratorIterator($dir);

Как обычно, итерация выполняется foreach:

foreach ($files as $file) {

Результат точно такой же. Так что же другое? Другой объект, используемый в foreach. В первом примере это. Во DirectoryIteratorвтором примере это IteratorIterator. Это показывает гибкость итераторов: вы можете заменять их друг на друга, код внутри foreachпросто продолжает работать должным образом.

Приступим к получению всего списка, включая подкаталоги.

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

Мы знаем, что теперь нам нужно пройти все дерево, а не только первый уровень. Для того, чтобы иметь эту работу с простым foreachнам нужен другой тип итератора: RecursiveIteratorIterator. И это можно делать только по объектам контейнера, у которых есть RecursiveIteratorинтерфейс .

Интерфейс - это контракт. Любой класс, реализующий его, можно использовать вместе с RecursiveIteratorIterator. Примером такого класса является RecursiveDirectoryIterator, что-то вроде рекурсивного варианта DirectoryIterator.

Давайте посмотрим на первый пример кода, прежде чем писать любое другое предложение с I-словом:

$dir  = new RecursiveDirectoryIterator($path);

echo "[$path]\n";
foreach ($dir as $file) {
    echo " ├ $file\n";
}

Этот третий пример почти идентичен первому, однако он создает другой результат:

[tree]
 ├ tree\.
 ├ tree\..
 ├ tree\dirA
 ├ tree\fileA

Хорошо, не так уж и много, имя файла теперь содержит путь впереди, но остальное тоже похоже.

Как показывает пример, даже объект каталога уже реализует RecursiveIteratorинтерфейс, этого еще недостаточно для foreachобхода всего дерева каталогов. Здесь RecursiveIteratorIteratorвступает в действие. Пример 4 показывает, как:

$files = new RecursiveIteratorIterator($dir);

echo "[$path]\n";
foreach ($files as $file) {
    echo " ├ $file\n";
}

Использование RecursiveIteratorIteratorвместо предыдущего $dirобъекта приведет foreachк рекурсивному обходу всех файлов и каталогов. Затем в нем перечислены все файлы, так как тип итерации объекта уже указан:

[tree]
 ├ tree\.
 ├ tree\..
 ├ tree\dirA\.
 ├ tree\dirA\..
 ├ tree\dirA\dirB\.
 ├ tree\dirA\dirB\..
 ├ tree\dirA\dirB\fileD
 ├ tree\dirA\fileB
 ├ tree\dirA\fileC
 ├ tree\fileA

Это уже должно продемонстрировать разницу между обходом по плоскости и по дереву. RecursiveIteratorIteratorМожет пройти любую древовидную структуру в виде списка элементов. Поскольку существует больше информации (например, уровень, на котором итерация происходит в настоящее время), можно получить доступ к объекту итератора во время итерации по нему и, например, сделать отступ для вывода:

echo "[$path]\n";
foreach ($files as $file) {
    $indent = str_repeat('   ', $files->getDepth());
    echo $indent, " ├ $file\n";
}

И вывод примера 5 :

[tree]
 ├ tree\.
 ├ tree\..
    ├ tree\dirA\.
    ├ tree\dirA\..
       ├ tree\dirA\dirB\.
       ├ tree\dirA\dirB\..
       ├ tree\dirA\dirB\fileD
    ├ tree\dirA\fileB
    ├ tree\dirA\fileC
 ├ tree\fileA

Конечно, это не победа в конкурсе красоты, но показывает, что с рекурсивным итератором доступно больше информации, чем просто линейный порядок ключа и значения . Даже foreachможет выражать только такую ​​линейность, доступ к самому итератору позволяет получить больше информации.

Подобно метаинформации, существуют также различные способы обхода дерева и, следовательно, упорядочивания вывода. Это режим изRecursiveIteratorIterator и он может быть установлен с помощью конструктора.

В следующем примере будет сказано RecursiveDirectoryIteratorудалить записи с точками ( .и ..), поскольку они нам не нужны. Но также будет изменен режим рекурсии, чтобы родительский элемент (подкаталог) сначала ( SELF_FIRST) принимал дочерние элементы ( файлы и подкаталоги в подкаталоге):

$dir  = new RecursiveDirectoryIterator($path, RecursiveDirectoryIterator::SKIP_DOTS);
$files = new RecursiveIteratorIterator($dir, RecursiveIteratorIterator::SELF_FIRST);

echo "[$path]\n";
foreach ($files as $file) {
    $indent = str_repeat('   ', $files->getDepth());
    echo $indent, " ├ $file\n";
}

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

[tree]
 ├ tree\dirA
    ├ tree\dirA\dirB
       ├ tree\dirA\dirB\fileD
    ├ tree\dirA\fileB
    ├ tree\dirA\fileC
 ├ tree\fileA

Таким образом, режим рекурсии управляет тем, что и когда возвращается ветвь или лист в дереве, для примера каталога:

  • LEAVES_ONLY (по умолчанию): только список файлов, без каталогов.
  • SELF_FIRST (вверху): Список каталога, а затем файлы в нем.
  • CHILD_FIRST (без примера): сначала перечислите файлы в подкаталоге, затем в каталоге.

Результат примера 5 с двумя другими режимами:

  LEAVES_ONLY                           CHILD_FIRST

  [tree]                                [tree]
         ├ tree\dirA\dirB\fileD                ├ tree\dirA\dirB\fileD
      ├ tree\dirA\fileB                     ├ tree\dirA\dirB
      ├ tree\dirA\fileC                     ├ tree\dirA\fileB
   ├ tree\fileA                             ├ tree\dirA\fileC
                                        ├ tree\dirA
                                        ├ tree\fileA

Если сравнить это со стандартным обходом, все это недоступно. Таким образом, рекурсивная итерация немного сложнее, когда вам нужно обдумать ее, однако ее легко использовать, потому что она ведет себя так же, как итератор, вы помещаете ее в a foreachи готово.

Думаю, этого достаточно для одного ответа. Вы можете найти полный исходный код, а также пример отображения красивых ascii-деревьев в этой сущности: https://gist.github.com/3599532

Сделай сам: сделай RecursiveTreeIteratorработу строка за строкой.

Пример 5 продемонстрировал наличие метаинформации о состоянии итератора. Однако в рамках foreachитерации это было целенаправленно продемонстрировано . В реальной жизни это, естественно, принадлежит внутри RecursiveIterator.

Лучшим примером является то RecursiveTreeIterator, что он заботится об отступах, префиксе и так далее. См. Следующий фрагмент кода:

$dir   = new RecursiveDirectoryIterator($path, RecursiveDirectoryIterator::SKIP_DOTS);
$lines = new RecursiveTreeIterator($dir);
$unicodeTreePrefix($lines);
echo "[$path]\n", implode("\n", iterator_to_array($lines));

Он RecursiveTreeIteratorпредназначен для работы построчно, вывод довольно прост с одной небольшой проблемой:

[tree]
 ├ tree\dirA
 │ ├ tree\dirA\dirB
 │ │ └ tree\dirA\dirB\fileD
 │ ├ tree\dirA\fileB
 │ └ tree\dirA\fileC
 └ tree\fileA

При использовании в сочетании с a RecursiveDirectoryIteratorон отображает полный путь, а не только имя файла. В остальном выглядит неплохо. Это потому, что имена файлов генерируются SplFileInfo. Вместо этого они должны отображаться как базовое имя. Желаемый результат следующий:

/// Solved ///

[tree]
 ├ dirA
 │ ├ dirB
 │ │ └ fileD
 │ ├ fileB
 │ └ fileC
 └ fileA

Создайте класс декоратора, который можно использовать RecursiveTreeIteratorвместо RecursiveDirectoryIterator. Он должен предоставлять базовое имя текущего SplFileInfoвместо имени пути. Окончательный фрагмент кода мог бы выглядеть так:

$lines = new RecursiveTreeIterator(
    new DiyRecursiveDecorator($dir)
);
$unicodeTreePrefix($lines);
echo "[$path]\n", implode("\n", iterator_to_array($lines));

Эти фрагменты, в том числе, $unicodeTreePrefixявляются частью сути Приложения «Сделай сам: сделай RecursiveTreeIteratorработу линия за строкой». .

hakre
источник
Он не отвечает на поставленные вопросы, содержит фактические ошибки и упускает ключевые моменты, когда вы переходите к настройке итерации. В общем, это выглядит как неудачная попытка получить награду за тему, о которой вы мало знаете или, если да, то не можете дать ответ на поставленные вопросы.
Салате 02
2
Что ж, это не отвечает на мой вопрос "почему", вы просто произносите больше слов, не говоря много. Может быть, вы начнете с действительно важной ошибки? Укажите на это, не держите в секрете.
hakre
Самое первое предложение неверно: «RecursiveIteratorIterator - это IteratorIterator, который поддерживает…», это неверно.
Салате 02
1
@salathe: Благодарим вас за отзывы. Я отредактировал ответ, чтобы адресовать его. Первое предложение действительно было неправильным и неполным. Я все еще не упомянул конкретные детали реализации, RecursiveIteratorIteratorпотому что это похоже на другие типы, но я дал некоторую техническую информацию о том, как это работает. Примеры, на мой взгляд, хорошо показывают различия: тип итерации является основным различием между ними. Понятия не имею, если вы покупаете тип итерации, вы делаете его немного по-другому, но ИМХО нелегко с семантикой типов итераций.
hakre
1
Первая часть несколько улучшена, но как только вы начнете переходить к примерам, она все равно приведет к фактическим неточностям. Если бы вы обрезали ответ по горизонтальной линейке, он был бы намного лучше.
Салате
32

В чем разница IteratorIteratorи RecursiveIteratorIterator?

Чтобы понять разницу между этими двумя итераторами, нужно сначала немного понять используемые соглашения об именах и то, что мы подразумеваем под «рекурсивными» итераторами.

Рекурсивные и нерекурсивные итераторы

PHP имеет нерекурсивные итераторы, такие как ArrayIteratorи FilesystemIterator. Существуют также «рекурсивные» итераторы, такие как RecursiveArrayIteratorи RecursiveDirectoryIterator. У последних есть методы, позволяющие исследовать их, а у первых - нет.

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

Рекурсивные итераторы реализуют рекурсивное поведение (через hasChildren(), getChildren()), но не используют его.

Было бы лучше думать о рекурсивных итераторах как о «рекурсивных» итераторах, у них есть возможность рекурсивно повторяться, но простое повторение экземпляра одного из этих классов этого не сделает. Чтобы использовать рекурсивное поведение, продолжайте читать.

RecursiveIteratorIterator

Вот RecursiveIteratorIteratorтут-то и пригодится. Он знает, как вызывать «рекурсивные» итераторы таким образом, чтобы детализировать структуру в обычном плоском цикле. Он приводит в действие рекурсивное поведение. По сути, он выполняет работу по обходу каждого из значений в итераторе, проверяя, есть ли «дочерние элементы», в которые нужно рекурсивно или нет, а также входя и выходя из этих наборов дочерних элементов. Вы вставляете экземпляр RecursiveIteratorIteratorв foreach, и он погружается в структуру, так что вам не нужно.

Если бы RecursiveIteratorIteratorне использовался, вам пришлось бы написать свои собственные рекурсивные циклы для использования рекурсивного поведения, проверяя «рекурсивный» итератор hasChildren()и используя getChildren().

Итак, это краткий обзор того RecursiveIteratorIterator, чем он отличается от IteratorIterator? Ну, вы в основном задаете тот же вопрос, что и в чем разница между котенком и деревом? Тот факт, что оба они представлены в одной энциклопедии (или руководстве для итераторов), не означает, что вы должны запутаться между ними.

Итератор

Задача IteratorIterator- взять любой Traversableобъект и обернуть его так, чтобы он удовлетворял Iteratorинтерфейсу. Использование для этого состоит в том, чтобы затем иметь возможность применить специфичное для итератора поведение к объекту, не являющемуся итератором.

Чтобы привести практический пример, DatePeriodкласс, Traversableно не класс Iterator. Таким образом, мы можем перебирать его значения, foreach()но не можем делать другие вещи, которые обычно выполнялись бы с итератором, например фильтрацию.

ЗАДАЧА : Обсудите понедельник, среду и пятницу следующих четырех недель.

Да, это тривиально: foreachперебрать DatePeriodи использовать if()внутри цикла; но не в этом суть этого примера!

$period = new DatePeriod(new DateTime, new DateInterval('P1D'), 28);
$dates  = new CallbackFilterIterator($period, function ($date) {
    return in_array($date->format('l'), array('Monday', 'Wednesday', 'Friday'));
});
foreach ($dates as $date) { … }

Приведенный выше фрагмент не будет работать, потому что CallbackFilterIteratorожидает экземпляр класса, реализующего Iteratorинтерфейс, а DatePeriodэто не так. Однако, поскольку это так, Traversableмы можем легко удовлетворить это требование, используя IteratorIterator.

$period = new IteratorIterator(new DatePeriod(…));

Как видите, это не имеет никакого отношения ни к переборам классов итераторов, ни к рекурсии, и в этом заключается разница между IteratorIteratorи RecursiveIteratorIterator.

Резюме

RecursiveIteraratorIteratorпредназначен для перебора RecursiveIterator(«рекурсивного» итератора) с использованием доступного рекурсивного поведения.

IteratorIteratorпредназначен для применения Iteratorповедения к Traversableобъектам, не являющимся итератором .

салате
источник
Разве это не IteratorIteratorстандартный тип обхода линейного порядка для Traversableобъектов? Те, которые можно было бы использовать без него, foreachкак есть? И даже более того, не RecursiveIterator всегда ли a Traversableи, следовательно, не только, IteratorIteratorно и RecursiveIteratorIteratorвсегда, «для применения Iteratorповедения к не-итератору, проходимым объектам» ? (Теперь я бы сказал, что foreachприменяет тип итерации через объект-итератор к объектам-контейнерам, которые реализуют интерфейс типа итератора, поэтому они всегда являются объектами-итераторами Traversable)
hakre 02
Как говорится в моем ответе, IteratorIteratorэто класс, предназначенный для упаковки Traversableобъектов в Iterator. Больше ничего . Кажется, вы применяете этот термин в более общем смысле.
Салате
Вроде информативный ответ. Один вопрос, не будет ли RecursiveIteratorIterator также обертывать объекты, чтобы они также имели доступ к поведению Iterator? Единственная разница между ними будет в том, что RecursiveIteratorIterator может выполнять детализацию, а IteratorIterator - нет?
Mike Purcell
@salathe, вы знаете, почему рекурсивный итератор (RecursiveDirectoryIterator) не реализует поведение hasChildren (), getChildren ()?
anru 08
8
+1 за слова «рекурсивный». Это имя надолго сбило меня с пути, потому что Recursivein RecursiveIteratorподразумевает поведение, тогда как более подходящим именем было бы то, которое описывает возможности, например RecursibleIterator.
goat
0

При использовании iterator_to_array(), RecursiveIteratorIteratorрекурсивно проходит массив , чтобы найти все значения. Это означает, что он сгладит исходный массив.

IteratorIterator сохранит исходную иерархическую структуру.

Этот пример ясно покажет вам разницу:

$array = array(
               'ford',
               'model' => 'F150',
               'color' => 'blue', 
               'options' => array('radio' => 'satellite')
               );

$recursiveIterator = new RecursiveIteratorIterator(new RecursiveArrayIterator($array));
var_dump(iterator_to_array($recursiveIterator, true));

$iterator = new IteratorIterator(new ArrayIterator($array));
var_dump(iterator_to_array($iterator,true));
Чупи
источник
Это полное заблуждение. new IteratorIterator(new ArrayIterator($array))эквивалентно new ArrayIterator($array), то есть внешний IteratorIteratorничего не делает. Более того, сглаживание вывода не имеет ничего общего iterator_to_array- оно просто преобразует итератор в массив. Сглаживание - это свойство способа RecursiveArrayIteratorобхода внутреннего итератора.
Quolonel Questions
0

RecursiveDirectoryIterator отображает полный путь, а не только имя файла. В остальном выглядит неплохо. Это потому, что имена файлов генерируются SplFileInfo. Вместо этого они должны отображаться как базовое имя. Желаемый результат следующий:

$path =__DIR__;
$dir = new RecursiveDirectoryIterator($path, FilesystemIterator::SKIP_DOTS);
$files = new RecursiveIteratorIterator($dir,RecursiveIteratorIterator::SELF_FIRST);
while ($files->valid()) {
    $file = $files->current();
    $filename = $file->getFilename();
    $deep = $files->getDepth();
    $indent = str_repeat('│ ', $deep);
    $files->next();
    $valid = $files->valid();
    if ($valid and ($files->getDepth() - 1 == $deep or $files->getDepth() == $deep)) {
        echo $indent, "├ $filename\n";
    } else {
        echo $indent, "└ $filename\n";
    }
}

выход:

tree
 ├ dirA
 │ ├ dirB
 │ │ └ fileD
 │ ├ fileB
 │ └ fileC
 └ fileA
Джавад шариат
источник