迭代器

第一节 概述

1.1 迭代器是什么？

迭代器（iterator），是确使用户可在容器对象（container，例如链表或数组）上遍访的对象，设计人员使用此接口无需关心容器对象的内存分配的实现细节。

1.2 Java迭代器

Java JDK 1.2 版开始支持迭代器。每一个迭代器提供 next()以及 hasNext()方法，同时也支持 remove() 。

Iterator iter = list.iterator();
//Iterator<MyType> iter = list.iterator();    in J2SE 5.0
while (iter.hasNext())
    System.out.println(iter.next());

迭代器主要用来帮助集合遍历，使集合类型的遍历行为与被遍历的集合对象分离。

Java语法糖中的 foreach 就是由迭代器来实现的。

1.3 快速失败与安全失败

快速失败（fail-fast）是指迭代器遍历集合对象时发现内容被同时修改，且修改导致了计数器与期待值不同，导致抛出异常 ConcurrentModificationException（迭代器内部有计数器ModCount，每次移动指针前会检查当前值是否是expected，若修改不会使modCount不匹配就不会抛出异常）。

安全失败（fail-safe）则是指相应集合并不直接在内部访问，而是先拷贝副本，在副本上进行遍历，所以遍历过程中的修改不会影响到读取。

Java迭代器采用的是快速失败的模式，在一个线程工作时不允许其他线程修改相关内容。

---

第二节 源码

本部分代码来自于JDK 1.8。

2.1 Iterable

Iterable接口定义了 iterator() 返回一个迭代器。

public interface Iterable<T> {

    Iterator<T> iterator();

    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }

    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

接口Iterable表示对象是否可迭代，集合顶层接口Collection继承了此接口，所以所有集合对象都是可迭代的。

public interface Collection<E> extends Iterable<E> {
    ...
}

2.2 Iterator

迭代器接口Iterator源码如下。

public interface Iterator<E> {
	// 是否还有元素
    boolean hasNext();
	// 返回下一个元素
    E next();
	// 删除最后一个元素，默认实现抛出异常
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }

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

需要注意 remove() 使用时有一些陷阱，如下所示。

List list = ...;  
for(Iterator iter = list.iterator();iter.hasNext();) {  
    Object obj = iter.next();  
    ...  
    if(XXX) {  
        list.remove(obj);  
    }  
}  

在迭代器遍历集合时，调用 remove() 后，继续执行 next() 时，程序会抛出异常 UnsupportedOperationException 或 ConcurrentModificationException 。

前者是因为接口或抽象类默认实现即抛出此异常。后者则因为删除方法修改了modCount计数值，导致与期待值不等所以抛出此异常。

2.3 Itr

AbstractList中通过子类Itr实现了迭代器接口Iterator。

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
    // 计数器记录操作次数
    protected transient int modCount = 0;
        
    // 抽象类默认仍是抛出异常
    public E remove(int index) {
        throw new UnsupportedOperationException();
    }
    
    private class Itr implements Iterator<E> {
        /**
         * Index of element to be returned by subsequent call to next.
         */
        int cursor = 0;

        /**
         * Index of element returned by most recent call to next or
         * previous.  Reset to -1 if this element is deleted by a call
         * to remove.
         */
        int lastRet = -1;

        /**
         * The modCount value that the iterator believes that the backing
         * List should have.  If this expectation is violated, the iterator
         * has detected concurrent modification.
         */
        int expectedModCount = modCount;

        public boolean hasNext() {
            return cursor != size();
        }

        public E next() {
        	// 检查modCount是否修改
            checkForComodification();
            try {
                int i = cursor;
                E next = get(i);
                lastRet = i;
                cursor = i + 1;
                return next;
            } catch (IndexOutOfBoundsException e) {
                checkForComodification();
                throw new NoSuchElementException();
            }
        }

        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();
            }
        }

        // 检查modCount是否修改
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }
}

ArrayList中也通过子类Itr实现了迭代器接口Iterator。

在ArrayList中如 remove() 或 sort() 等方法会 modCount++ 所以并发修改会导致计数器值和期待值不符，导致抛出异常。

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

	/**
     * An optimized version of AbstractList.Itr
     */
    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        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
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }
    
    public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }
    
    
    public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }
    
    @Override
    @SuppressWarnings("unchecked")
    public void sort(Comparator<? super E> c) {
        final int expectedModCount = modCount;
        Arrays.sort((E[]) elementData, 0, size, c);
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }
    
}

---

参考：

🔗 《维基百科》