[Mono-list] references to individual keys

edward.harvey.mono edward.harvey.mono at clevertrove.com
Wed Apr 17 14:31:58 UTC 2013


I have an in-memory tree data structure, where each node contains a dictionary of named subnodes.  Some of the leaf nodes need to know their own path (that is, they need to know which sequence of strings you would follow from the root node, in order to reach this node.)

Skipping over the alternatives for now, my question is this:  Since a string is a reference type, and each string exists already within the keys of the dictionary in each parent node, I would like to just reference the string that's referenced by the keys of the parent dictionary.  When I look at the MSDN page for dictionaries, I see the TryGetValue or [] will return the value associated with a given key ... And I see the ContainsKey which returns a boolean.  But I want TryGetKey, which will actually return the *key* that has equality to the key I'm searching for.  Any way to do that?

I could use the Keys property, but then I'll have to perform O(n) string comparisons, enumerating over the collection of keys.  I see the ContainsKey method includes the comment, "This method approaches an O(1) operation." which means, I really want to avoid manually enumerating string comparisons and somehow tie into the Dictionary internal key search algorithm.

Is it possible?

At the moment, I'm not aware of any way to do it.  At the moment, my best known alternative is for each node to store a copy of its own name.  Then each leaf node could contain either a link to its parent, or a bunch of links to all of its lineage parents, or a bunch of links to just the names of all the lineage parents.  This will at least double memory usage, due to repeated storage of strings, but at least it's simple to use and understand, and won't incur a horrible performance penalty.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ximian.com/pipermail/mono-list/attachments/20130417/07c3d6ec/attachment.html>


More information about the Mono-list mailing list