tags:

views:

472

answers:

6

Hi

I'm looking for a sorted data structure, that will be similar to the STL set(T). I found SortedList, but it requires (key, val), I'm looking for something like List(string) - only sorted.

I found on the web Spring.Collections, but my framework does not recognize it.

Is there a simple SortedSet I could use in the regular basic framework?

Thanks, Gal

+7  A: 

You can do this with A System.Collections.Generic.Dictionary. Here's a good article: Dictionarys and sorting

Edit: The SortedDictionary seems even better.

Stormenet
Thanks. But this is exactly what i was trying to avoid: having <key, val>. I'm looking for a sorted data structure with only value, like List<string>, but I guess there isn't any, so I'll use your solution. :-)
Gal Goldman
+1  A: 

Also List<T> can be sorted. It is not sorted by default, but you can sort it, even with custom sorting algorithms if you so wish.

Nikos Steiakakis
A: 

How about using a List<> and calling the Sort method?

Not an extension but try this

public class SortedList<T>: List<T>
{
    public SortedList(): base()
    {
    }
    public SortedList(IEnumerable<T> collection): base(collection)
    {
    }
    public SortedList(int capacity)
        : base(capacity)
    {
    }

    public void AddSort(T item)
    {
        base.Add(item);
        this.Sort();
    }
}

It's only a starting point, but adds a new method AddSort.

An extension method would be used to alter the List<>.Add method and call the sort on the end of it.

Using extension method

Place the following in a namespace accessible by your code:

public static class ListExtension
{
    public static void AddSort<T>(this List<T> list, T item)
    {
        list.Add(item);
        list.Sort();
    }
}

You can the use code such as:

List<int> newList = List<int>();
newList.AddSort(6);
newList.AddSort(4);
newList.AddSort(3);

And the values will be:

newList[0] == 3 newList[1] == 4 newList[3] == 6

You can also just use newList.Add and the list is then sorted when you call newList.AddSort

ChrisBD
This has a complexity penalty, it would be quicker to use a sorted data structure that inserts the values in a sorted way to begin with.
Gal Goldman
Could you not use an extension method to encompass this behaviour?
ChrisBD
Well, using a sorted data structure that inserts the values in a sorted way to begin with is one way - like SortedDictionary, but then you have to use <keys, values>, and I was looking for something simpler with only <values>...
Gal Goldman
@Gal: have added a new class in my answer based on List<> it's very rough and ready, but does what you want. Ideally I was looking at an extension to the List<>.Add() method which would be my preferred route.
ChrisBD
@Gal just added an example entension method to the List<> class for you.
ChrisBD
@Chris, Thanks for your efforts, but your solution is N*N*Log(N), because If you have N AddSort() calls, for each call you do Sort() in N*Log(N). Building a sorted data structure shouldn't take more than N*Log(N).
Gal Goldman
A: 

There is a System.Collections.SortedList or System.Collections.Generic.SortedList which is always sorted. Or you can use the Array.Sort method to sort ar defined moments in time.

florin
+1  A: 

There's nothing built into the framework other than SortedDictionary<K,V> and SortedList<K,V>.

The C5 Collections library has several sorted collections. One of the following should do the trick, depending on your exact requirements: SortedArray<T>, TreeBag<T> or TreeSet<T>.

There's also Power Collections, which provides OrderedBag<T> and OrderedSet<T> collections.

LukeH
+1  A: 

A SortedSet < T > introduced in .NET 4.0 is what you are looking for, see MSDN here

vzczc