Iterator란 정확히 어떤 객체를 가리키는 말인가 나는 잘 모르겠다...
그래서 시험기간에 하기 좋은... '시험에 안 나올 것 같은 것을 공부라는 이름 아래에 죄책감 없이 쳐다보기'를 하려고 한다.
Iterator란 무엇인가
- Java의 Collection framework에서 제공하는 어떤 인터페이스
- 사용자가 Collection의 내부 구조를 모르더라도 탐색하고 값에 접근할 수 있도록 해줌
- hasNext, next, remove 요 세 개를 가장 기본적인 메소드로 삼는 것 같다.
그래서 Iterator란 정확히 무엇인가
이 고민을 하게 된 것은 이런 메소드 때문이다.
public static void f(List<String> a, List<String> b) {
ListIterator<String> aIter = a.listIterator();
ListIterator<String> bIter = b.listIterator();
while (aIter.hasNext()) {
String s1 = aIter.next();
bIter.add(s1); // 요기
aIter.remove(s1);
}
}
}로직은 간단하게...
- a, b라는 list가 있고
- a를 순회하면서 a 값이 있으면 그걸 a에서 지우고 b에 넣는다.
그런데 주석으로 '//요기'라고 표시한 줄의 코드를 b.add(t2)로 바꾸면 ConccurentModificationException이 터진다. Iterator가 쳐다보고 있는 리스트가 변경되었기 때문에 터지는 것이다. 이해하기로는 아래와 같은 상황에서 exception이 터지는 것과 같은 맥락이다. (자바의 for-each문은 내부적으로 Iterator를 쓰도록 구현되어 있기 때문에 사실 완전히 같은 상황임)
for (Object obj : someList) {
someList.add(something); // exception
}여기서 이해가 잘 안되는 것이 있다...
aIter = a.ListIterator(); 했을 때, aIter는 무엇의 listIterator가 되는가?
왜 순회할 때에 aIter.add()는 해도 되고 a.add()는 하면 안되는가?
a의 요소를 변경한다는 점에서, 만약 a.add() 했을 때 exception이 터진다면 aIter.add()에서도 터져야 하는 것 아닌가? aIter는 커서 위치를 알고 있으므로 괜찮은 것인가?...
공식 문서를 살펴보자
ListIterator에 대해 알아보자 (공식 문서와 함께...)
공용 인터페이스 ListIterator<E> extends Iterator<E>
프로그래머가 리스트를 어느 방향 으로든 순회하고, 반복하는 동안 리스트를 수정하고, 리스트에서의 현재 위치를 취득할 수 있는 리스트용 이터레이터입니다. ListIterator에는 현재 요소가 없으며, 커서 위치는 항상 previous() 호출로 반환되는 요소와 next() 호출로 반환되는 요소 사이에 위치합니다. 아래 캐럿(^)으로 표시된 것처럼 길이 n의 목록에 대한 이터레이터에는 n+1개의 가능한 커서 위치가 있습니다:
- ListIterator를 사용하면 반복하는 동안 콜렉션을 수정할 수 있다.
- ListIterator는 콜렉션에서 요소를 가리키는 것이 아니라 요소와 요소 사이의 커서를 나타낸다.
지정된 엘리먼트를 목록에 삽입합니다(optional). 요소는 next()에 의해 반환될 요소가 있으면 바로 앞에, previous()에 의해 반환될 요소가 있으면 뒤에 삽입됩니다. (목록에 요소가 없는 경우 새 요소가 목록의 유일한 요소가 됩니다.) 새 요소는 암시적 커서 앞에 삽입됩니다. next 호출은 영향을 받지 않고, previous 호출은 새 요소를 반환합니다. (이 호출은 nextIndex 또는 previousIndex에 대한 호출에서 반환되는 값을 1 증가시킵니다.)
- ListIterator.add()는 next() 값이 유효하면 커서 앞, previous() 값이 유효하면 커서 뒤에 요소를 삽입한다.
- add한 뒤 next는 영향을 받지 않는다. (커서 앞에 삽입했으므로)
- add한 뒤 previous는 add한 요소를 나타낸다. (커서 뒤에 삽입했으므로)
여기까지 읽고 나니 약간 이해가 된다.... 일반적으로는 Iterate하는 중에 순회하는 콜렉션이 변경되면 안되지만, Iterator는 그것을 위해서 (순회하는 중에 배열을 수정하기 위해서) 설계되었기 때문에 add를 해도 안전하도록 설계되어 있는 것이다. 그래도 약간 명쾌하지 않아서 구글링을 좀 해봤다.
왜냐하면 그렇게 설계되었기 때문에
참고한 링크
List는 구조적으로 수정된 횟수를 추적하는 modCount라는 transient variable을 사용함으로써 ConcurrentModificationExeption를 감지한다. 구조적 수정(Structural modification)은 목록의 크기를 변경하는 수정으로, iteration에 영향을 미쳐 잘못된 결과를 초래할수 있다.
Iterator와 ListIterator는 모두 이 필드를 사용하여 예기치 않은 변경을 감지한다. List를 구조적으로 수정하는 List의 다른 메서드들도 add(), remove()와 같이 이 메서드를 사용한다.
원인: ConcurrentModfiicationException의 실제 원인은 일관되지 않은 modCount입니다. ArrayList를 반복할 때 Iterator의 next() 메서드는 modCount를 추적합니다. 요소를 추가하거나 제거하여 컬렉션을 수정하면 modCount가 변경되고 예상 modCount와 일치하지 않으므로 Iterator는 ConcurrentModificationException을 던집니다.
LinkedList의 listIterator의 내부 구현을 직접 보면 이렇다. 링크
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}checkForComodification()의 내부 구현은 이렇다.
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}위의 설명 대로, modCount가 expecteModCount와 다르면 exception을 던진다. 콜렉션을 직접 변경해서 iterator가 모르는 변화가 생기면 iterator가 exception을 던지는 것임.
expectedModCount는 ListItr가 private int field로 가지고 있고, modCount 값으로 초기화한다.
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;아래는 ListItr의 add 메소드 구현이다.
linkLast나 linkBefore를 하고, expectedModCount를 1 증가시킴.
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}아래는 linkedList의 addFirst, addLast 메소드 구현이다.
/**
* Inserts the specified element at the beginning of this list.
*
* @param e the element to add
*/
public void addFirst(E e) {
linkFirst(e);
}
/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #add}.
*
* @param e the element to add
*/
public void addLast(E e) {
linkLast(e);
}공통으로 사용하는 linkLast 메소드의 구현은 이렇다.
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}노드를 새로 만들고, 그걸 맨 뒤에 붙인다. 암튼 앞은 별로 안 중요하고 중요한 건 modCount++;를 한다는 것임.
즉 listIterator를 사용할 때 expectedModCount++을 modCont++이랑 같은 타이밍에 해주지 않으면 listIterator가 알지 못하는 변화가 있었기 때문에 checkForComodification를 통과하지 못하고 exception이 터지는 것이다.
결론
맨 처음 코드로 돌아가보면
public static void f(List<String> a, List<String> b) {
ListIterator<String> aIter = a.listIterator();
ListIterator<String> bIter = b.listIterator();
while (aIter.hasNext()) {
String s1 = aIter.next();
bIter.add(s1); // 요기
aIter.remove(s1);
}
}
}- bIter.add(s1)은 add를 수행하고 expectedModCount를 1 증가시킨다. 근데 add 할 때 modCount도 1이 증가되므로, checkForComodification를 통과한다.
- 주석으로 '//요기'라고 적어놓은 부분을 b.add(s1)으로 바꾸면, modCount는 1 증가하지만 expectedModCount는 증가하지 않아서 checkForComodification를 통과하지 못하고 ConcurrentModificationException이 터지는 것이다.
- 정확히는 add를 한 다음 iteration의 add()에서 터지는 것
- 저렇게 바꿔서 수행한 다음 checkForComodification를 지날 때 exception이 터진다
아 재밌었따
이제 공부해야지...
