I am looking for something like a tree. We are constantly inserting into an already sorted collection. We would like access to the minimum and maximum value. We don't need any keys, just the value. I couldn't find any tree structures from .Net and I couldn't see any thing else that looked like what I am looking for.
views:
51answers:
1
+3
A:
In .NET 4.0 there's SortedSet - it looks like that would do what you want, and it has Min and Max properties.
.NET 3.5 has HashSet, but that only deals with equality rather than ordering.
Jon Skeet
2010-05-17 08:25:23
Hi Jon. Unfortunately not on .Net 4.0 yet. Plans are to get there soon but in the mean time we have to think of something else. I had already come across the HashSet but as you mentioned it doesn't support ordering. I had a thought, but I am not sure how much of a bad idea it is. What if we used a SortedList and stored the value as the key and stored nulls as the values? I can't think of any reason why this is a bad idea other than it just feels wrong.
uriDium
2010-05-17 09:58:24
@uriDium: You might want to use `SortedDictionary` instead of `SortedList` - basically `SortedDictionary` *is* a tree structure, so it's more efficient for random insertions, but less efficient if you're adding sorted items. See the docs for more detailed comparisons. You might want to wrap this in your own type, so you can move to `SortedSet` smoothly when you start using .NET 4. Basically it should work, but as you say it's ugly.
Jon Skeet
2010-05-17 10:05:24
@Jon: Thanks for your comments. We have done testing with both collections already and it appears sortedlist slightly out performs sorteddictionary for our scenario and the shape of our data. Definitely feels ugly to abuse a collection. Feels like I should perhaps implement our own tree. Shouldn't be too hard. Once again thanks for the comments.
uriDium
2010-05-17 10:35:33