Почему вызов метода remove () для итератора дает исключение ConcurrentModificationException?

Question

Я пытаюсь написать очень простой метод удаления дубликатов в LinkedList:

Я пытаюсь сделать это без использования дополнительного буфера, поэтому я поддерживаю два итератора в связанном списке, один выполняет обычную итерациюи другой перебирает все предыдущие узлы для проверки на наличие ошибок (как указано в CareerCup);тем не менее, компилятор сообщает мне, что есть CME, хотя я вызываю itr1.remove ():

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();
            }
        }

    }
}

Другое простое решение этой проблемы с помощью хэш-набора легко выполнить следующим образом, и об исключениях не сообщается:

    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

С API документы :

Итераторы, возвращаемые методами iterator и listIterator этого класса, fail-fast : еслиСписок структурно изменяется в любое время после создания итератора, любым способом, кроме использования собственных методов итератора remove или add, итератор выдаст ConcurrentModificationException.

Answer 2

В первом случае да - вы изменяете содержимое коллекции с помощью iterator2, в то время как iterator1 не знает об изменениях. Во втором случае HashSet / HashMap не позволяют удалять элементы во время их итерации.

Вы можете добавить удаленные элементы в другую коллекцию и удалить их все после итерации. Э.Г.

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

Надеюсь, это поможет.

P.S. подробнее о том, как удалить элементы из списка, касающиеся сложности алгоритма, вы можете прочитать здесь Устранение проблемы с объектом ArrayList

Answer 3

Да, вы можете исправить это, не используя дополнительное пространство.

Проблема заключается в выполнении этих двух строк одна за другой.

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

Вы можете использовать два итератора для одного и того же списка одновременно. Если вы осторожны .
Но как только один из этих итераторов изменил список (как это происходит с itr1.remove()), вы больше не можете использовать другой итератор (поэтому вы не можете вызвать itr2.hasNext()).

Решение состоит в том, чтобы поставить break после itr1.remove(). И обновить 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;
      }
    }
  }
}

Это не лучшие решения с точки зрения вычислительной сложности. Если пространство памяти не является проблемой, решение с использованием хэш-набора является лучшим в отношении сложности вычислений.

Но речь идет о параллельной обработке через итераторы, а не об оптимизации сложности.

Answer 4

Причина, по которой вы получаете CME, была объяснена другими, вот возможный способ, который вы можете использовать для удаления дубликатов

Использование списка toRemove для записи элемента в первый раз iterator наткнуться на него,затем, когда встретитесь снова с записанным элементом, удалите его, используя 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 5

Да.Вы можете думать об этом так: когда вы создаете итератор, он получает текущий «счетчик изменений» списка.Когда итератор удаляет элемент из списка, он проверяет счетчик изменений, чтобы увидеть, соответствует ли он ожиданиям, и, если все в порядке, он удаляет элемент и обновляет счетчик изменений как для итератора, так и для списка.У другого итератора все еще будет старое количество модификаций, и он увидит новое значение и выбросит CME.

Способ, основанный на хеш-наборе, является правильным решением в большинстве случаев.Он будет работать намного лучше - два прохода O (n) обычно лучше, чем O (n ^ 2), как это могло бы дать вложенное итерационное решение (если бы оно работало).

Answer 6

Вы получаете CME, потому что список изменен вторым итератором, и первый итератор не знает об этом изменении.Когда в следующий раз он попытается получить доступ к списку, он уже будет изменен.И, следовательно, он выдает исключение.

Пожалуйста, используйте только один итератор для изменения списка за раз.