Want a key value collection that maintains ordering

  • Thread starter Thread starter illegal.prime
  • Start date Start date
I

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 NameValueCollection 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
 
I would create a class that wraps an ArrayList and a Hashtable.
Whenever anything is added to your class, add it to both the ArrayList
and the Hashtable. When you want to return an iterator, return an
iterator into the ArrayList. When you want a lookup by key, look it up
in the Hashtable.
 
I was actually thinking of doing something like that originally since
it is all reference based, there would be minimal cost (memory) to do
something like that - i.e. to have the ArrayList and the Hashtable to
point to the various elements.

Does anyone know of any reason why I should just rip off the
implementation of PhoneNumberDictionary (that extends DictionaryBase)
from here:
http://www.codeproject.com/csharp/collection1.asp

I'm not doing a PhoneNumberDictionary, but it seems to provide what I
want in terms of allowing me to specify an arbitrary name and an
arbitrary object. And when I get them all, they will be returned in
the order I added them.

Does that sound right?

Thanks,
Novice
 
Crud!

I've tried using DictionaryBase, but the compiler gives me
DictionaryBase could not be found. I guess that means it is a .Net 2
class?

That sucks.
 
Never mind - looks like the executable wasn't getting regenerated or
something - fresh build and the compiler was okay with it.
 
Well, this doesn't work, it doesn't maintain the order in which I added
them when I iterate through it.

So I guess I will just do something like (not compileable code):
class DictionaryEntryCollection
{
private ArrayList mKeyValues;

public DictionaryEntryCollection()
{
mKeyValues = new ArrayList();
}

public void Add (object key, object value)
{
DictionaryEntry keyValue = new DictionaryEntry(key, value);
mKeyValues.Add(keyValue);
}

public DictionaryEntry[] GetKeyValueElements()
{
//iterate over all the elements in my arraylist
}
}

Sound right?

Thanks,
Novice
 
Bruce said:
I would create a class that wraps an ArrayList and a Hashtable.
Whenever anything is added to your class, add it to both the ArrayList
and the Hashtable. When you want to return an iterator, return an
iterator into the ArrayList. When you want a lookup by key, look it up
in the Hashtable.
Click to expand...

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.

I'd create a new collection that wrapped an ArrayList<Object[]> and
massage the add method to check for duplicates, while maintaining order.

I just whipped something up in Java. Its untested, unsynchronized,
probably slow, and the syntax is slightly different for C# (the for
loop). Here it is; it might help you, it might not.

public class HashList {

private ArrayList<Object[]> coll;

public HashList() {
coll = new ArrayList<Object[]>();
}

public void add(Object key, Object value) {
boolean alreadyAdded = false;

for (Object[] s : coll) {
if (s[0] == key) {
int me = coll.indexOf(s);
coll.remove(me);
coll.add(me, s);
alreadyAdded = true;
}
}

if (!alreadyAdded) {
coll.add(new Object[] { key, value });
}
}

}
 
Novice,

You can just use the SortedList<TKey, TValue> generic class. It will
allow you to perform lookups, and order the list as well.

Hope this helps.
 
Nicholas,

new to Generics, is SortedList already generic?

Why can I ! say SortedList<string,string> ??? Throws Error


if (!Page.IsPostBack)
{
AlwaysSortedList = new SortedList();
Session.Add("ASL",AlwaysSortedList);
}

in button handler....

((SortedList)Session["ASL"]).Add(TextBox1.Text,TextBox1.Text);
DropDownList1.DataSource = ((SortedList)Session["ASL"]); //AlwaysSortedList;
DropDownList1.DataTextField = "key";
DropDownList1.DataValueField = "value";
DropDownList1.DataBind();



Nicholas Paldino said:
Novice,

You can just use the SortedList<TKey, TValue> generic class. It will
allow you to perform lookups, and order the list as well.

Hope this helps.


--
- Nicholas Paldino [.NET/C# MVP]
- (e-mail address removed)

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 NameValueCollection 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
Click to expand...
Click to expand...
 
Yes. In VB 2005, you would use

dim AlwaysSortedList as new SortedList(of String, String)
AlwaysSortedList.add("Key1", "This is Key1")

debug.print(AlwaysSortedList("Key1") displays "This is Key1" in the
Immediate window.

Mike Ober.

MSDN said:
Nicholas,

new to Generics, is SortedList already generic?

Why can I ! say SortedList<string,string> ??? Throws Error


if (!Page.IsPostBack)
{
AlwaysSortedList = new SortedList();
Session.Add("ASL",AlwaysSortedList);
}

in button handler....

((SortedList)Session["ASL"]).Add(TextBox1.Text,TextBox1.Text);
DropDownList1.DataSource = ((SortedList)Session["ASL"]); //AlwaysSortedList;
DropDownList1.DataTextField = "key";
DropDownList1.DataValueField = "value";
DropDownList1.DataBind();



message news:%23S3q%[email protected]...
Novice,

You can just use the SortedList<TKey, TValue> generic class. It will
allow you to perform lookups, and order the list as well.

Hope this helps.


--
- Nicholas Paldino [.NET/C# MVP]
- (e-mail address removed)

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 NameValueCollection 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
Click to expand...
Click to expand...
Click to expand...
 
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
 
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.
 
Why not add a Hashtable to that and avoid the iteration over the
ArrayList looking for the item? A linear search is terribly slow.
 
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.
Click to expand...

There's a simple solution to that:

public void Add(object key, object item)
{
object existingItem = this._hash[key];
if (existingItem != null)
{
this._array.Remove(existingItem);
}
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.
 
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
 
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.
 
jeremiah said:
Bruce Wood wrote:
Click to expand...
I just whipped something up in Java. Its untested, unsynchronized,
Click to expand...

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.
 
Michael said:
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.
Click to expand...

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.
 
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:
Click to expand...

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
Click to expand...

*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
Click to expand...

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.
Click to expand...

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'.
Click to expand...

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,
Click to expand...

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];
return d[keys[keys.Length - 1]];
}

dict.lookup("foo", "foo", "baz");
 
Back
Top