is this iterator correct?

[emma_middlebrook]

Hi

I know there's a SortedDictionary in C# 2.0 but I was just converting
my existing implementation of SortedHashtable (which just wraps a
Hashtable and provides an enumerator) to use iterators as an
experiment.

The old version had the usual IEnumerator stuff and, in Current,
returned:

new DictionaryEntry(_sortedKeys[_position],
_hashTable[_sortedKeys[_position]]);

_sortedKeys is an ArrayList of the sorted hashtable's keys, set up in
the constructor of the enumerator.

Can I use the following in my SortedHashtable and it will be 'expanded
out' by the compiler to a proper implementation OK?

public IEnumerator GetEnumerator()
{
ArrayList sortedKeys = new ArrayList(_hashTable.Keys);
sortedKeys.Sort();

foreach (object o in sortedKeys)
{
yield return new DictionaryEntry(o, _hashTable[o]);
}
}

Cheers

Emma

 

[Barry Kelly]

Can I use the following in my SortedHashtable and it will be 'expanded
out' by the compiler to a proper implementation OK?

public IEnumerator GetEnumerator()
{
ArrayList sortedKeys = new ArrayList(_hashTable.Keys);
sortedKeys.Sort();

foreach (object o in sortedKeys)
{
yield return new DictionaryEntry(o, _hashTable[o]);
}
}

That looks like it should work, although it won't necessarily be as fast
as people who are foreach-ing over the collection might expect it to be,
since it does a sort each time. I'm presuming this old collection wasn't
strongly typed, and that's why you're using ArrayList and not returning
IEnumerator<T>.

-- Barry

 

[emma_middlebrook]

Can I use the following in my SortedHashtable and it will be 'expanded
out' by the compiler to a proper implementation OK?

public IEnumerator GetEnumerator()
{
ArrayList sortedKeys = new ArrayList(_hashTable.Keys);
sortedKeys.Sort();

foreach (object o in sortedKeys)
{
yield return new DictionaryEntry(o, _hashTable[o]);
}
}

That looks like it should work, although it won't necessarily be as fast
as people who are foreach-ing over the collection might expect it to be,
since it does a sort each time. I'm presuming this old collection wasn't
strongly typed, and that's why you're using ArrayList and not returning
IEnumerator<T>.

Yep, it's an old collection, just having a play as I'd like to convince
someone that we should move to C# 2.0.

Regarding the speed, I thought sorting at the point of enumerating
would be the best idea. The other alternative is to sort the ArrayList
of the keys every time something is added/removed to the actual
Hashtable but I thought that would be even worse. I suppose it depends
on the usage: i.e. the ratio of insertion/deletion vs enumeration
doesn't it?

Cheers

Emma

 

[Greg Young]

Another possibility would be to store the data as a sorted hashlist.

This may be worth looking at for you.


Cheers,

Greg

Can I use the following in my SortedHashtable and it will be 'expanded
out' by the compiler to a proper implementation OK?

public IEnumerator GetEnumerator()
{
ArrayList sortedKeys = new ArrayList(_hashTable.Keys);
sortedKeys.Sort();

foreach (object o in sortedKeys)
{
yield return new DictionaryEntry(o, _hashTable[o]);
}
}

That looks like it should work, although it won't necessarily be as fast
as people who are foreach-ing over the collection might expect it to be,
since it does a sort each time. I'm presuming this old collection wasn't
strongly typed, and that's why you're using ArrayList and not returning
IEnumerator<T>.

Yep, it's an old collection, just having a play as I'd like to convince
someone that we should move to C# 2.0.

Regarding the speed, I thought sorting at the point of enumerating
would be the best idea. The other alternative is to sort the ArrayList
of the keys every time something is added/removed to the actual
Hashtable but I thought that would be even worse. I suppose it depends
on the usage: i.e. the ratio of insertion/deletion vs enumeration
doesn't it?

Cheers

Emma

 

[Barry Kelly]

Regarding the speed, I thought sorting at the point of enumerating
would be the best idea. The other alternative is to sort the ArrayList
of the keys every time something is added/removed to the actual
Hashtable

You could insert in the right location rather than do a full sort (O(n)
because it's insertion into an array, versus O(n log n)), but it would
have O(n^2) time performance for iterated insertions, which would lead
to adding BeginUpdate/EndUpdate methods when required.

Of course, this is put together using relatively bulky primitives
supplied by the (1.1) framework. For a good sorted dictionary, you'd use
a balanced binary tree or heap, and probably do away with the hash
lookup altogether, since log n grows very slowly. And of course, that's
what SortedDictionary does.

but I thought that would be even worse. I suppose it depends
on the usage: i.e. the ratio of insertion/deletion vs enumeration
doesn't it?

Sure does, swings and roundabouts.

-- Barry

 

[Jon Skeet [C# MVP]]

Can I use the following in my SortedHashtable and it will be 'expanded
out' by the compiler to a proper implementation OK?

public IEnumerator GetEnumerator()
{
ArrayList sortedKeys = new ArrayList(_hashTable.Keys);
sortedKeys.Sort();

foreach (object o in sortedKeys)
{
yield return new DictionaryEntry(o, _hashTable[o]);
}
}

That looks like it should work, although it won't necessarily be as fast
as people who are foreach-ing over the collection might expect it to be,
since it does a sort each time. I'm presuming this old collection wasn't
strongly typed, and that's why you're using ArrayList and not returning
IEnumerator<T>.

It does the sort each time you fetch the enumerator, which is once per
time you go through the whole list. It's not sorting the list on every
iteration of the enumerator, which is how I read your comment.

 

[Barry Kelly]

It does the sort each time you fetch the enumerator, which is once per
time you go through the whole list. It's not sorting the list on every
iteration of the enumerator, which is how I read your comment.

Once per foreach, I could have been clearer, yes; although I never
mentioned iteration, only foreach-ing, so hopefully the implied context
is the act of multiple "foreach"s. English isn't as unambiguous as we'd
like it to be, of course.

One could declare a semantic rule:

For the pattern "when <n>ing, it does <x> each time", infer "when
<n>ing, it does <x> each time it <n>s".

Using that semantic rule with the above construction:

when "foreach"ing, it does a sort each time it "foreach"s

.... the key point being that the atomicity of 'n' is a foreach, and not
an iteration. Unfortunately, programming style analysis is a poor tool
for natural language parsing...

-- Barry