集合类随笔（迭代器）

集合类随笔

回顾集合类的整体框架结构，集合类简单的看主要有以下分类:

Collection
    |-List
    	|-ArrayList
    	|-LinkedList
    |-Set
    	|-HashSet
    	|-LinkedList

Java的集合类的常用API主要用来实现元素的存储和增删改查，对于集合类而言，为什么没有集合类元素的遍历方法呢?

从某种角度来讲，如果再在集合类里面加上集合元素的遍历操作，显得在功能上有几分冗余，也就是说，不满足类设计的单一职责原则

因此，为了满足单一职责原则，集合类中使用迭代器来实现集合的遍历，有关迭代器，就不得不说设计模式中的迭代器模式,我们首先来看ArrayList中关于这个模式的实现:

图上画的很明确，ArrayList中通过调用listIterator()方法或者iterator()方法作为方法入口,通过这个方法来生成一个Iterator对象，然后通过这个Iterator对象完成集合元素的迭代操作，ArrayList中有以下两个Iterator对象的内部类实现:

class Itr implements Iterator<E>;
class ListItr extends Itr implements ListIterator<E; //interface ListIterator<E> extends Iterator<E>

如果调用iterator()方法，返回Itr对象，如果调用listIterator()方法，返回ListItr对象

public Iterator<E> iterator() {
        return new Itr();
}
public ListIterator<E> listIterator() {
    return new ListItr(0);
}

Itr对象和ListItr对象的区别:

从ListItr的继承关系中就可以看出来，ListItr是在Itr的功能上做了一些扩展，可以搭配ArrayList的特性做一些特有的迭代操作，比如可以会用hasPrevious()方法向前迭代，还可以使用构造函数指定迭代器的指针的停留位置

public static void main(String[] args) {
    ArrayList<String> list = new ArrayList<>();
    list.add("1");
    list.add("1");
    //可以有顺序的 迭代器 默认在所有元素的前面
    ListIterator<String> iterator1 = list.listIterator();
    //将指针放在 下标为1的位置
    ListIterator<String> iterator2 = list.listIterator(2);

    while (iterator2.hasPrevious()){
        //这个函数执行的第一步会进行checkForComodification()判断
        String previous = iterator2.previous();
        if("1".equals(previous)){
            list.remove("1");
            //iterator2.add("2");
        }
    }
    System.out.println(list);
}

关于ArrayList里面大致的迭代器的实现思路就是如上,有关迭代器是如何实现的元素的迭代原理我们还不清楚，所以，继续往下探索！！！

迭代器的原理都大同小异，为便于分析，我们直接使用Itr类的实现进行分析：

上面已经说过，Itr对象继承自Iterator接口，接口用来定义规范，Iterator接口用来定义迭代器的规范，Iterator接口里面的方法主要如下:

public interface Iterator<E> {
    /**
    返回false表示迭代器中没有其他的对象
    反之，返回true表示有对象
     */
    boolean hasNext();

    /**
     * 返回下一个对象
     */
    E next();

    /**
  	  如果自己写的类没有覆盖这个方法，则会抛出异常
     */
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
    
    /**
     * Performs the given action for each remaining element until all elements
     * have been processed or the action throws an exception.  Actions are
     * performed in the order of iteration, if that order is specified.
     * Exceptions thrown by the action are relayed to the caller.
     */
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

从接口中可以看出来，迭代器接口中主要有两个核心方法，next()和hasNext()方法,一个得到遍历元素，另一个用来判断

接下来我们来看ArrayList中的Itr类关于Iterator接口的实现：

里面有hasNext()方法和next()方法的具体实现，hasNext()方法的实现原理主要就是判断当前迭代元素的指针位置是否和集合的size相同，如果不同，则表示当前迭代器中还有没有元素,next()方法主要用来移动指针，返回

private class Itr implements Iterator<E> {
        int cursor;       // 下一个元素返回的指针，默认是0
        int lastRet = -1; 
        int expectedModCount = modCount; //modeCount是当前类中当前时刻的集合操作次数,利用expectedModCount来记录这个次数，用来后面元素的检验

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

        @SuppressWarnings("unchecked")
    	//做两件事： 1，返回当前指针元素 2，指针后移一位
        public E next() {
            //这个方法就是计较当前集合的修改次数是否等于记录的expectedModCount，如果不等会抛出异常
            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];
        }

    	//同样是调用集合的方法来调用删除方法，同时更新expectedModCount
        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();
        }
    }