\(6.3\)迭代

1.增强型\(for\)循环

  我们知道，可以用以下\(for\)语句实现对数组元素的遍历：

Set<String> s = new HashSet<>();
...
for (String city : s) {
    ...
}

  这与下面的程序等价：

Set<String> s = new HashSet<>();
...
Iterator<String> seer = s.iterator();
while (seer.hasNext()) {
    String city = seer.next();
    ...
}

  这个程序的关键在于被称作迭代器(\(iterator\))的对象。我们可以使用如下方法返回一个迭代器对象：

public Iterator<E> iterator();

  例如，我们可以通过如下语句实现对\(List\)的迭代遍历：

List<Integer> friends = new ArrayList<Integer>();
...
Iterator<Integer> seer = friends.iterator();

while (seer.hasNext()) {
System.out.println(seer.next());
}

  这个迭代器有三个关键方法：

1. 获得迭代器对象：Iterator<Integer> seer = friends.iterator();。
2. 检测是否有对象剩余：seer.hasNext()。
3. 返回当前对象、并使迭代器前进一个对象：seer.next()。

2.迭代器的实现

  \(a.\)迭代器要素

  首先，我们考虑编译器需要知道哪些可迭代对象的信息。首先，iterator()被调用了，于是我们需要知道：

• 该接口具有iterator()方法。

  其次，\(seer\)的.next()与.hasNext()方法被调用了，于是： * 迭代器接口是否有.next()与.hasNext()方法。

  \(b.\)迭代器的实现

1. 我们的\(List\)接口需要扩展迭代器接口，继承迭代器的抽象方法：

   public interface Iterable<T> {
       Iterator<T> iterator();
   }
   
   public interface List<T> extends Iterable<T> {
       ...
   }

2. 编译器检查迭代器接口是否具有.next()与.hasNext()方法：

   public interface Iterator<T> {
       boolean hasNext();
       T next();
   }

  特定的类需要实现自己的迭代器方法与行为。例如，我们想给\(ArrarMap\)添加一个迭代器。可以先如下实现迭代器接口所需方法：

private class ArraySetIterator implements Iterator<T> {
    private int wizPos;

    public ArraySetIterator() {
        wizPos = 0;
    }

    public boolean hasNext() {
        return wizPos < size;
    }

    public T next() {
        T returnItem = items[wizPos];
        wizPos += 1;
        return returnItem;
    }
}

  这样，我们就可以利用\(ArraySetIterator\)来实现对\(ArrayMap\)的迭代：

ArraySet<Integer> aset = new ArraySet<>();
aset.add(5);
aset.add(23);
aset.add(42);

Iterator<Integer> iter = aset.iterator();

while(iter.hasNext()) {
    System.out.println(iter.next());
}

  \(c.\)增强型\(for\)循环的实现

  为了实现增强型\(for\)循环，我们需要让\(ArrayMap\)类实现可迭代接口。可迭代接口的关键方法是iterator，我们只需要如下实现：

public Iterator<T> iterator() {
    return new ArraySetIterator();
}

  这样以后，我们就可以使用增强型\(for\)循环了：

ArraySet<Integer> aset = new ArraySet<>();
...
for (int i : aset) {
    System.out.println(i);
}

  \(d.\)关键概念辨析

• 可迭代对象(\(iterable\))：使得一个类可以被迭代的接口，需要方法iterator()。

• 迭代器(\(iterator\))：定义某些方法的接口，这些方法用于实现真正的迭代。

   You can think of an Iterator as a machine that you put onto an iterable that facilitates the iteration. Any iterable is the object on which the iterator is performing.

3.可迭代\(ArraySet\)的完整实现

import java.util.Iterator;

public class ArraySet<T> implements Iterable<T> {
    private T[] items;
    private int size; // the next item to be added will be at position size

    public ArraySet() {
        items = (T[]) new Object[100];
        size = 0;
    }

    /* Returns true if this map contains a mapping for the specified key.
     */
    public boolean contains(T x) {
        for (int i = 0; i < size; i += 1) {
            if (items[i].equals(x)) {
                return true;
            }
        }
        return false;
    }

    /* Associates the specified value with the specified key in this map.
       Throws an IllegalArgumentException if the key is null. */
    public void add(T x) {
        if (x == null) {
            throw new IllegalArgumentException("can't add null");
        }
        if (contains(x)) {
            return;
        }
        items[size] = x;
        size += 1;
    }

    /* Returns the number of key-value mappings in this map. */
    public int size() {
        return size;
    }

    /** returns an iterator (a.k.a. seer) into ME */
    public Iterator<T> iterator() {
        return new ArraySetIterator();
    }

    private class ArraySetIterator implements Iterator<T> {
        private int wizPos;

        public ArraySetIterator() {
            wizPos = 0;
        }

        public boolean hasNext() {
            return wizPos < size;
        }

        public T next() {
            T returnItem = items[wizPos];
            wizPos += 1;
            return returnItem;
        }
    }

    public static void main(String[] args) {
        ArraySet<Integer> aset = new ArraySet<>();
        aset.add(5);
        aset.add(23);
        aset.add(42);

        //iteration
        for (int i : aset) {
            System.out.println(i);
        }
    }

}