What is the "good" (and why ?) solution to get a List from a Set and sorted against a given Comparator ?
views:
83answers:
5
+3
A:
Just construct it. The ArrayList has a constructor taking another Collection.
Set<Foo> set = new TreeSet<Foo>(new FooComparator<Foo>());
// Fill it.
List<Foo> list = new ArrayList<Foo>(set);
// Here's your list with items in the same order as the original set.
BalusC
2010-10-13 12:12:27
A:
This is how you get a List when you have a Set:
List list = new ArrayList(set);
Not sure what you expect to do with the Comparator. If the Set is sorted, the list will contain the elements in sorted order.
Michael Borgwardt
2010-10-13 12:12:29
Obviously he expects to use the comparator to get a sorted list, implying that the set is unsorted. What else would you use a comparator for? So he should either go via a sorted set or sort the list after populating it.
Christoffer Hammarström
2010-10-13 12:33:18
@Christoffer Hammarström - or sort it when/by inserting the elements one by one : insertion sort.
Ishtar
2010-10-13 12:39:40
@Ishtar: Which is what happens if you go via a sorted set, my first suggestion.
Christoffer Hammarström
2010-10-13 12:51:29
+1
A:
Set<Object> set = new HashSet<Object>();
// add stuff
List<Object> list = new ArrayList<Object>(set);
Tyler
2010-10-13 12:14:47
Wrong answer, this won't work as ArrayList constructor doesn't sort anything, you haven't even used your Comparator, so how will be it sorted? Use either Collections.sort() or TreeSet, as in other answers.
iirekm
2010-10-14 10:40:22
+1
A:
Either:
Set<X> sortedSet = new TreeSet<X>(comparator); ...
List<X> list = new ArrayList<X>(sortedSet);
or:
Set<X> unsortedSet = new HashSet<X>(); ...
List<X> list = new ArrayList<X>(unsortedSet);
Collections.sort(list, comparator);
iirekm
2010-10-13 12:24:10
+1
A:
Assuming that you start with an unsorted set or a set sorted on a different order, the following is probably the most efficient assuming that you require a modifiable List.
Set<T> unsortedSet = ...
List<T> list = new ArrayList<T>(unsortedSet);
Collections.sort(list, comparator);
If an unmodifiable List is acceptable, then the following is a bit faster:
Set<T> unsortedSet = ...
T[] array = new T[unsortedSet.size()];
unsortedSet.toArray(array);
Arrays.sort(array, comparator);
List<T> list = Arrays.asList(array);
In the first version, Collections.sort(...) copies the list contents to an array, sorts the array, and copies the sorted elements back to the list. The second version is faster because it doesn't need to copy the sorted elements.
But to be honest the performance difference is probably not significant. Indeed, as the input set sizes get larger, the performance will be dominated by the O(NlogN) time to do the sorting. The copying steps are O(N) and will reduce in importance as N grows.
Stephen C
2010-10-13 13:26:34
Your version with Arrays.sort in fact doesn't optimize much (or even nothing), because Collections.sort() already contains similar code: Object[] a = list.toArray(); Arrays.sort(a, (Comparator)c); ListIterator i = list.listIterator(); for (int j=0; j<a.length; j++) { i.next(); i.set(a[j]); }
iirekm
2010-10-14 10:46:51
@iirekm - using `Arrays.asList(array)` avoids the copying performed using the list iterator.
Stephen C
2010-10-14 11:36:23
@iirekm - yes. But as I mentioned, as N gets really large, the cost of sorting dominates the cost of copying.
Stephen C
2010-10-15 11:52:01