Best implementation for Key Value Pair Data Structure?

Question

So I've been poking around with C# a bit lately, and all the Generic Collections have me a little confused. Say I wanted to represent a data structure where the head of a tree was a key value pair, and then there is one optional list of key value pairs below that (but no more levels than these). Would this be suitable?

public class TokenTree
{
    public TokenTree()
    {
        /* I must admit to not fully understanding this,
         * I got it from msdn. As far as I can tell, IDictionary is an
         * interface, and Dictionary is the default implementation of
         * that interface, right?
         */
        SubPairs = new Dictionary<string, string>();
    }

    public string Key;
    public string Value;
    public IDictionary<string, string> SubPairs;
}

It's only really a simple shunt for passing around data.

Answer 1

There is an actual Data Type called KeyValuePair, use like this

KeyValuePair<string, string> myKeyValuePair = new KeyValuePair<string,string>("defaultkey", "defaultvalue");

Answer 2

One possible thing you could do is use the Dictionary object straight out of the box and then just extend it with your own modifications:

public class TokenTree : Dictionary<string, string>
{
    public IDictionary<string, string> SubPairs;
}

This gives you the advantage of not having to enforce the rules of IDictionary for your Key (e.g., key uniqueness, etc).

And yup you got the concept of the constructor right :)

Answer 3

I think what you might be after (as a literal implementation of your question), is:

public class TokenTree
{
    public TokenTree()
    {
        tree = new Dictionary<string, IDictionary<string,string>>();
    }

    IDictionary<string, IDictionary<string, string>> tree; 
}

You did actually say a "list" of key-values in your question, so you might want to swap the inner IDictionary with a:

IList<KeyValuePair<string, string>>

Answer 4

There is a KeyValuePair built-in type. As a matter of fact, this is what the IDictionary is giving you access to when you iterate in it.

Also, this structure is hardly a tree, finding a more representative name might be a good exercise.

Answer 5

Just one thing to add to this (although I do think you have already had your question answered by others). In the interests of extensibility (since we all know it will happen at some point) you may want to check out the Composite Pattern This is ideal for working with "Tree-Like Structures"..

Like I said, I know you are only expecting one sub-level, but this could really be useful for you if you later need to extend ^_^

Answer 6

@Jay Mooney: A generic Dictionary class in .NET is actually a hash table, just with fixed types.

The code you've shown shouldn't convince anyone to use Hashtable instead of Dictionary, since both code pieces can be used for both types.

For hashtable:

foreach(object key in h.keys)
{
     string keyAsString = key.ToString(); // btw, this is unnecessary
     string valAsString = h[key].ToString();

     System.Diagnostics.Debug.WriteLine(keyAsString + " " + valAsString);
}

For dictionary:

foreach(string key in d.keys)
{
     string valAsString = d[key].ToString();

     System.Diagnostics.Debug.WriteLine(key + " " + valAsString);
}

And just the same for the other one with KeyValuePair, just use the non-generic version for Hashtable, and the generic version for Dictionary.

So it's just as easy both ways, but Hashtable uses Object for both key and value, which means you will box all value types, and you don't have type safety, and Dictionary uses generic types and is thus better.

Answer 7

Dictionary Class is exactly what you want, correct.

You can declare the field directly as Dictionary, instead of IDictionary, but that's up to you.

Answer 8

Use something like this:

class Tree < T > : Dictionary < T, IList< Tree < T > > >  
{  
}  

It's ugly, but I think it will give you what you want. Too bad KeyValuePair is sealed.