Java 中的迭代器 Iterator

集合上的迭代器。

在 Java 集合框架中，迭代器 Iterator 取代了枚举 Enumeration 的位置。两者在两个方面存在不同：

• 迭代器允许调用者在迭代过程中，从底层集合中移除元素
• 方法名称得到了改进

此接口是Java集合框架的成员之一。

一、接口源码

package java.util;

import java.util.function.Consumer;

/**
 * @since 1.2
 */
public interface Iterator<E> {

    boolean hasNext();

    E next();

    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    /**
     * @since 1.8
     */
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

• hasNext() 方法，用来判断是否还有需要迭代的元素，如果有则返回 true。
• next() 方法，返回迭代中的下一个元素，如果没有，则抛出 NoSuchElementException 异常
• remove() 方法，从集合中删除迭代器返回的最后一个元素。
  • 每次调用 next() 方法时只能调用 remove() 方法一次，如果在迭代过程中以调用 remove() 方法之外的任何其他方式修改了集合，则迭代器接下来的行为将是不可控的，除非重写了类指定并发修改策略。
  • 在调用了 forEachRemaining() 方法后调用此方法，则迭代器的行为将不可控。
  • 如果迭代器不支持删除操作，将抛出 UnsupportedOperationException 异常
  • 如果 next() 方法尚未被调用，或者在最后一次调用 next() 方法之后已经调用了 remove() 方法，将抛出 IllegalStateException 异常
• forEachRemaining()方法，对于剩余的每个元素，执行给定的操作，直到所有元素都被处理完毕或操作抛出一个异常。
  • 如果制定了迭代顺序，则按照改顺序执行操作。抛出的异常会传递给调用者。
  • 如果操作以任何方式修改了集合（即使是通过调用迭代器的 remove() 方法或迭代器子类型的其他修改方法），除非重写了类并指定了并发修改策略，否则迭代器的行为将是不可控的。
  • 如果操作抛出一个异常，则迭代器后续的行为也是不确定的。

1、forEachRemaining() 方法

forEachRemaining 在 Java 8 中被引入。此允许你传递一个 Consumer 函数式接口的实现，该函数式接口会在当前迭代器位置的剩余所有元素上被调用。这意味着，一旦调用 forEachRemaining 方法，它会从当前迭代器指向的元素开始（而不是从头开始），直到迭代器末尾，对每个元素执行提供的操作。

使用场景

• 处理迭代器中的剩余元素。当使用迭代器遍历了一部分元素，终止遍历之后，还想要对剩余元素执行某个其他操作时，此方法将会很有用。避免了手动遍历剩余元素的繁琐，让代码更为简洁。
• 性能优化。需要处理大量数据时，可以一定程度上提高性能，它减少了方法调用次数。
• 并行处理。
• 链式调用。
• 简化代码。在只需要对迭代器剩余部分执行单一操作时，forEachRemaining 可以显著简化代码。你不需要编写额外的循环逻辑来检查迭代器是否有更多元素，也不需要维护一个循环计数器或索引。

二、实现

1、AbstractList 中的实现

在 AbstractList 中定义了实现 Iterator 接口的私有内部类 Itr，iterator() 方法会返回一个 Itr 对象。

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {

    protected transient int modCount = 0;
    
    public Iterator<E> iterator() {  
        return new Itr();  
    }

    private class Itr implements Iterator<E> {
    
        int cursor = 0;
        
        int lastRet = -1;
        
        int expectedModCount = modCount;
        
        public boolean hasNext() {  
            return cursor != size();  
        }
        
        public E next() {  
            checkForComodification();  
            try {  
                int i = cursor;  
                E next = get(i);  
                lastRet = i;  
                cursor = i + 1;  
                return next;  
            } catch (IndexOutOfBoundsException e) {  
                checkForComodification();  
                throw new NoSuchElementException(e);  
            }  
        }  
          
        public void remove() {  
            if (lastRet < 0) {
                throw new IllegalStateException();  
            }
            checkForComodification();  
          
            try {  
                AbstractList.this.remove(lastRet);  
                if (lastRet < cursor)  
                    cursor--;  
                lastRet = -1;  
                expectedModCount = modCount;  
            } catch (IndexOutOfBoundsException e) {  
                throw new ConcurrentModificationException();  
            }  
        }  
          
        final void checkForComodification() {  
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();  
            }
        }
    }
}

1.1 modCount 属性

上面 AbstractList 类中定义了 modCount 属性，该属性用来表示这个列表结构修改的次数。结构修改是指那些改变列表大小的操作，或者以某种方式干扰列表从而使正在进行的迭代产生不正确结果的行为。

