Fog Creek Software
Discussion Board




Welcome! and rules

Joel on Software

What kind of collection am I looking for?

Working in VB .NET; I have a group of objects that I want to put in a collection.

On the one hand, they have keys, so I was thinking to put them in a Hashtable or DictionaryBase.

On the other hand, I want to be able to sort them like you can do with an ArrayList.  (They all implement a custom IComparable.)  So I was thinking SortedList, but that sorts by the keys, not by the objects.

Am I overlooking some collection class that has keys and objects but sorts by the objects?  Or if not, what's the best way to roll my own?

(The other thing that occurs to me is that since they're both Object type anyway, I could just reverse the keys and objects in the SortedList, perhaps through a wrapper class, but that sort of makes me cringe...)

Kyralessa
Wednesday, January 05, 2005

Maybe try a hand-rolled collection class inheriting from CollectionBase or ReadOnlyCollectionBase?

If you have a FooCollection that inherits from ReadOnlyCollectionBase, you can use a key indexor like:

public Foo this[string fooKey]
{
    get
    { 
        foreach(Foo foo in InnerList)
        {
            if(foo.Key == fooKey) { return foo; }
        }

        throw new System.IndexOutOfRangeException();
    }
}

...and you can sort like:

Foo[] foos = (Foo[])InnerList.ToArray(typeof(Foo));
Array.Sort(foos);
InnerList.Clear();
foreach(Foo foo in foos)
{
    InnerList.Add(foo);
}

smallbiz
Wednesday, January 05, 2005

sorry for the c#...I just noticed you said VB.NET...convert where applicable  :-)

smallbiz
Wednesday, January 05, 2005

That seems kind of inefficient, though.  Especially the Key part; surely the point of using a Hashtable or Dictionary (which contains a Hashtable) is that it doesn't have to do a linear search for keys?

Kyralessa
Wednesday, January 05, 2005

Why not use BOTH?

Let the Hastable mantain references to the objects that are at the same time stored in order in a SortedList.

Need access by key? access through the Hashtable. Need to iterate over the items in order? Use the SortedList.

You could wrap both structures in your own collection that takes the work of maintain them in synch.

.NET Developer
Wednesday, January 05, 2005

Yeah, it is a bit inefficient if you're going to have collections of hundreds of items.  I've used that technique in apps where the typical return is 1-50 items in a collection and it works pretty well.

If you want to experiment the ReadOnlyCollectionBase.InnerList is an ArrayList so you might be able to use .Contains or the indexor of the arraylist (along with a hashtable holding the Foo name and an arraylist index pointer) to get objects more quickly.

smallbiz
Wednesday, January 05, 2005

I tried today designing a wrapper class for a sort of reversed SortedList, switching Keys for Values and vice versa, so that the Values would stay sorted instead of the keys.  It was an interesting exercise but it started to make my head hurt after a while, trying to remember to put the key in the value and the value in the key, and it seemed like a very clumsy solution.

Later I hit on something else.  I think it was using DictionaryBase.  My problem is twofold: I want to get out a sorted list of objects (based on their own comparers) and I want the enumerator (i.e. For Each) to use that sorted list.

DictionaryBase returns an IDictionaryEnumerator instead of IEnumerator.  So I did this:

Public Shadows Function GetEnumerator() As IEnumerator
    Dim aList As New ArrayList(Me.Dictionary.Values)
    aList.Sort()
    Return aList.GetEnumerator
End Function

The Values property is read-only, I believe, but I should still be able to manipulate the objects since they're reference types.  But other than the fact that using Shadows is kind of ugly, I wonder if there are any other pitfalls in doing it this way...

Kyralessa
Thursday, January 06, 2005

"Yeah, it is a bit inefficient if you're going to have collections of hundreds of items."

I'd like to challenge this notion.

Hundreds of items in a hashtable means hundreds of references to existing items. The size of the hashtable will be, give or take, 2 * sizeof(IntPtr) * collectionSize. You're talking about 8 bytes. If you had hundreds of items in the collection, you could be talking about a whopping few kilobytes of RAM.

Brad Wilson (dotnetguy.techieswithcats.com)
Thursday, January 06, 2005

I agree with you that it doesn't take up a lot of memory but the inefficiency that we're referring to is having to spin through (potentially) each object in the InnerList using a foreach loop and returning the object on a name match.

Or am I misunderstanding your argument?

smallbiz
Thursday, January 06, 2005

"Yeah, it is a bit inefficient if you're going to have collections of hundreds of items."

I don't know if you were refering to my suggestion of using both a Hashtable and a SortedList.

As Brad said, you might really considering measuring first to really know if this is as inneficient as you suppose, as we all know that having two collections does NOT mean having two copies of the items, they are just two data structures around the same item set.

I don't think having two sets of references instead of just one means a lot of memory wasted. In fact, the code would be much simpler (you wouldn't need to do your own collection storing and sorting code) and that would be a great advantage, without mentioning the low coding time.

.NET Developer
Thursday, January 06, 2005

I had a similar requirement so I created a class that had two things in it; an arraylist (for the keys) and a hashtable (for the data).

I can sort the keys (arraylist) how I like and then extract in arraylist order by reading the key from the arraylist and then using the key to access the hashtable.

The class encapsulates the arraylist/hashtable so all this is invisible to the user. Also supports enumeration.

I thought this would be inefficient but running it adding lots of data, sorting keys and retrieving in key order works in the magnitude of millions of retrievals a second.

gwyn
Saturday, January 15, 2005

*  Recent Topics

*  Fog Creek Home