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.

Fatma

Answer 1

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.

Secluded

Answer 2

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.

Passional

It's clear answer for single iterator p pointing into collection c. What about having two iterators p and q pointing into the same collection c and iterated independently? Does "except via the iterator itself" mean specific instance of iterator like p or it means any instance of iterator? I guess independent iteration of p and q will invalidate each other (simply because neither iterators know about other iterators nor collection remembers all its iterators), but it's good to clarify it here. Thanks! – Babita

@uvsmtid: It's except via that specific iterator. If you have two iterators over the same collection, then you can't modify the collection via either of them, unless it's a collection that explicitly supports concurrent modification. – Passional

Answer 3

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.

Remission

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.

Robbins

Where "normally" includes "might see the same element again"... I'm slightly disappointed that this doesn't throw an exception, to be honest. – Passional

The exception isn't guaranteed to be thrown, it's for debugging. – Secluded