modCount 字段被迭代器 Iterator 和列表迭代器 ListIterator 的实现所使用。如果这个字段的值意外地改变，迭代器或列表迭代器将在下一次调用 next、remove、previous、set 或 add 操作时抛出 ConcurrentModificationException 异常。这提供了快速失败（fail-fast）的行为，而不是在迭代过程中面对并发修改时出现不确定的行为。

子类使用这个字段是可选的。如果一个子类希望提供快速失败的迭代器和列表迭代器，那么它只需要在其 add(int, E) 和 remove(int) 方法以及它重写的任何导致列表结构修改的其他方法中增加这个字段的值。对 add(int, E) 或 remove(int) 的单次调用必须将这个字段的值增加不超过一，否则迭代器和列表迭代器将抛出 ConcurrentModificationException 异常。如果一个实现不希望提供快速失败的迭代器，则可以忽略这个字段。

ArrayList 中使用了这个字段。

1.2 私有内部类 Itr 迭代器实现

cursor 属性用来定义接下来调用 next() 方法返回元素的索引。

lastRet 属性用来记录最近一次调用 next() 或 previous() 返回的元素的索引。如果此元素被调用 remove() 删除了，则将此属性重新赋值为 -1

expectedModCount 属性定义了迭代器创建时应该具有的 modCount 值，如果后续期望值

1.2.1 hasNext() 方法

当下一个元素的索引不等于列表的容量的时候，表示迭代器中还有元素没有遍历，返回 true

1.2.2 checkForComodification() 方法

该方法中检测列表对象中的 modCount 和 迭代器中的 expectedModCount 值是否相等。

如果不相等，则代表在迭代器遍历过程中，其他操作（迭代器方法之外的方法）修改了列表的结构，抛出异常 ConcurrentModificationException

1.2.3 next() 方法

在 next() 方法中，会首先调用 checkForComodification() 方法用来检测列表对象是否执行过其他修改结构的操作，如果有则会抛出异常，直接结束 next() 方法。

int i = cursor;  
E next = get(i);  
lastRet = i;  
cursor = i + 1;  
return next;

接下来上述代码段，则是通过元素下标获取元素，以及 cursor 和 lastRet 重新赋值的过程。

上述代码使用 try-catch 包裹，捕获 IndexOutOfBoundsException 异常，该异常是根据索引获取元素方法 get() 抛出的。在迭代过程中可能会因为并发操作导致列表结构被修改，迭代器中定义的用来决定遍历位置的 cursor 和 lastRet 属性与列表结构不匹配，导致获取元素失败。在捕获到 IndexOutOfBoundsException 异常之后，会再次确认 modCount 和 expectedModCount 属性，来判断是否真的是因为并发修改产生的异常，如果是的话，直接抛出 ConcurrentModificationException 异常。

1.2.4 remove() 方法

该方法开头先判断 lastRet 属性的值，来判断迭代器是否遍历过元素。也就是说，在执行 remove() 方法之前，必须要调用过 next() 方法才行。

之后，同样会调用 checkForComodification() 方法用来检测列表对象是否执行过其他修改结构的操作。

在调用列表的 remove(lastRet) 方法之后，会更新 lastRet 和 cursor 属性的值。

• 将 lastRet 属性赋值为 -1，表示刚遍历的这个元素已经被删除了，如果连续调用两次迭代器的 remove() 方法，则第二次会因为 remove() 方法开头对 lastRet 的检测而抛出异常。
• 将 cursor 属性的值减去1，重新定位下一个元素的索引位置。

之后，重新将列表对象的 modCount 的值赋值给迭代器的 expectedModCount。因为 AbstractList 的实现类中，可能有的类在删除了元素之后会修改 modCount 属性的值，所以这里需要同步修改 expectedModCount 的值。

迭代器的 remove() 的方法中同样需要将修改列表结构的操作使用 try-catch 包裹起来，用来捕获并发导致的列表下标和列表大小不匹配的问题。但这里没有在 catch 中判断 modCount 和 expectedModCount 属性的值，直接抛出并发修改异常。应该是因为在删除时出现列表下标的问题则可以直接确定是因为并发问题，而在调用 next() 方法时的 IndexOutOfBoundsException 异常则不确定是否是并发修改问题。

try {  
} catch (IndexOutOfBoundsException e) {  
    throw new ConcurrentModificationException();  
}

疑问

至于方法中有一个 if 语句用来判断 lastRet 和 cursor 的值的大小，当符合条件之后才修改 cursor 的值，这里还有点疑问，不知为何？

