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 6 2785 em**************@fastmail.fm wrote:
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
-- http://barrkel.blogspot.com/
Barry Kelly wrote:
em**************@fastmail.fm wrote:
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
Another possibility would be to store the data as a sorted hashlist.
This may be worth looking at for you.
Cheers,
Greg
<em**************@fastmail.fmwrote in message
news:11*********************@m73g2000cwd.googlegro ups.com...
Barry Kelly wrote:
>em**************@fastmail.fm wrote:
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 em**************@fastmail.fm wrote:
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
-- http://barrkel.blogspot.com/
Barry Kelly <ba***********@gmail.comwrote:
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.
--
Jon Skeet - <sk***@pobox.com> http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too
Jon Skeet [C# MVP] <sk***@pobox.comwrote:
Barry Kelly <ba***********@gmail.comwrote:
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.
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 <xeach time", infer "when
<n>ing, it does <xeach 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
-- http://barrkel.blogspot.com/ This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: greg |
last post by:
Hello all,
I havent used STL containers much, as I am used to MFC
containers/classes always
..The differences that I could see is iterators and algorithms.
The algorithms providing some basic...
|
by: CoolPint |
last post by:
If I were to design my own container and its iterators, I understand
that I need to provide both "iterator" and "const_iterator" so that
begin() and end() return appropriate ones depending on the...
|
by: uclamathguy |
last post by:
I am working on connected component analysis, but that is irrelevant. I
have a mapping containing ints as the keys and sets of ints as the
"values."
Given an integer, I need to iterate through...
|
by: Lorenzo Castelli |
last post by:
This is an old problem of mine.
Basically I have an abstract base class which represents a generic iterator
over a collection of elements, and various derived classes that implement
the...
|
by: shawnk |
last post by:
I searched the net to see if other developers have been looking for a
writable iterator in C#. I found much discussion and thus this post.
Currently (C# 2) you can not pass ref and out arguments...
|
by: Johan Pettersson |
last post by:
Hi,
I'm trying to "port" a project from VC++ 2003 to VC++ 2005 (Express
Edition). This project contains the following code on several places (It is
not exactly this code but a generalization of...
|
by: subramanian100in |
last post by:
Whenever we specify an iterator range to a container operation or an
std::algorithm, the first iterator should always be a valid iterator
ie it should point to some element in the respective...
|
by: subramanian100in |
last post by:
I am reading David Musser's "STL Tutorial and Reference Guide" Second
Edition.
In that book, on pages 68-69, definition has been given that "an
iterator can be mutable or constant depending on...
|
by: Luis Zarrabeitia |
last post by:
Hi there.
For most use cases I think about, the iterator protocol is more than enough.
However, on a few cases, I've needed some ugly hacks.
Ex 1:
a = iter() # assume you got the iterator...
|
by: Terry Reedy |
last post by:
Luis Zarrabeitia wrote:
Interesting observation. Iterators are intended for 'iterate through
once and discard' usages. To zip a long sequence with several short
sequences, either use...
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each...
| |