이터레이터에서 remove()를 호출하면 ConcurrentModificationException이 발생하는 이유는 무엇입니까?

Question

LinkedList에서 중복을 제거하는 매우 간단한 방법을 쓰려고합니다 :

추가 버퍼를 사용하지 않고이 작업을 시도하므로 링크 된 목록에 두 개의 반복자를 유지합니다. 하나는 일반 반복을 유지하고 다른 하나는 유지합니다. (CareerCup에 표시된대로) 모든 이전 노드를 반복하여 중복을 확인합니다. 다음과 같이

public static void RemoveWithoutBuffer(LinkedList l) { 
    ListIterator itr1 = l.listIterator(); 
    int count1 = 0; 
    int count2 = 0; 
    while (itr1.hasNext()) { 
     Object next = itr1.next(); 
     count1++; 
     count2 = 0; 
     ListIterator itr2 = l.listIterator(); 
     while (itr2.hasNext()) { 
      count2++; 
      if (count2 == count1) 
       break; 
      if (itr2.next() == next){ 
       itr1.remove(); 
      } 
     } 

    } 
} 

HashSet의의 도움으로이 문제의 또 다른 간단한 해결책은 간단하고도 예외는보고되지 : 그러나, 컴파일러가 내게 말하길가 심지어 내가) (itr1.remove를 호출하고 비록 CME입니다

public static void Remove(LinkedList l) { 
    HashSet set = new HashSet(); 
    ListIterator itr = l.listIterator(); 
    while (itr.hasNext()) { 
     Object next = itr.next(); 
     if (set.contains(next)) 
      itr.remove(); 
     else 
      set.add(next); 
    } 
} 

itr2를 반복 할 때 itr1을 수정할 수 없기 때문에 그렇습니까? 이 문제를 해결할 수있는 방법이 있습니까? 고마워.

Answer 1

첫 번째 경우 예 - iterator1이 변경 사항을 인식하지 못하는 동안 iterator2를 통해 콜렉션의 내용을 변경합니다. 두 번째 경우 HashSet/HashMap은 요소를 반복하면서 요소를 제거하는 것을 허용하지 않습니다.

제거 된 요소를 다른 컬렉션에 추가하고 반복 후 모든 요소를 ​​제거 할 수 있습니다. 예 :

List toRemove = new ArrayList(); 
    for (Object next : collection) { 
     if (someCondition) toRemove.add(next); 
    } 
    collection.removeAll(toRemove); 

도움이되기를 바랍니다.

P. 알고리즘 복잡성에 관한 목록에서 요소를 제거하는 방법에 대한 자세한 내용은 여기를 참조하십시오. Removing ArrayList object issue

Answer 2

목록이 두 번째 이터레이터에 의해 수정되고 첫 번째 이터레이터가 해당 변경을 인식하지 못하기 때문에 CME가 표시됩니다. 다음 번에 목록에 액세스하려고하면 이미 수정 된 것입니다. 그리고 따라서 그것은 예외를 던집니다.

한 번에 하나의 목록을 수정하려면 반복자를 하나만 사용하십시오.

Answer 3

예. 이 방법으로 생각할 수 있습니다. 반복자를 만들면 목록의 현재 "수정 횟수"를 가져옵니다. 반복자가 목록에서 요소를 제거하면 수정 횟수를 확인하여 예상되는 내용인지 확인하고 모두 괜찮 으면 요소를 제거하고 반복자와 목록에서 수정 횟수를 업데이트합니다. 다른 반복자는 여전히 이전 수정 횟수를 가지며 새 값을보고 CME를 던집니다.

대부분의 경우 해시 세트 기반 방식이 올바른 해결책입니다. 중첩 된 반복 솔루션이 생성 할 때 O (n^2)보다 O (n) 개의 패스가 두 개 더 잘 수행됩니다 (작동하는 경우). the API docs에서

Answer 4

:이 클래스의 iterator 및 listIterator 방법에 의해 반환

반복자 있습니다 르파 : 반복자의 작성 후에리스트는 구조적으로 어떤 방식으로, 어떤 시간이 변경되면 Iterator 자신의 remove 또는 add 메서드를 사용하는 경우를 제외하고는 반복기가 ConcurrentModificationException이됩니다.

Answer 5

당신은 CME가 다른 사람에 의해 설명되었다받을 이유, 여기 당신이 때 대회 이후, 그것에 처음 iterator 비틀 거림에 요소를 기록하는 데 사용에게 목록 toRemove을 DUPS

을 제거하는 데 사용할 수있는 가능한 방법입니다 다시 녹음 된 요소를 사용하여 제거하십시오. iterator.remove()

 
private void removeDups(List list) { 
     List toRemove = new ArrayList(); 
     for(Iterator it = list.iterator(); it.hasNext();) { 
      Object next = it.next(); 
      if(!toRemove.contains(next)) { 
       toRemove.add(next); 
      } else { 
       it.remove(); 
      } 
     } 
     toremove.clear(); 
    } 

Answer 6

예, 추가 공간을 사용하지 않고이 문제를 해결할 수 있습니다.

이 두 줄을 차례로 실행하면 문제가 발생합니다.

• itr1.remove();
• itr2.hasNext();

같은 목록에 두 개의 반복자를 동시에 사용할 수 있습니다. 신중한 경우.
그러나이 반복자 중 하나가 목록을 수정하면 (itr1.remove()으로 발생) 다른 이터레이터를 더 이상 사용할 수 없으므로 (itr2.hasNext()으로 전화 할 수 없음).

해결책은 itr1.remove() 다음에 break을 넣는 것입니다. 그리고 count1를 업데이트 :

이

public static void RemoveWithoutBuffer(LinkedList l) { 
    ListIterator itr1 = l.listIterator(); 
    int count1 = 0; 
    int count2 = 0; 
    while (itr1.hasNext()) { 
     Object next = itr1.next(); 
     count1++; 
     count2 = 0; 
     ListIterator itr2 = l.listIterator(); 
     while (itr2.hasNext()) { 
      count2++; 
      if (count2 == count1) 
       break; 
      if (itr2.next() == next){ 
       itr1.remove(); 
       --count1; 
       break; 
      } 
     } 
    } 
} 

더 우아한 솔루션은 현재 전 오히려 요소보다 현재 후 요소를 비교하는 것입니다 :

public static void RemoveWithoutBuffer(LinkedList l) { 
    ListIterator itr1 = l.listIterator(); 
    while (itr1.hasNext()) { 
    Object next = itr1.next(); 
    ListIterator itr2 = l.listIterator(itr1.nextIndex()); 
    while (itr2.hasNext()) { 
     if (itr2.next() == next) { 
     itr1.remove(); 
     break; 
     } 
    } 
    } 
} 

이러한 측면에서 최상의 솔루션되지 않습니다 계산상의 복잡성. 메모리 공간이 문제가되지 않는다면 해시 셋 솔루션은 계산상의 복잡성과 관련하여 더 나은 솔루션입니다.

그러나 문제는 반복자를 통한 동시 모핑과 복잡도 최적화가 아니라는 점입니다.