if (lastRet < cursor) {
    cursor--;
}

但是 AbstractList 的实现类 ArrayList 的迭代器中就没有这个判断：

try {  
    ArrayList.this.remove(lastRet);  
    cursor = lastRet;  
    lastRet = -1;  
    expectedModCount = modCount;  
} catch (IndexOutOfBoundsException ex) {  
    throw new ConcurrentModificationException();  
}

感觉可能是为了约束不同的实现类中的操作而做的。暂时还不知道其用意。

2、ArrayList 中的实现

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

    public Iterator<E> iterator() {  
        return new Itr();  
    }

    private class Itr implements Iterator<E> {
        int cursor;
        int lastRet = -1;
        int expectedModCount = modCount;
    
        Itr() {
        }
    
        public boolean hasNext() {
            return cursor != size;
        }
    
        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }
    
        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();
    
            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
    
        @Override
        public void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i < size) {
                final Object[] es = elementData;
                if (i >= es.length)
                    throw new ConcurrentModificationException();
                for (; i < size && modCount == expectedModCount; i++)
                    action.accept(elementAt(es, i));
                // update once at end to reduce heap write traffic
                cursor = i;
                lastRet = i - 1;
                checkForComodification();
            }
        }
    
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }    
}

在 ArrayList 中定义了实现 Iterator 接口的私有内部类 Itr，iterator() 方法会返回一个 Itr 对象。值得注意的是，ArrayList 中的迭代器私有内部类实现注释上面写的是：是对 AbstractList 迭代器的优化。

An optimized version of AbstractList.Itr

2.1 next() 方法

因为 ArrayList 继承自 AbstractList 方法，是对列表的完全实现，其中没有调用列表对象的 get(int index) 方法而是直接使用 ArrayList 的底层数组获取的元素。

进入方法时，首先会调用了 checkForComodification() 方法判断是否存在并发异常，并且在获取元素时判断索引位置和底层数组长度来决定是否要抛出并发异常。

2.2 forEachRemaining() 方法

覆盖了 Iterator 接口的 forEachRemaining() 方法，接口中该方法的默认实现为调用迭代器的 next() 方法，这里将 next() 方法的内容融合进 forEachRemaining() 方法。

在方法结束时，给 cursor 和 lastRet 变量重新赋值，此时 cursor 的值为 “数组索引最大值 + 1”，而 lastRet 的值为“数组索引最大值”。

三、关于 Enumeration

发音：/ɪˌnju:mə'reɪʃn/

Enumeration 是 Java 1.0 时期的功能，被用来遍历集合（比如 Vector、HashTable 等）。

是一个传统的迭代器，提供了 hasMoreElements() 方法用来判断集合中是否还存在需要遍历的元素，以及 nextElement() 来获取下一个元素

/**
 * @since   1.0
 */
public interface Enumeration<E> {
    
    boolean hasMoreElements();

    E nextElement();

}

Vector 中的相关实现：

public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

    protected Object[] elementData;

    public Enumeration<E> elements() {
        return new Enumeration<E>() {
            int count = 0;

            public boolean hasMoreElements() {
                return count < elementCount;
            }

            public E nextElement() {
                synchronized (Vector.this) {
                    if (count < elementCount) {
                        return elementData(count++);
                    }
                }
                throw new NoSuchElementException("Vector Enumeration");
            }
        };
    }
    
    E elementData(int index) {
        return (E) elementData[index];
    }
}

从上面的源码中可知，如果在使用 Vector.elements() 方法返回的枚举遍历过程中删除集合中的元素（或添加元素等对集合结构进行修改），则枚举的结果是不确定的。因为获取元素是通过元素在数组中的位置来获取的，而修改集合结构（添加或删除元素）时，元素在数组中的位置将会发生改变。

从 Java 1.2 版本开始，引入了 Iterator 接口，提供了比 Enumeration 更多的功能（提供 remove() 方法用于在迭代过程中删除元素），并且成为遍历集合的首选方式。但是 Enumeration 仍然在 Java 的一些遗留代码和特定 API 中被使用。

不推荐再使用了，另外常用的集合框架也没有相关实现了。

从 Java 9 版本开始，Enumeration 提供了一个方法 asIterator()，用于转换为 Iterator：

public interface Enumeration<E> {

    /**
     * @since 9
     */
    default Iterator<E> asIterator() {  
        return new Iterator<>() {  
            @Override 
            public boolean hasNext() {  
                return hasMoreElements();  
            }  
            @Override
            public E next() {  
                return nextElement();  
            }  
        };  
    }
}

相关链接

OB links

OB tags

#Java