When I sort a List what happens to its iterators?

Question

Let's say I have a List object and an iterator for that list.

Now I sort the list with java.util.Collections.sort()

• What happens to the iterator?
• Is its behavior still defined and can it still be used?
• If not, can I prevent destroying the iterators for the list?

I know, this problem could be circumvented by changing the program design, cloning the list for example, but I specificly want to know the "official" behavior of Java.

Answer 1

Iterators are generally invalid after any modification to their underlying collections, except via the iterator itself. (For instance, ListIterator allows for insertion and removal.)

I'd certainly expect any iterators to become invalidated after a sort though - and if they weren't, I'd have no idea what order to expect.

Answer 2

Generally, any kind of mutation on a collection will invalidate its iterators. A mutation done through an iterator will not invalidate that iterator. There are some exceptional collection implementations, such as CopyOnWriteArrayList.

The general solution would be to sort a copy of the collection or recreate your iterators.

Answer 3

Most of the collections in java.util are "fail-fast" and may throw a ConcurrentModificationException if the underlying collection is changed. It should be pointed out that this is intended for debugging and so is not guaranteed. According to the javadocs, this is true of all decedents of AbstractList, but this is not true of CopyOnWriteArrayList, which is intended for multi-threaded use.

Answer 4

I wrote some code to see what happens when a collection is sorted while you are iterating. It seems that the iterator does not throw any exceptions, but continues to iterate normally. Still it gives you wrong results if you are expecting to iterate over the collection unsorted. Look at that :

public static void main(String[] args) {
    List<String> list = new ArrayList<String>();
    list.add("D");
    list.add("B");
    list.add("A");
    list.add("C");
    list.add("E");

    Iterator<String> it = list.iterator();
    String s = it.next();
    System.out.println(s);
    s = it.next();
    System.out.println(s);

    Collections.sort(list);
    Iterator<String> it2 = list.iterator();

    s = it.next();
    System.out.println(s);
    s = it.next();
    System.out.println(s);
    s = it.next();
    System.out.println(s);

    while (it2.hasNext()) {
        System.out.println(it2.next());
    }
    }

Hope it helps.