深入理解iterator

  今天我们就来说说在collection集合体系中的一个很有用但初学者看起来很鸡肋的功能：迭代器。由于分析的很细致，所以文章比较冗长，共分成三部分：为什么有迭代器？如何使用迭代器？由源码分析迭代器使用的限制。
  首先第一部分，为什么有迭代器？对于我们这种经常只使用ArrayList、LinkedList的人来说，感觉迭代器就是一个很鸡肋的功能，我们完全可以先获得集合的大小，再通过循环遍历集合。这样就有一些问题，比如Set集合该如何处理？Set集合是没有get(int index)方法的，通过索引值遍历它肯定是做不到的。又比如是对于不同的集合，可能会有不同的取值方法。比如对于ArrayList集合的get(int index)方法，Stack的peek()方法。这样我们修改了集合的类型后与其相关的遍历全部都可能会修改。还有就是增强for循环底层使用的是迭代器，没有迭代器也就没有增强for循环。所以迭代器有存在的必要性。
  第二部分如何使用迭代器？首先是获取迭代器：集合对象.iterator()。面相对象的思想嘛，使用方法也就是：对象.方法()。同时它就是一个游标，初始位置在当前元素之前。且除两端外游标位于最近返回元素与下一个应返回的元素之间。

方法	解释
boolean hasNext()	游标之后是否有元素
E next()	返回游标之后紧邻的元素，返回之后游标向后移动一个位置
void remove()	在集合中移除最近一次返回的元素

  以上是Iterator接口的一些方法，还有List接口所特有的实现类listIterator，它的一些方法如下：

方法	解释
boolean hasNext()	游标之后是否有元素
boolean hasPrevious()	游标之前是否有元素
E next()	返回游标之后紧邻的元素，返回之后游标向后移动一个位置
E previous()	返回游标之前紧邻的元素，返回之后游标向前移动一个位置
void remove()	在集合中移除最近一次返回的元素。且在最近一次next()或previous()被调用与remove()被调用之间不能进行remove()和add()操作
void add(E e)	将e插入到集合的实际序列中游标之前距游标最近的元素与游标之间
void set(E e)	用指定元素在集合中代替最近一次返回的元素

  第三部分，由源码分析Iterator。如果仅仅了解使用方法的话，迭代器的使用其实很简单：集合对象.iterator()即可。但既然是深入解析iterator，我们肯定是从源码说起。首先，Collection接口继承了Iterable接口，Iterable接口中有一个方法：Iterator<T> iterator()，所以很明显，我们使用的iterator()方法是源自于这。那么他的实现类又是如何实现的呢？
  答案是内部类！根据小码农分析过的几个实现类：ArrayList、LinkedList、Vector、HashSet、TreeSet，都是使用内部类来实现的。在分析之前，先说明两个问题，第一个是Set集合其实是Map集合的key值，所以Set集合中没有直接通过内部类实现Iterator，而是在Map实现类中实现的Iterator。第二个是Iterator既然屏蔽了单列集合之间的差异，那么所有被实现的Iterator其实具有相同的功能，由于ArrayList是逻辑结构较简单的一个实现类，所以接下来使用此集合来进行分析。
ArrayList中有一个属性：private class Itr implements Iterator<E>，一看是一个private的属性，就知道它只能在本类中使用了。同时他还有三个属性：cursor、lastRet、expectedModCount。对接下的分析来说，只需要理解cursor和lastRet就行。
  对于是否有下一个元素，取下一个元素这些代码都不难。主要想分析的就是remove()的使用限制和为什么在获取迭代器之后不允许对集合进行直接的有关结构的修改。remove()的源码如下图。

remove()

  源码做了一些安全性检验，但真正发挥移除功能的一句是ArrayList.this.remove()这句。从代码中可以看到，他移除的是最后一次被访问的元素。并且在移除之后lastRet = -1，从这就能看出来为什么不能在一次next()或previous()被调用与remove()被调用之间使用remove操作，因为remove()之后lastRet被置为-1，很明显这个位置没有元素，自然不能被移除。

add()

  我们再看看ListIterator里的add()，它同样也有一句lastRet = -1。自然也不能在一次next()或previous()被调用与remove()被调用之间使用add操作。而每次使用next()或previous()后lastRet会被置为当前游标所在的前一个位置，自然又能使用remove()了。那为什么要给他置-1呢？

ArrayList.this.rmove()

  看ArrayList.this.remove()这个remove()方法。在这个方法中真正起到移除作用的是System.arraycopy(…)这句。它是一个数组拷贝的方法，而我们都知道，对于一个数组来说，想删除它的某个元素是从当前元素的索引+1的位置，向后依次向前覆盖。此方法正是有这个功能。参数依次是：源数组、源数组中的起始位置、目标数组、目标数据中的起始位置、要复制的数组元素的数量。再看传入的参数：index就是lastRet。从最后一次被返回的元素之后紧邻的位置向前覆盖，也就是删除了lastRet位置的元素。在覆盖完了之后，size减一，删除最后一位，真是完美的操作。而它没有把lastRet--是由于它不知道此时是向前遍历还是向后遍历。而如果是向前遍历需要lastRet是不需要改变的。所以它不允许进行两次连续的remove()。
  看到这里有人会注意到add(E e)这个方法，为什么它可以进行连续的插入呢？因为它插入的位置和遍历顺序无关，它插入在实际序列顺序中在游标之前距游标最近的位置与游标之间。那么插入之后为什么把lastRet也置为-1呢，这还是由于向前遍历和向后遍历结果不同。比如原集合：[1, 2, 3, 4]，向后遍历遇到2时插入11, 12为：[1, 11, 12, 2, 3, 4]；向前遍历遇到2时插入11, 12为：[1, 2, 11, 12, 3, 4]。在不知道遍历顺序的情况下是计算不出2所在索引的，即无法进行System.copyarray()。
  那么为什么获得迭代器之后不能直接对进行remove呢？这时候就得用到我们刚才看到的三个属性中还剩下的这个expectedModCount，它就是确保此条的原因。ArrayList集合中的modCount属性是保存此集合的结构被改变的次数，通常指大小被改变的次数。集合.remove()、.add()方法改变它的容量时会改变modCount的值，当它与expectedModCount不同会报ConcurrentModificationException。
  那么问题又来了，为什么要这样设计呢？这是设计者故意将错误提前，防止在并发时出现不确定情况（原话：This provides fail-fast behavior, rather than non-deterministic behavior in the face of concurrent modification during iteration）。比如在并发时，一个线程对集合进行增加，另一个进行移除，这时由于线程执行的先后顺序是有不确定关系的，所以线程操作结束之后再使用迭代器遍历结果也会不确定。而用上modCount这种方式，第一个线程对集合进行操作后时再有线程对集合操作就会抛出异常，也就是错误提前。当然这种方式并不能保证线程安全，它只是一种预警机制。