Nested Dictionary collection in .NET

Question

The .NET Dictionary<TKey, TValue> object allows assignment of key/values like so:

Dictionary<string, string> dict = new Dictionary<string, string>();
dict["1"] = "foo";
dict["2"] = "bar";

but I cannot use a Dictionary like so:

Dictionary<string, string> dict = new Dictionary<string, string>();
dict["F1"]["F2"]["F3"] = "foo";
dict["2"]["X"] = "bar";

Is there a collection in .NET which allows me to nest [], or would I have to create my own?

If I have to create my own, how would I do this?

EDIT:

It would also be useful if I could have implementations which expect unique keys, like so:

dict["F1"]["F2"]["F3"] = "foo";
dict["F1"]["F2"]["F3"] = "bar"; //result is "bar" because "foo" was overridden

and an implementation where a key can be used more than once

dict["F1"]["F2"]["F3"] = "foo";
dict["F1"]["F2"]["F3"] = "bar"; //result can be "foo" and "bar"

Is this possible?

EDIT (as per Jon Skeet's question):

I want to use the structure like so (as a very rough example):

json["data"]["request"]["name"] = "username";
json["data"]["request"]["pass"] = "password";

resolves to

{ data: { request: { name: "username", pass: "password" } } }

and equally there would be an equivalent for XML etc.

Solution 1

Having a requirement for arbitrarily long nesting, I have come up with the following solution, which as far as I can see, doesn't break, according to my test:

public class NestedDictionary<K, V> : Dictionary<K, NestedDictionary<K, V>>
    {
        public V Value { set; get; }

        public new NestedDictionary<K, V> this[K key]
        {
            set { base[key] = value; }

            get
            {
                if (!base.Keys.Contains<K>(key))
                {
                    base[key] = new NestedDictionary<K, V>();
                }
                return base[key];
            }
        }
    }

TEST:

NestedDictionary<string, string> dict = new NestedDictionary<string, string>();
dict["one"].Value = "Nest level 1";
dict["one"]["two"]["three"].Value = "Nest level 3";
dict["FieldA"]["FieldB"].Value = "Hello World";

Console.WriteLine(dict["one"].Value);
Console.WriteLine(dict["one"]["two"]["three"].Value);
Console.WriteLine(dict["FieldA"]["FieldB"].Value);

Solution 2

You can do this using the standard Dictionary, you just have to declare the nesting:

Dictionary<string, Dictionary<string, string>> dict = ...
string test = dict["first"]["second"]

Dictionary<string, Dictionary<string, Dictionary<string, string>>> dict = ...
string test = dict["first"]["second"]["third"]

etc

Solution 3

The original Dictionary COM object which was created to work with vb6 would respond to an attempt to access a non-existent item by creating a new item of type Dictionary with the corresponding name. This approach allows something to be stored to MyDict["Foo"]["Bar"] without having to first create MyDict["Foo"]. The problem with this approach is that while one would want to add "Foo" to MyDict when performing a write to MyDict["Foo"]["Bar"], one would rather not create such an item if one was attempting to e.g. evaluate MyDict["Foo"]["Bar"].ValueOrDefault(someDefaultValue).

I've used such collections, since they can be handy for modeling certain things (conceptually they're a lot like XML documents). One workable approach is to declare that dictionaries which contain nothing but other dictionaries are considered semantically as non-entities which may be removed at any opportunity. When implicitly adding a subcollection, set a flag in the item to which it's added it indicating that it should be checked for items that may be deleted (or keep a counter of how many such items may exist). Then with some reasonable frequency, scan through the dictionaries and remove such "dead" items.

An alternative approach is to have the indexer from the dictionary not return an actual item, but instead return an "ephemeral indexer" type, which keeps a reference to the parent object and has internal methods GetNestedForReading, SetNestedForReading, GetValue, and SetValue, which chain back to it. Then a statement Foo["Bar"]["Boz"] = "George"; will end up effectively performing Foo.SetNestedForReading("Bar").SetValue("Boz", "George"); while z = Foo["Bar"]["Boz"]; will effectively perform Foo.GetNestedForReading("Bar").GetValue("Boz");. Calling SetNestedForReading method with a non-existent key will create and return a new nested item; the GetNestedForReading method will an immutable "empty" item. Using this approach will thus avoid creating empty items.

Although the latter approach is more complicated than the former, it has another advantage. It's possible to have each node to individually hold its collection as either a shared deeply-immutable dictionary or an unshared mutable one; if a GetNestedForWriting call sees that the nested object is immutable, it can construct a new shallowly-mutable object holding the same items. If one defines the cloning method for a mutable node as creating a new immutable node with (immutable) clones of all subnodes, and the cloning method of an immutable node as returning itself, cloning trees that are mostly immutable becomes very cheap. If one had a newly-cloned (thus immutable) four-level tree with sixteen items on each level (65,536 leaf nodes total) and all the nodes were shared-immutable, updating a leaf node would only require replacing one leaf and four other nodes with mutable ones. Cloning the tree again would only require creating new immutable objects for the nodes which had been replaced with mutable ones (e.g. copying five things). Although one would have the convenience of a fully-mutable tree, one would have the efficiency advantages of an immutable one.

The biggest "problem" I see with this approach is that to avoid some weird behaviors one must require the use of syntax like MyDict["Foo"]["Bar"].Value = "George". If implicit conversion operators were used to avoid that requirement, someone would expect a statement like var st = MyThing["Foo"]["Bar"]; to define st as a string snapshot of whatever MyThing["Foo"]["Bar"] holds at that moment; instead it would define it as something that will index MyThing["Foo"]["Bar"]. If one had to use .Value to read or write strings from such a type, the fact that the variable wasn't a string would be apparent. If one used implicit operators to allow such assignments, the behavior would be odd. It's too bad there's no way a function can specify "do not allow this return value to be used for type inference".

Incidentally, it's possible to have the indexer type be a class or a generic struct. If it's a class, an access to foo["Bar"]["boz"]["baz"]... nested N deep would likely require the creation of N temporary heap objects. If it's a generic struct, it would entail the creation of N structs, but the more-deeply-nested structs would get bigger. For reasonable levels of nesting, generic structs would probably be slightly more efficient, but classes would probably be easier to work with.