Java: Efficient Equivalent to Removing while Iterating a Collection

Question

Hello everyone.

We all know you can't do this:

for (Object i : l)
    if (condition(i)) l.remove(i);

ConcurrentModificationException etc... this apparently works sometimes, but not always. Here's some specific code:

public static void main(String[] args)
{
    Collection<Integer> l = new ArrayList<Integer>();
    for (int i=0; i < 10; ++i) {
    l.add(new Integer(4));
    l.add(new Integer(5));
    l.add(new Integer(6));
    }
    for (Integer i : l)
    {
        if (i.intValue() == 5)
            l.remove(i);
    }
    System.out.println(l);
}

This, of course, results in:

Exception in thread "main" java.util.ConcurrentModificationException

...even though multiple threads aren't doing it... Anyway.

What's the best solution to this problem? "Best" here means most time and space efficient (I realize you can't always have both!) I'm also using an arbitrary Collection here, not necessarily an ArrayList, so you can't rely on get.

Answer 1

Silly me:

Iterator<Integer> iter = l.iterator();
while (iter.hasNext()) {
    if (iter.next().intValue() == 5) iter.remove();
}

I assumed that since a foreach loop is syntactic sugar for iterating, using an iterator would help.

Answer 2

Iterator.remove() is safe.

Note that Iterator.remove is the only safe way to modify a collection during iteration; the behavior is unspecified if the underlying collection is modified in any other way while the iteration is in progress.

is from:

http://java.sun.com/docs/books/tutorial/collections/interfaces/collection.html

Answer 3

You can either use the iterator directly like you mentioned, or else keep a second collection and add each item you want to remove to the new collection, then removeAll at the end. This allows you to keep using the type-safety of the for-each loop at the cost of increased memory use and cpu time (shouldn't be a huge problem unless you have really, really big lists or a really old computer)

public static void main(String[] args)
{
    Collection<Integer> l = new ArrayList<Integer>();
    Collection<Integer> itemsToRemove = new ArrayList<Integer>();
    for (int i=0; i < 10; ++i) {
    l.add(new Integer(4));
    l.add(new Integer(5));
    l.add(new Integer(6));
    }
    for (Integer i : l)
    {
        if (i.intValue() == 5)
            itemsToRemove.add(i);
    }

    l.removeAll(itemsToRemove);
    System.out.println(l);
}

Answer 4

Since the question has been already answered i.e. the best way is to use the remove method of the iterator object, I would go into the specifics of the place where the error "java.util.ConcurrentModificationException" is thrown.

Every collection class has a private class which implements the Iterator interface and provides methods like next(), remove() and hasNext().

The code for next looks something like this...

public E next() {
    checkForComodification();
    try {
        E next = get(cursor);
        lastRet = cursor++;
        return next;
    } catch(IndexOutOfBoundsException e) {
        checkForComodification();
        throw new NoSuchElementException();
    }
}

Here the method checkForComodification is implemented as

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

So, as you can see, if you explicitly try to remove an element from the collection. It results in modCount getting different from expectedModCount, resulting in the exception "ConcurrentModificationException".