Чем iterator.remove() отличается от list.remove(), так что итератор не выдает исключение, а list.remove() выдает его? В конце концов, оба изменяют размер коллекции.
Пожалуйста, игнорируйте многопоточность здесь. Я просто говорю о цикле for-each и цикле итератора. Насколько я знаю, цикл for-each создает итератор только внутри.
Я смущен.
ConcurrentModificationException не генерируется Iterator.remove(), потому что это разрешенный способ изменить коллекцию во время итерации. Вот что говорит javadoc для Iterator:
Удаляет из базовой коллекции последний элемент, возвращаемый этим итератором (необязательная операция). Этот метод может быть вызван только один раз за вызов функции next(). Поведение итератора не определено, если базовая коллекция изменена во время выполнения итерации любым другим способом, кроме вызова этого метода.
Если вы изменяете коллекцию, повторяемую любым другим способом, вы обязаны получить исключение, в зависимости от реализации итератора и коллекции (или любой другой), которую вы повторяете. (Некоторые классы коллекций не дают вам ConcurrentModificationException: проверьте соответствующие javadocs, чтобы увидеть, как они определяют поведение своих итераторов)
Вы также обязаны получить исключение, если у вас есть два итератора в одной коллекции, и вы удаляете через один из них.
Чем iterator.remove отличается от list.remove тем, что итератор не выдает исключение, в то время как list.remove выдает?
Причина № 1. Если бы вы одновременно обновляли не параллельную коллекцию из двух мест в одном и том же стеке вызовов, такое поведение нарушало бы проектный инвариант для итерации 1. Итерация неконкурентной коллекции гарантирует, что все элементы в коллекции будут видны ровно один раз. (Напротив, в случае одновременных коллекций эти гарантии ослаблены.)
Причина № 2. Неконкурентные типы коллекций не реализованы как поточно-ориентированные. Следовательно, могут возникнуть условия гонки и аномалии памяти, если коллекция и итератор используются для обновления коллекции различными потоками. Это не веская причина, потому что у вас все равно будут эти проблемы. Однако наличие обновлений двумя различными способами усугубляет проблему.
Я просто говорю о цикле for-each и цикле итератора. Насколько я знаю, для каждого цикла внутренне создается только итератор.
Это верно. Цикл for-each - это на самом деле просто синтаксический сахар для цикла while с использованием итератора.
С другой стороны, если вы используете цикл вроде этого:
for (int i = 0; i < list.size(); i++) {
if (...) {
list.remove(i);
}
}
вы не получите ConcurrentModificationException, но вам нужно будет настроить переменную индекса для элементов, которые вы удаляете, а обновления другого потока могут заставить вас пропускать элементы или посещать их более одного раза 2.
1 - To achieve "exactly once" iteration behavior, when you remove an element via the collection object, the iterator data structure would need to be updated to keep it in step with what has happened to the collection. This is not possible in the current implementations because they don't keep links to the outstanding iterators. And if they did, they would need to use [TG47] objects or risk memory leaks.
2 - Or even get an [TG48]. And if the collection is not concurrent / properly synchronized, you can get worse problems.
Я думаю, вы имеете в виду, что если вы выполняете итерацию списка, почему list.remove() вызывает list.remove() ConcurrentModificationException, а iterator.remove() - нет?
Рассмотрим этот пример:
List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c", "d"));
for (Iterator<String> iter = list.iterator(); iter.hasNext(); ) {
if (iter.next().equals("b")) {
// iter.remove(); // #1
// list.remove("b"); // #2
}
}
Если вы раскомментируете строку # 1, она будет работать нормально. Если вы раскомментируете строку # 2 (но оставите комментарий # 1), то последующий вызов iter.next() вызовет iter.next() ConcurrentModificationException.
Причина в том, что итератор - это отдельный объект, который имеет некоторые ссылки на внутреннее состояние базового списка. Если вы измените список во время работы итератора, это может привести к тому, что итератор будет вести себя плохо, например, пропуская элементы, повторяя элементы, индексируя конец массива и т.д. Он пытается обнаружить такие модификации и поэтому выдает ConcurrentModificationException если это так.
Удаление элементов через итератор работает и не вызывает исключений, потому что это обновляет базовый список и состояние итератора, которое ссылается на внутренние элементы списка, поэтому все может оставаться согласованным.
Однако в iterator.remove() нет ничего особенного, что делает его работоспособным во всех случаях. Если есть несколько итераторов, повторяющихся в одном и том же списке, изменения, сделанные одним, вызовут проблемы для других. Рассматривать:
Iterator<String> i1 = list.iterator();
Iterator<String> i2 = list.iterator();
i1.remove();
i2.remove();
Теперь у нас есть два итератора, указывающие на один и тот же список. Если мы изменим список с помощью одного из них, он нарушит работу второго, поэтому вызов i2.remove() приведет к i2.remove() ConcurrentModificationException.
Потому что именно итератор генерирует исключение. Если вы вызываете List.remove(), он не знает об удалении, только что-то изменилось под ногами. Если вы вызываете Iterator.remove(), он знает, что текущий элемент удален и что с ним делать.
Вот пример, как все может пойти не так, если итераторы коллекции не проверяли изменения базовой коллекции. Вот как реализуется итератор ArrayLists:
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
public E next() {
checkForComodification();
int i = cursor;
if (i >= size) throw new NoSuchElementException();
// ...
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
// ...
ArrayList.this.remove(lastRet);
// ...
cursor = lastRet;
lastRet = -1;
}
Посмотрим на пример:
List list = new ArrayList(Arrays.asList(1, 2, 3, 4));
Iterator it = list.iterator();
Integer item = it.next();
Удалим первый элемент
list.remove(0);
Если мы хотим называть it.remove() теперь, итератор удалит номер 2, потому что теперь указывает то, что поле lastRet.
if (item == 1) {
it.remove(); // list contains 3, 4
}
Это было бы неправильное поведение! Контракт итератора гласит, что remove() удаляет последний элемент, возвращаемый next(), но он не может удерживать его в контракте при наличии одновременных изменений. Поэтому он предпочитает быть в безопасности и исключать.
Ситуация может быть еще более сложной для других коллекций. Если вы измените HashMap, он может увеличиваться или уменьшаться по мере необходимости. В это время элементы будут попадать в разные ведра, а итератор, сохраняющий указатель на ведро, прежде чем перезагрузка будет полностью потеряна.
Обратите внимание, что iterator.remove() не генерирует исключение самостоятельно, поскольку оно может обновлять как внутреннее состояние, так и коллекцию. Вызов remove() на двух итераторах той же коллекции экземпляров будет бросать, однако, потому что он оставит один из итераторов в несогласованном состоянии.
public class ArrayListExceptionTest {
public static void main(String[] args) {
ArrayList<String> list1 = new ArrayList<>();
list1.add("a");
list1.add("b");
list1.add("c");
Iterator<String> it1 = list1.iterator();
ArrayList<String> list2 = new ArrayList<String>();
list2.add("a");
try {
while (it1.hasNext()) {
list1.add(it1.next());
}
} catch (ConcurrentModificationException e) {
e.printStackTrace();
}
it1 = list1.iterator();
while (it1.hasNext()) {
System.out.println(it1.next());
}
it1 = list1.iterator();
try {
while (it1.hasNext()) {
if (it1.next().equals("a"))
list1.retainAll(list2);
}
} catch (ConcurrentModificationException e) {
e.printStackTrace();
}
it1 = list1.iterator();
while (it1.hasNext()) {
System.out.println(it1.next());
}
it1 = list1.iterator();
Iterator<String> it2 = list1.iterator();
it1.remove();
it2.remove();
}
}
Вы можете увидеть выше 3 случая
случай 1: изменение, произведенное путем добавления элемента, следовательно, при использовании функции next() это привело к исключению ConcurrentModificationException.
Случай 2: модификация, выполненная с использованием retain(), следовательно, когда используется функция next(), это привело к ConcurrentModificationException.
Случай 3: вызовет исключение java.lang.IllegalStateException, а не ConcurrentModificationException.
Выход:
a
b
c
a
a
a
java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
at java.util.ArrayList$Itr.next(ArrayList.java:859)
at com.rms.iteratortest.ArrayListExceptionTest.main(ArrayListExceptionTest.java:21)
java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
at java.util.ArrayList$Itr.next(ArrayList.java:859)
at com.rms.iteratortest.ArrayListExceptionTest.main(ArrayListExceptionTest.java:37)
Exception in thread "main" java.lang.IllegalStateException
at java.util.ArrayList$Itr.remove(ArrayList.java:872)
at com.rms.iteratortest.ArrayListExceptionTest.main(ArrayListExceptionTest.java:55)