Java итератор

Есть еще одно средство, предоставляемое Java, которое позволяет писать компактный код – это итератор. Именно об этом мы и поговорим в данном материале.

Итак, мы хотим позволить клиенту перебирать элементы в коллекции. Но у нас нет клиента, чтобы знать, используем ли мы массив или список ссылок или какое-либо внутреннее представление, которое мы могли бы иметь в виду. Это не имеет отношения к клиенту. И многие клиенты только хотят просто перебирать вещи в коллекции. И Java предоставляет хорошее решение для этой так называемой итерации.



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

public interface Iterable
{
Iterator<Item> iterator();
}

Ну, в Java lingo, Iterable, это класс, который имеет метод, который возвращает итератор. Так что же такое итератор? Ну итератор-это что-то, класс, который имеет методы hasNext() и Next(). Java также позволяет удалить (). Мы думаем, что одна плохая новость, мы не используем его может привести к коварной проблеме отладки ошибок. Итак, это hasNext() и next() и поэтому, чтобы сделать структуру данных итеративной, мы собираемся реализовать эти вещи.

public interface Iterator<Item>
{
boolean hasNext();
Item next();
void remove();
}

Кажется, что у нас много багажа, и причина, по которой мы это делаем, почему мы идем на это, заключается в том, что мы можем, если у нас есть структура данных, которая повторяется, мы можем использовать очень компактный и элегантный клиентский код на Java, так называемый оператор for-each. Поэтому, если у нас есть стек, мы можем сказать - (для строки s : stack). Это означает для каждой строки в стеке - распечатать его.

Iterator i = stack.iterator();
while (i.hasNext())
{
String s = i.next();
StdOut.println(s);
}

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

Вот как это выглядит для списка ссылок.

import java.util.Iterator;
public class Stack<Item> implements Iterable
{
...
public Iterator iterator() { return new ListIterator(); }
private class ListIterator implements Iterator<Item>
{
private Node current = first;
public boolean hasNext() { return current != null; }
public void remove() { /* not supported */ }
public Item next()
{
Item item = current.item;
current = current.next;
return item;
}
}
}

Итак, он должен реализовать Iterable так что же это значит реализовать Iterable? Он должен иметь метод iterator (), который возвращает итератор. Так что же такое итератор?

Мы собираемся использовать внутренний класс. В этом случае мы будем называть его ListIterator, который реализует Iterator и является универсальным. И в основном то, что эта вещь должна сделать, это реализовать эти методы hasNext() и next(). А семантика просто понятна из названий. hasNext () должен if, if we'Re done должен возвращать false.

Если мы не закончили, мы должны вернуть true, а next() должен дать следующий элемент в итерации. Поэтому, если дело в связанном списке, мы начнем сначала. У нас есть это, наш первый элемент в списке, и мы собираемся поддерживать переменную экземпляра current внутри этого итератора, который является текущей вещью, которую мы повторяем. Итак, получите следующий, как если бы мы хотели удалить первый.

Мы вытаскиваем текущий элемент, а затем продвигаем текущую ссылку и возвращаем элемент. Перемещение тока на следующее место. Клиент всегда будет тестировать hasNext (), как я показал, как я показал, и что заглушка код до и поэтому, когда он получает null он будет возвращать false в итерационной остановки. Но для нашей итерации нам просто нужно беспокоиться о реализации next() и hasNext() и, возможно, использовать локальную переменную экземпляра, чтобы сделать это.

import java.util.Iterator;
public class Stack implements Iterable
{
…
public Iterator iterator()
{ return new ReverseArrayIterator(); }
private class ReverseArrayIterator implements Iterator
{
private int i = N;
public boolean hasNext() { return i > 0; }
public void remove() { /* not supported */ }
public Item next() { return s[--i]; }
}
}

Мы должны, вероятно, сделать пуленепробиваемые исключения кода, если клиент пытается вызвать next() без каких - либо элементов и пытается вызвать remove() вообще, мы не будем поддерживать remove(). Для, и для массива, это еще проще. Итак, теперь с итератором у нас есть контроль над тем, в каком порядке мы проходим через элементы, и поэтому это будет идти вместе с семантикой и структурой данных, поэтому, вероятно, в стеке вы хотите получить вещи в порядке стека, например, порядок, который выходит из стека, так что это обратный порядок в массиве, поэтому в этом случае next() просто декремент и возвращает следующий, а наша переменная экземпляра является индексом в массиве.

И тогда hasNext () в порядке, пока эта вещь положительна. Итак, немного кода Java чтобы обеспечить эту итерацию, но на самом деле в этой структуре не слишком много, и вы можете увидеть, как реализовать это для своего собственного типа данных, и мы будем использовать эту парадигму для каждого базового типа данных, который мы, который включает в себя коллекции объектов, с которыми мы столкнемся.

Хорошо, и на самом деле, это приводит нас к тому, что на самом деле для многих клиентов не имеет значения, какой заказ мы получаем. Очень часто мы просто вставляем элементы в коллекцию, а затем, позже, повторяем элементы, которые у нас есть. Эта структура данных называется сумкой, поэтому давайте посмотрим, как выглядит этот API.



Заказ не имеет значения, поэтому все, что мы хотим сделать, это добавить элемент, возможно, вы хотите знать размер, и мы хотим, чтобы перебрать все элементы в сумке. Таким образом, это более простой, более узкий API, но все же он выражает важную небольшую коллекцию операций, и мы будем использовать этот, и мы уже видели реализации. Вы просто берете стек и удаляете pop, или очередь и удаляете dequeue и у вас есть прекрасная реализация полезной структуры данных.