遍历器用于遍历Collection, Map没有提供public的遍历器,但是其内部定义了几个private遍历器自用。

简单地说,每个AbstratCollection的子类都有一个iterator()方法,这个方法将返回一个对应容器的遍历器。而AbstractList的子类自有一个listIterator()方法(ArrayList等具体类也提供iterator()方法,从源码中可以知道listIterator()实际上来自iterator()!在下面有详细解释)。


(*)通过研究源码可知,Set的Iterator实际上是从Map的内部Iterator获得的(HashSet从HashMap.KeySet私有内嵌类获得,TreeSet从TreeMap.KeySet私有内嵌类获得),之所以这样实现估计是因为Set和Map有同样的性质:不允许重复值。这里暂时不讨论。


listIterator()在AbstractList类中实现。AbstractList类中有四个内嵌类:Itr, ListItr, RandomAccessSubList和SubList。与Iterator有关的是Itr和ListItr这两个。

Itr和ListItr是两个private内嵌类,Itr的实现如下:


private class Itr implements Iterator {

//定义一个游标,标示List中元素Index

int cursor = 0;


//lastRet是最近被访问的元素的index,如果该元素被remove()了,设为-1

int lastRet = -1;


/**

modCount是该List的被修改次数(指结构上的变化,例如size改变),通常在我们一边遍历一边remove()时会发生。注意modCount是transient的,不能被序列化。

expectedModCount如果不等于modCount,就说明在遍历过程中List结构改变了

*/

int expectedModCount = modCount;


//hasNext()的实现

public boolean hasNext() {

return cursor != size();

}


//next()的实现

public Object next() {

try {
Object next = get(cursor);

checkForComodification();

lastRet = cursor ;

return next;

} catch(IndexOutOfBoundsException e) {

checkForComodification();

throw new NoSuchElementException();

}

}


//remove()的实现

public void remove() {

if (lastRet == -1)

throw new IllegalStateException();

checkForComodification();


try {

/**

AbstractList.remove()将会抛出UnsupportedOperationException,如果

如果某个子类允许remove(int)操作的话,必须override此方法。

*/

AbstractList.this.remove(lastRet);

if (lastRet < cursor)

cursor--;

lastRet = -1;

expectedModCount = modCount;

} catch(IndexOutOfBoundsException e) {

throw new ConcurrentModificationException();

}

}


//检查List是否被修改

final void checkForComodification() {

if (modCount != expectedModCount)

throw new ConcurrentModificationException();

}

}

AbstractList.iterator()其实只有一行:return new Itr(); 返回一个Itr实例。

可以看到,Itr类中调用了大量AbstractList中的方法,例如get(int)、remove(int)等,但是这些方法要么是抽象的,要么只有一句:throw new UnsupportedOperationException(); 这样AbstractList的子类如果实现了这些方法,那么它们继承的iterator()也就有用了。如果不允许实现get(int),remove(int),那么iterator()也将被禁止。如下图所示:


ArrayList要提供遍历器,只需要覆盖它继承自AbstractList的get(int)和remove(int)方法就可以了。也就是说,遍历器的普遍行为都在AbstractList中定义了,其他具体类只需要根据自己的特点覆盖几个方法就能够使用iterator()。

ListItr内嵌类继承了Itr类,源码如下:


private class ListItr extends Itr implements ListIterator {

ListItr(int index) {

cursor = index;

}


public boolean hasPrevious() {

return cursor != 0;

}


public Object previous() {

try {

int i = cursor - 1;

Object previous = get(i);

checkForComodification();

lastRet = cursor = i;

return previous;

} catch(IndexOutOfBoundsException e) {

checkForComodification();

throw new NoSuchElementException();

}

}


public int nextIndex() {

return cursor;

}


public int previousIndex() {

return cursor-1;

}

public void set(Object o) {

if (lastRet == -1)

throw new IllegalStateException();

checkForComodification(); //检查是否有修改


try {

AbstractList.this.set(lastRet, o);

expectedModCount = modCount;

} catch(IndexOutOfBoundsException e) {

throw new ConcurrentModificationException();

}

}


public void add(Object o) {

checkForComodification();


try {

AbstractList.this.add(cursor , o);

lastRet = -1;

expectedModCount = modCount;

} catch(IndexOutOfBoundsException e) {

throw new ConcurrentModificationException();

}

}

}


AbstractList.listIterator()有两个:


(1)public ListIterator listIterator() {

return listIterator(0);

}


(2)public ListIterator listIterator(final int index) {

if (index<0 || index>size())

throw new IndexOutOfBoundsException("Index: " index);


return new ListItr(index);

}

 


Joshua Bloch设计的Collection架构之美,只有在源码中慢慢领会……

 

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