is there a type available for sorted list of items

[shrishjain]

Hi All,

I need a type where I can store my items in sorted order. And I want to
keep adding items to it, and want it to remain sorted. Is there any
type in .net which I can make use of.

I see there is SortedList<key, value> for hash tables, but could find
anything for a sorted list.

Currently I am using List<string> and whenever I add an item, I need to
call Sort() and it takes a long time - Order(nlogn). If the list is
already sorted, it will take just Order - logn. Does someone know if
there is a type where I can so such stuff.

Thanks,
Shrish

 

[Guillermo 'guille']

If access by an index is what you're looking for, with SortedList<key,
value> you can also access its elements by an index using the Values or Keys
properties.

--
Nos vemos.
Guillermo
--------------
Microsoft VB MVP desde 1997
Mentor Asociado de Solid Quality Learning Iberoamericana

Te recuerdo que puedes entrar en mi sitio desde:
http://www.elguille.info/ y http://www.mundoprogramacion.com/
Los foros en: http://foros.elguille.info/
Si buscas un buen plan de alojamiento:
http://www.elguille.info/hostings/ofertas_hosting_guille.htm

 

[Bruce Wood]

Well, SortedList _is_ a list, but you have to tell it how to sort...
that's what the key is for. If you never look things up by the key,
just maintain the sorted order, then you don't lose anything.

Another possibility is to write a "lazy sort" class: one that allows
you to add items to the list without sorting, but sorts whenever you
try to iterate over the list, for example. All you need to do is keep a
"dirty" flag. Whenever you add an item to the list, flag the list as
"dirty". Whenever you do some operation that would require the list to
be sorted, if it's "dirty" then sort it before returning the result,
otherwise just return the result.

 

[Branco Medeiros]

Hi All,

I need a type where I can store my items in sorted order. And I want to
keep adding items to it, and want it to remain sorted. Is there any
type in .net which I can make use of.

I see there is SortedList<key, value> for hash tables, but could find
anything for a sorted list.

Currently I am using List<string> and whenever I add an item, I need to
call Sort() and it takes a long time - Order(nlogn). If the list is
already sorted, it will take just Order - logn. Does someone know if
there is a type where I can so such stuff.

Note that the List<T> class has a BinarySearch method that will return
a positive or zero index for the item if it already exists in the list
or the one's complement of the position where the item should be, if
it's not in the list yet.

The list must be sorted for the BinarySearch method to work, but it's
quite fast to locate the item's position.

Therefore, instead of simply adding to the list, which would ruin the
sort order and require you to perform a explicit sort afterwards, you
could add the item at its sorted position by using BinarySearch to find
it for you (warning: untested VB code ahead!):

Dim Index As Integer = List.BinarySearch(Item)
If Index < 0 then List.InsertAt(Index Xor -1, Item)

And your list would be kept sorted...

Regards,

Branco.

 

[Bruce Wood]

That is very cool. I didn't know about that.

Here is the relevant documentation page:

http://msdn2.microsoft.com/en-us/library/w4e7fxsh(VS.80).aspx