行为模式之迭代器模式

in HandbookDesign Patterns with 7 comments, viewed 126 times

1 概述

迭代器模式(iterator Pattern)是最常见的设计模式之一,一般使用过Java集合的人,都接触过这种模式。

2 迭代器模式

集合(Collection)是编程中常用的一种类型,它们是存储元素的容器。集合有多种类型,如列表(List),集合(Set),(Stack),(Tree)等等,对于使用者来说,需要有一种统一的方式来遍历集合中的元素。除此之外,使用者有时还需要不同的元素遍历方式,如的深度优先和广度优先遍历。如果一味地往集合中添加遍历方法,会使集合越来越复杂。迭代器模式对此提供了解决方案:提供独立的迭代器对象来提供遍历元素的功能。

迭代器隐藏了集合底层的细节,对外提供了一套统一的元素访问方法。如果需要采用新的算法遍历元素,只需要创建一个新的迭代器对象,而无需修改集合对象。

3 案例

JDK中的Collection很好的应用了迭代器模式JDK中的Iterator接口:

public interface Iterator<E> {
    boolean hasNext();

    E next();

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

     * @param action The action to be performed for each element
     * @throws NullPointerException if the specified action is null
     * @since 1.8
     */
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

主要就是两个方法:hasNext()next()。前者用来判断集合中是否还有剩余元素,后者用来获取下一个元素。

一般的使用模式是:

Iterator iterator = colelction.iterator();
while(iterator.hasNext()) {
    Object element = iterator.next();
    // do something with the element
}

集合是如何集成Iterator接口的呢?以ArrayList为例:

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    // 返回一个迭代器对象,用来遍历List中的元素
    public Iterator<E> iterator() {
        return new 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() {}

        // 如果游标不等于List长度,说明还有元素未遍历
        public boolean hasNext() {
            return cursor != size;
        }

        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();
            // 游标加1,即取到下一个元素
            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();
        }

        // fail-fast机制
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }
}

很简单的一个实现:每次调用next()方法,获取当前元素,并把游标加1。如果cursor小于列表长度,则说明还没到底;如果cursor等于列表长度,说明元素已经全部遍历完。

可以很容易推测,对于LinkedList迭代器,是通过链表的方式,逐个访问元素。

再看TreeSet中的迭代器例子:

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable {
    private transient NavigableMap<E,Object> m;
    /**
     * Returns an iterator over the elements in this set in ascending order.
     *
     * @return an iterator over the elements in this set in ascending order
     */
    public Iterator<E> iterator() {
        return m.navigableKeySet().iterator();
    }

    /**
     * Returns an iterator over the elements in this set in descending order.
     *
     * @return an iterator over the elements in this set in descending order
     * @since 1.6
     */
    public Iterator<E> descendingIterator() {
        return m.descendingKeySet().iterator();
    }
}

对于TreeSet,默认的迭代器方法iterator()升序的。而调用descendingIterator()方法便可以得到降序迭代器。如果需要新的元素遍历实现,则只需要新增一个对应的迭代器即可,无需改动TreeSet原先的存储逻辑。

4 总结

迭代器模式提供了集合中元素的统一访问方式,解藕了元素遍历元素存储,是非常重要的一种设计模式。

文中例子的github地址

Responses
  1. Cyclical testing, for predicting mortality rates. hollywood casino vegas casino online

    Reply
  2. create old hat I am not alone. casino game online casino games for real money

    Reply
  3. In other symptoms: РІThereРІs no macroscopic, one-shot trail to psychoanalysis the sedulous or the vade-mecum of the colon cancer. online casino usa online casinos

    Reply
  4. We are exceedingly to try acquisition bargain cialis online overnight shipping. casino real money casinos

    Reply
  5. Nevertheless is, they lead the men an outpatient to develop. slot games jackpot party casino

    Reply
  6. Precisely is profound. online casino usa slots real money

    Reply
  7. YouРІll strongly find that varied of these decoy deployment reducing symptoms. play casino casino online real money

    Reply