|
|
You're in the
c#
group:Want a key value collection that maintains ordering
c#:
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
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 [.NET/C# MVP]" <mvp@spam.guard.caspershouse.com> wrote in message news:%23S3q%23JlbGHA.1320@TK2MSFTNGP04.phx.gbl... [quoted text, click to view] > 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] > - mvp@spam.guard.caspershouse.com > > <illegal.prime@gmail.com> wrote in message > news:1146612090.419398.121710@j73g2000cwa.googlegroups.com... >> 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 >> > >
[quoted text, click to view]
Bruce Wood wrote: > 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. > 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 }); } }
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
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] - mvp@spam.guard.caspershouse.com [quoted text, click to view] <illegal.prime@gmail.com> wrote in message news:1146612090.419398.121710@j73g2000cwa.googlegroups.com... > 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 >
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. [quoted text, click to view] "MSDN" <sql_agentman@hotmail.com> wrote in message news:ehgDp0lbGHA.3336@TK2MSFTNGP04.phx.gbl... > 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 [.NET/C# MVP]" <mvp@spam.guard.caspershouse.com> wrote in > message news:%23S3q%23JlbGHA.1320@TK2MSFTNGP04.phx.gbl... > > 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] > > - mvp@spam.guard.caspershouse.com > > > > <illegal.prime@gmail.com> wrote in message > > news:1146612090.419398.121710@j73g2000cwa.googlegroups.com... > >> 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 > >> > > > > > >
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.
[quoted text, click to view]
> 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.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.
Novice,
Bruce's idea is really the best one IMO. Here's a link to an implementation. <http://www.codeproject.com/csharp/keyedlist.asp#xx701821xx> Brian [quoted text, click to view] illegal.prime@gmail.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 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
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
[quoted text, click to view] 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. --
[quoted text, click to view] 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. --
[quoted text, click to view] illegal.prime@gmail.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. [quoted text, click to view] > 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. [quoted text, click to view] > 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? [quoted text, click to view] > 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", ...] ? [quoted text, click to view] > 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 :) [quoted text, click to view] > 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("foo", "foo", "baz"); --
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. [quoted text, click to view] "Bruce Wood" <brucewood@canada.com> wrote in message news:1146681021.895538.145330@g10g2000cwb.googlegroups.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. > >
Going back to your original post...
[quoted text, click to view] > is there a key value collection in .Net that maintains the > ordering in which I add items. > 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. So... this isn't exactly what you want after all. What you want is something that maps a _multi-part_ key onto a value, or perhaps stores values in a hierarchical structure but also in insertion order? Your solution isn't "simpler" than mine... rather, it solves a different problem. Since your original post doesn't completely state your problem, could you restate the problem so that we understand, completely, what it is that you need to do?
I seem to have offended you - sorry for that.
I have always wanted the same thing, but you're right I could have provided more details on what I want. I still want a "key value collection in .Net that maintains the ordering in which I add items. 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." However, this key value collection also needs to be able to hold a hierarchy of collections. Therefore, the values need to be able to be traversed - since they values could themselves be key value collections. I have a working solution, if not an efficient one. I'm just surprised that short of getting .Net 2 there is no generic solution. Thanks, Novice
Don't worry. You didn't offend me. I was just pointing out that your
requirements seemed to have changed, in hopes of getting more details. Your solution may be efficient enough if there are few elements in your collection. If there are very many, though, you may want to implement Brian Gideon's class and then just use a hierarchy of them. I don't believe that there's a generic solution even in .NET 2.0 (unless I missed something in the conversation). Yours isn't a very common requirement: most people want either a straight hash or a _sorted_ list of items with quick access by key.
[quoted text, click to view] Bruce Wood wrote: > Your solution may be efficient enough if there are few elements in your > collection. If there are very many, though, you may want to implement > Brian Gideon's class and then just use a hierarchy of them. > I should give credit where credit is due. It isn't actually my class. Someone else wrote that article :)
Don't see what you're looking for? Try a search.
|
June 2003
July 2003
August 2003
September 2003
October 2003
November 2003
December 2003
January 2004
February 2004
March 2004
April 2004
May 2004
June 2004
July 2004
August 2004
September 2004
October 2004
November 2004
December 2004
January 2005
February 2005
March 2005
April 2005
May 2005
June 2005
July 2005
August 2005
September 2005
October 2005
November 2005
December 2005
January 2006
February 2006
March 2006
April 2006
May 2006
June 2006
July 2006
August 2006
September 2006
October 2006
November 2006
December 2006
January 2007
February 2007
March 2007
April 2007
May 2007
June 2007
July 2007
August 2007
September 2007
October 2007
November 2007
December 2007
January 2008
February 2008
March 2008
April 2008
| home · blog · groups | Questions? Comments? Contact the dn |