Re: A suitable container that can sort -- please help!
Simon wrote:
- If you gather all the Point/double pairs and then want to process
them in sorted order, begin by putting them in a List without
regard to order. When you've gathered them all, sort the List
with Collections.sort(), and then traverse the sorted List.
Will be n log(n) for sorting, but again does not allow for updates.
Some Lists does.
Example:
List<String> l = new ArrayList<String>(Arrays.asList("b", "a", "c"));
Collections.sort(l);
String s = "abc";
int i = Collections.binarySearch(l, s);
l.add(i < 0 ? -(i + 1) : i, s);
This is at par with the SortedSet solution. Inserting n times, each in
time log(n) will also require time n log(n).
Not exactly, SortedSet typically forms the binary tree, so time needed
will typically be O(n^2).
However, the SortedSet
allows for updates.
Lists allows for updates as well. Typically, with log(n) for lookup,
and amortized constant time for insert (i.e. adding n elements requires
O(n) time). No important difference asymptotically.
So, one sort of List with n elements (usually marge-sort for
RandomAccess lists) with relatively big n is typically faster than n
add()s to SortedSet (tree-sort equivalent). So, I would prefer sort of
unordered List, before using SortedList in this particular scenario.
piotr