Why iterator.remove does not throw ConcurrentModif

问题:

What iterator.remove does different from list.remove that iterator does not throw exception while list.remove does throw? At the end both are modifying the collection size.

Please ignore the threading here. I am just talking about for-each loop and iterator loop. As far as I know for-each loop internally create iterator only.

I am confused.

回答1:

ConcurrentModificationException is not thrown by Iterator.remove() because that is the permitted way to modify an collection while iterating. This is what the javadoc for Iterator says:

Removes from the underlying collection the last element returned by this iterator (optional operation). This method can be called only once per call to next(). The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method.

If you change the collection being iterated any other way, then you are liable to get an exception, depending on the implementation of iterator, and the collection (or whatever) that you are iterating. (Some collection classes won't give you a ConcurrentModificationException: check the respective javadocs to see how they specify the behavior of their iterators)

You are also liable to get an exception if you have two iterators on the same collection, and you remove via one of them.

---

What iterator.remove does different from list.remove that iterator does not throw exception while list.remove does throw?

The deal is that when you remove via the iterator, the implementation of the iterator is able to update its data structures to take account of the deletion. By contrast, if you remove (or insert, or replace) via the collection object, the iterator data structure cannot be updated to keep it in step with the collection.

Why? Because it would require the following:

• There would need to be link from the collection data structure to all of the extant iterator objects. Such links have either a risk of memory leaks or require the use of Reference objects to avoid leaks.

• On each update to a collection, "keep in step" updates would be required for each iterator. That would make collections updates a lot more expensive.

There is also the issue that the non-concurrent collection types are not implemented to be thread-safe, so you could also have anomalies if the collection and iterator are used / updated by different threads.

These issues motivate the design choices for the collections APIs.

---

I am just talking about for-each loop and iterator loop. As far as I know for-each loop internally create iterator only.

That is correct. A for-each loop is really just syntactic sugar for a while loop using an iterator.

On the other hand, if you use a loop like this:

    for (int i = 0; i < list.size(); i++) {
        if (...) {
            list.remove(i);
        }
    }

you won't get ConcurrentModificationException, but you will need to adjust the index variable for the elements that you delete, and updates by another thread are liable to cause you to skip elements or visit them more than once².

---

^{2 - Or even get an IndexOutOfBoundsException. And if the collection is not concurrent / properly synchronized, ytou can get worse problems.}

回答2:

I think you mean, if you're iterating a list, why does list.remove() cause a ConcurrentModificationException to be thrown whereas iterator.remove() does not?

Consider this example:

    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
        }
    }

If you uncomment line #1, it will work fine. If you uncomment line #2 (but leave #1 commented) then it will cause the subsequent call to iter.next() to throw ConcurrentModificationException.

The reason is that the iterator is a separate object that has some references to the internal state of the underlying list. If you modify the list while the iterator is in operation, it could cause the iterator to behave badly, e.g. by skipping elements, repeating elements, indexing off the end of the array, etc. It attempts to detect such modifications and so it throws ConcurrentModificationException if it does.

Removing elements through the iterator works and does not cause exceptions, because this updates the underlying list and the iterator's state that refers to the internals of the list, so everything can stay consistent.

However, there is nothing special about iterator.remove() that makes it work in all cases. If there are multiple iterators iterating over the same list, modifications made by one will cause problems for the others. Consider:

    Iterator<String> i1 = list.iterator();
    Iterator<String> i2 = list.iterator();
    i1.remove();
    i2.remove();

We now have two iterators pointing into the same list. If we modify the list using one of them, it disrupts the operation of the second, so the call to i2.remove() will result in ConcurrentModificationException.

回答3:

Because it is the iterator that throws the exception. If you call List.remove() it doesn't know about the removal, only that something has changed under its feet. If you call Iterator.remove() it knows the current element was removed and what to do about it.

回答4:

Here is an example how things could go wrong if collection iterators didn't check for modifications of the underlying collection. This is how ArrayLists's iterator is implemented:

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

Let's look at an example:

List list = new ArrayList(Arrays.asList(1, 2, 3, 4));
Iterator it = list.iterator();
Integer item = it.next();

We remove the first element

list.remove(0);

If we want to call it.remove() now, the iterator would remove number 2 because that's what field lastRet points to now.

if (item == 1) {
   it.remove(); // list contains 3, 4
}

This would be incorrect behavior! The contract of the iterator states that remove() deletes the last element returned by next() but it couldn't hold it's contract in the presence of concurrent modifications. Therefore it chooses to be on the safe side and throw an exception.

The situation may be even more complex for other collections. If you modify a HashMap, it may grow or shrink as needed. At that time, elements would fall to different buckets and an iterator keeping pointer to a bucket before rehashing would be completely lost.

Notice that iterator.remove() doesn't throw an exception by itself because it is able to update both the internal state of itself and the collection. Calling remove() on two iterators of the same instance collection would throw, however, because it would leave one of the iterators in an inconsistent state.

回答5:

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

You can see the above 3 cases

case 1: Modification made by adding the element, hence when next() function is used it resulted in ConcurrentModificationException.

case 2: Modification made by using the retain(), hence when next() function is used it resulted in ConcurrentModificationException.

case 3: Will throw java.lang.IllegalStateException not ConcurrentModificationException.

Output:

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)