# Sorted iterator for an unsorted list

Discussion in 'Java' started by Gyruss, Apr 11, 2005.

1. ### GyrussGuest

Dear all,

What's the preferred way to get an iterator that iterates over all elements
of an unsorted list, in sorted order? My approach was to create a copy of
the list, sort it and then return the sorted list's iterator.

This seems crude ... is it?

Cheers,
David

public Iterator getSortedIterator() {
List l = new ArrayList();
Collections.sort(l, new FooModelComparator());
return l.iterator();
}

private static class FooModelComparator implements Comparator {
public int compare(Object o1, Object o2) {
Foo s1 = (Foo) o1;
Foo s2 = (Foo) o2;
return s1.getId().compareTo(s2.getId());
}
}

Gyruss, Apr 11, 2005

2. ### John C. BollingerGuest

Gyruss wrote:

> Dear all,
>
> What's the preferred way to get an iterator that iterates over all elements
> of an unsorted list, in sorted order?

You mean that you want an iterator that returns the elements in a
sequence different from the List's current one. It is a key
characteristic of a List that it has an inherent order, so there is no
such thing as an unsorted List, just one whose elements are not in the
sequence implied by some chosen sorting scheme.

> My approach was to create a copy of
> the list, sort it and then return the sorted list's iterator.
>
> This seems crude ... is it?

If you need retain the List's current sequence and yet iterate over the
elements in a different sequence, then something like you describe is
nice and simple, and is likely to perform about as well as you can hope.
It's biggest drawback is that the iterator will not provide fail-fast
behavior relative to the original List.

If you do not need to retain the original List's sequence, then it is
better to just sort that List (or keep it in sorted order in the first
place) and use its iterator directly. You will get fail-fast behavior

If you cannot sort the original list, but do want fail-fast behavior
then it's going to start getting ugly. You could probably build an
Iterator that leverages Collections.min() and List.subList() to do its
thing, but it's going to be slower and consume more memory than any of
the other options I've discussed.

--
John Bollinger

John C. Bollinger, Apr 11, 2005