Want a key value collection that maintains ordering

[illegal.prime]

Hi all, is there a key value collection in .Net that maintains the
ordering in which I add items.

I'm finding that I'm creating a number of classes that contain a name
and then some object. I would prefer just to use some collection that
maintains the ordering in which I add things (like ArrayList), but that
maps a key to a value.

I thought NameValueCollec tion was the right one - but it doesn't
guarantee ordering.

If it doesn't exist, why not? If it doesn't what is the "right" way to
build it? Just have wrap your class around an instance of ArrayList
and have some internal class that takes the key given in the Add method
and instantiates this generic class with two members (a string key and
an object value), then add that to the internal ArrayList?

Thanks,
Novice

[illegal.prime]

I can't use .Net 2 yet... I'm stuck with my current version of .Net -
but thanks for the suggestion none the less.

Novice

[Bruce Wood]

But the OP asked that the entries be maintained in their original
order, not in key order. That's why I didn't suggest SortedList.

[Bruce Wood]

Why not add a Hashtable to that and avoid the iteration over the
ArrayList looking for the item? A linear search is terribly slow.

[Bruce Wood]

> What if you add something with the same key twice? It will show up in

the hashtable just once but in the ArrayList twice. That is probably
not what he's looking for.

There's a simple solution to that:

public void Add(object key, object item)
{
object existingItem = this._hash[key];
if (existingItem != null)
{
this._array.Rem ove(existingIte m);
}
this._hash[key] = item;
this._array.Add (item);
}

Much better than doing a linear search every time you add an item.

If the OP wants instead a collection that permits duplicates (two items
with the same key) then it's no longer clear what the indexer should
return.

[Brian Gideon]

Novice,

Bruce's idea is really the best one IMO. Here's a link to an
implementation.

<http://www.codeproject .com/csharp/keyedlist.asp#x x701821xx>

Brian

il***********@g mail.com wrote:

Hi all, is there a key value collection in .Net that maintains the
ordering in which I add items.

I'm finding that I'm creating a number of classes that contain a name
and then some object. I would prefer just to use some collection that
maintains the ordering in which I add things (like ArrayList), but that
maps a key to a value.

I thought NameValueCollec tion was the right one - but it doesn't
guarantee ordering.

If it doesn't exist, why not? If it doesn't what is the "right" way to
build it? Just have wrap your class around an instance of ArrayList
and have some internal class that takes the key given in the Add method
and instantiates this generic class with two members (a string key and
an object value), then add that to the internal ArrayList?

Thanks,
Novice

[illegal.prime]

So in case anyone is interested I did something even more simple than
Bruce's idea. I.E. I just wrapped ArrayList. The reason I don't also
use Hashtable is two fold:
1. My Collection also needs to be capable of containing other instances
of itself - i.e. I need a collection that can contain regular
key/value pairs, but any of those values could potentially be another
instance of itself. Therefore, I may end up with nested keys that are
identical - hence hashtable wouldn't work - unless I also embed
Hashtables in Hashtables - but that defeats the purpose of using
Hashtable for searching
2. Really just restating the last bit of point 1 - that is, a Hashtable
can't search on nested instances of itself - i.e. if I add a Hashtable
Object like this:
Hashtable hashtable = getHashtable1() ;
Hashtable hashtable2 = getHashtable2() ;
hashtable.Add(" blah", hashtable2);

Now searching on hashtable2 won't be done.

However, after writing all that - perhaps I could come up with a clever
naming system, whereby nested instances get characters in them much
like folders/directories in the various OS'.

So I could use some illegal character for my names as a separator and
then search using that...

Hmm... that could work,
Novice

[Michael D. Ober]

That's simple to solve. Use the data as the key. If you want to keep them
in the original order, any of the array list and collection objects will do
this by default - it's the way they're implemented.

Mike Ober.

"Bruce Wood" <br*******@cana da.com> wrote in message
news:11******** **************@ g10g2000cwb.goo glegroups.com.. .

But the OP asked that the entries be maintained in their original
order, not in key order. That's why I didn't suggest SortedList.

[Helge Jensen]

jeremiah johnson wrote:

Bruce Wood wrote: I just whipped something up in Java. Its untested, unsynchronized,

Java have a LinkedHashMap (or something like that) which does exactly
what OP want's.

The "good" (TM :) solution is to store double-linked-lists with
insertion-order and let the values in the hash contain references to
their linked-list representation.

This allows O(1) insert,update and remove, as well as ordered traversal
(forward and backward) and is exactly what the correspoding JAVA class does.

--
Helge

[Helge Jensen]

Michael D. Ober wrote:

That's simple to solve. Use the data as the key. If you want to keep them
in the original order, any of the array list and collection objects will do
this by default - it's the way they're implemented.

IDictionary have no ordering, which was what OP wanted.

You *could* embed the ordering into the keys, and use SortedList, but I
don't like the idea of embedding collection-containment info into the
contained objects. For one thing each object can only be contained in
one such list.

A better alternative is to do linked-list-hashtables.

--
Helge

[Helge Jensen]

il***********@g mail.com wrote:

So in case anyone is interested I did something even more simple than
Bruce's idea. I.E. I just wrapped ArrayList. The reason I don't also
use Hashtable is two fold:
So you've chosen linear lookup-time.
1. My Collection also needs to be capable of containing other instances
of itself - i.e. I need a collection that can contain regular
key/value pairs, but any of those values could potentially be another
instance of itself. Therefore, I may end up with nested keys that are
identical - hence hashtable wouldn't work - unless I also embed
*Nested* identical keys shouldn't be a problem. They are contained in
separate data-structures.
Hashtables in Hashtables - but that defeats the purpose of using
Hashtable for searching
Well,... atleast in multiple layers. Why don't you just have
IDictionary'es, and then use a hashtable for the "big" ones and
something else for the "smaller" ones?
2. Really just restating the last bit of point 1 - that is, a Hashtable
can't search on nested instances of itself - i.e. if I add a Hashtable
Object like this:
Hashtable hashtable = getHashtable1() ;
Hashtable hashtable2 = getHashtable2() ;
hashtable.Add(" blah", hashtable2);

Now searching on hashtable2 won't be done.
If you have a flat data-structure encoded in a recursive data-structure
(for performance) the recursion shouldn't be visible to the user.

If you have an inherently recursive data-structure you should probably
show that to the user, and do recursive lookup, and everything would be
fine.

What exactly is the type of your keys? which type are they? single:
"foo", or tupled: ("x", "y"), or list-like: ["x", "y", ...] ?
However, after writing all that - perhaps I could come up with a clever
naming system, whereby nested instances get characters in them much
like folders/directories in the various OS'.
Thats called linearization. Perhaps you *are* having a recursive
data-structure and you're just not doing lookup in a way corresponding
to that?

It sounds a lot like a tree with indexed children to me :)
So I could use some illegal character for my names as a separator and
then search using that...

Hmm... that could work,

Watch out, along that bumpy road lies all the dangers of linearization:

- escaping
- delinearization
- parsing, and error-handling of unparseable data
- formulation of searches

If your data *is* recursively structured, you are probably best off
storing the recursively and doing recursive lookups:

void object lookup(params object[] keys) {
IDictionary d = TopDict;
for ( int i = 0; i < keys.Length - 1; ++i )
d = (IDictionary)d[keys[i]];
return d[keys[keys.Length - 1]];
}

dict.lookup("fo o", "foo", "baz");
--
Helge