Javaコレクション:反復器(Iterator,Iterable)
19344 ワード
Iteratorインタフェース
要素にアクセスする前にhasNextを使用して要素が存在するかどうかを判断する必要があります.またnext操作で取得した場合は、hasNext検出を行わずにnext操作を直接使用し、末尾に達するとNoSuchElement異常が放出されます.
Iteratorのremove操作
JDKコードを見るのは久しぶりで、今日Java Coreを見て反復器の中の注意点を見て、意外にも少しも思い出せませんでした.まず、次のコードを参照してください.
では、ここでiter.remove()が削除した要素はどの要素で、削除したのはリストの最初の要素で、一般的には反復器が前回next()で返した要素です.次のコードもあります.
実際に実行すると、java.lang.IllegalStateException異常、すなわち、removeのたびに対応するnextがあるはずですが、実は2つのペアで、removeのはnextが返す要素です.
AbstractListのソースコードから、Iteratorの基本的な実装がわかります.
lastRetとcursorの2つの変数が表示され、前者はnext()操作で返される要素を表すインデックスであり、後者は次のnext()呼び出しが返されるべき要素のインデックス値であることを示す.remove操作のたびにlastRetが空になり、同時にcursor--は、lastRetに対応する要素がcursorの前にあるため、このときremoveされると、cursorの値は必ず1つ減少します.実はここの反復器実装は基本的にAbstractListのサブクラスによってカバーされており,例えばLinkedList,ArrayListである.前者はランダムアクセスをサポートしていないので、インデックス値を取得要素として使用することはできません.そうしないと、反復器の効率が低下します.
ListIterator(extends Iterator)
Listインタフェースは、Iterableインタフェースを継承するほか、リスト専用の反復器(すなわちListIterator)を取得するためのいくつかの追加の方法(listIterator)があります.LinkedListの反復器実装を参照してください.
remove操作の考え方はほぼ一致するが,lastRetをチェーンテーブルノードlastReturnedに変換し,removeのたびにnullを置く.取得要素は親バージョンのようにget(i)で直接取得されるわけではありません.反復器は、隣接する2つのノードポインタlastReturnedとnextを保存します.これにより、要素がremove(lastReturned=null)され、nextが再び呼び出されると、nextポインタ値が保存されるため、チェーンテーブル内を移動することができる.
IteratorインタフェースListIteratorインタフェースよりもaddメソッドが多く、反復器が指すnext要素の前の位置、すなわち次の要素の前の位置に要素を入れます.
Iterableインタフェース
Java Coreで説明したように、Iterableインタフェースを実装すればforeachサイクルで使用できます.のように
public interface Iterator<E> {
boolean hasNext();
E next();
void remove();
}要素にアクセスする前にhasNextを使用して要素が存在するかどうかを判断する必要があります.またnext操作で取得した場合は、hasNext検出を行わずにnext操作を直接使用し、末尾に達するとNoSuchElement異常が放出されます.
Iteratorのremove操作
JDKコードを見るのは久しぶりで、今日Java Coreを見て反復器の中の注意点を見て、意外にも少しも思い出せませんでした.まず、次のコードを参照してください.
Iterator<String> iter = list.iterator();
String s = iter.next();
iter.remove();では、ここでiter.remove()が削除した要素はどの要素で、削除したのはリストの最初の要素で、一般的には反復器が前回next()で返した要素です.次のコードもあります.
Iterator<String> iter = list.iterator();
String s = iter.next();
iter.remove();
iter.remove();実際に実行すると、java.lang.IllegalStateException異常、すなわち、removeのたびに対応するnextがあるはずですが、実は2つのペアで、removeのはnextが返す要素です.
AbstractListのソースコードから、Iteratorの基本的な実装がわかります.
1 private class Itr implements Iterator<E> {
2 /**
3 * Index of element to be returned by subsequent call to next.
4 */
5 int cursor = 0;
6
7 /**
8 * Index of element returned by most recent call to next or
9 * previous. Reset to -1 if this element is deleted by a call
10 * to remove.
11 */
12 int lastRet = -1;
13
14 /**
15 * The modCount value that the iterator believes that the backing
16 * List should have. If this expectation is violated, the iterator
17 * has detected concurrent modification.
18 */
19 int expectedModCount = modCount;
20
21 public boolean hasNext() {
22 return cursor != size();
23 }
24
25 public E next() {
26 checkForComodification();
27 try {
28 int i = cursor;
29 E next = get(i);
30 lastRet = i;
31 cursor = i + 1;
32 return next;
33 } catch (IndexOutOfBoundsException e) {
34 checkForComodification();
35 throw new NoSuchElementException();
36 }
37 }
38
39 public void remove() {
40 if (lastRet < 0)
41 throw new IllegalStateException();
42 checkForComodification();
43
44 try {
45 AbstractList.this.remove(lastRet);
46 if (lastRet < cursor)
47 cursor--;
48 lastRet = -1;
49 expectedModCount = modCount;
50 } catch (IndexOutOfBoundsException e) {
51 throw new ConcurrentModificationException();
52 }
53 }
54
55 final void checkForComodification() {
56 if (modCount != expectedModCount)
57 throw new ConcurrentModificationException();
58 }
59 }lastRetとcursorの2つの変数が表示され、前者はnext()操作で返される要素を表すインデックスであり、後者は次のnext()呼び出しが返されるべき要素のインデックス値であることを示す.remove操作のたびにlastRetが空になり、同時にcursor--は、lastRetに対応する要素がcursorの前にあるため、このときremoveされると、cursorの値は必ず1つ減少します.実はここの反復器実装は基本的にAbstractListのサブクラスによってカバーされており,例えばLinkedList,ArrayListである.前者はランダムアクセスをサポートしていないので、インデックス値を取得要素として使用することはできません.そうしないと、反復器の効率が低下します.
ListIterator(extends Iterator
Listインタフェースは、Iterableインタフェースを継承するほか、リスト専用の反復器(すなわちListIterator)を取得するためのいくつかの追加の方法(listIterator)があります.LinkedListの反復器実装を参照してください.
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned = null;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
public boolean hasNext() {
return nextIndex < size;
}
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
public boolean hasPrevious() {
return nextIndex > 0;
}
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}remove操作の考え方はほぼ一致するが,lastRetをチェーンテーブルノードlastReturnedに変換し,removeのたびにnullを置く.取得要素は親バージョンのようにget(i)で直接取得されるわけではありません.反復器は、隣接する2つのノードポインタlastReturnedとnextを保存します.これにより、要素がremove(lastReturned=null)され、nextが再び呼び出されると、nextポインタ値が保存されるため、チェーンテーブル内を移動することができる.
IteratorインタフェースListIteratorインタフェースよりもaddメソッドが多く、反復器が指すnext要素の前の位置、すなわち次の要素の前の位置に要素を入れます.
Iterableインタフェース
public interface Iterable<T> {
/**
* Returns an iterator over a set of elements of type T.
*
* @return an Iterator.
*/
Iterator<T> iterator();
}Java Coreで説明したように、Iterableインタフェースを実装すればforeachサイクルで使用できます.のように
class MyCollection implements Iterable<Integer> {
@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
public int count = 0;
@Override
public boolean hasNext() {
return count < 10;
}
@Override
public Integer next() {
return count++;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
}
public class Fields implements Const {
public static void main(final String[] args) {
MyCollection myCollection = new MyCollection();
for (Integer i : myCollection) {
System.out.println(i);
}
}
}