Iterator Design Partern

作用

遍历容器实现复杂，并且方式有多种，例如遍历二叉树时，有前序、后序、中序遍历。将遍历容器从容器中独立出来，让两者的职责更单一。

容器使用的是迭代器接口，基于接口而非实现编程，替换迭代器更加容易。

示例

public class MyArrayList<E> implements List<E> {
    private Object[] elements;
    private int size;

    @Override
    public Iterator<E> iterator() {
        return new MyIterator();
    }

    public class MyIterator implements Iterator<E> {

        private int cursor;

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

        @Override
        public E next() {
            if (hasNext()) {
                return (E) elements[++cursor];
            }
            throw new NoSuchElementException();
        }
    }
    ...
}

为什么ArrayList在遍历时不能修改容器

容器改变后，迭代器里的游标指向就会变化，可能导致有元素遍历不到，或者重复遍历。所以在使用迭代器遍历时，会检查一个修改计数的遍历，如果容器被修改了就抛出异常。

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

ArrayList迭代器删除操作的坑

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

• 只能删除上一个元素
• 一个next() 函数之后，只能跟着最多一个 remove() 操作，多次调用 remove() 操作会报错

如何实现支持“快照”的迭代器

方案一

创建迭代器时，将容器元素浅拷贝到迭代器内部维护的容器里，这样每个迭代器维护者属于自己的容器快照。

方案二

利用时间戳，记录添加、删除元素的时间戳，创建迭代器时，记录创建迭代器的时间戳到迭代器里。遍历时只遍历满足以下条件的元素

• 添加元素时间戳<创建迭代器的时间戳<删除元素时间戳

产生的问题

容器元素采用逻辑删除，造成内存空间浪费。

可以利用弱引用解决：删除元素时，将容器与元素设置为弱引用，当没有迭代器强引用元素时，元素将被回收。