How about DictionaryWhoseKeysAreStoredInComparisonOrderButMayNotBeATreeAndIAmNotTellingYouAnywaySoJustDealWithIt?

<br>

On a more serious note...

<br>

<br>TreeDictionary might just be the right kind of name if you want to have a partner to Hashtable.  With generics, do we now have Hashtable&lt;K,V&gt; or is it something else?  Does the new generic collection based on hash values have the term &quot;hash&quot; in it?

<br>

<br>Personally, I like the TreeMap and HashMap in Java.  *shrug*  I really do think having the implementation in the name of the concrete class is a good thing.  

I like SortedDictionary better. It keeps the naming consistency with SortedList.

I vote for... BOTH!

<br>

<br>The names cater to different audiences. My suggestion would obviously bloat the surface area of the API, but I think some thoughtful namespace organization would mitigate this (e.g. a specific namespace could be created to hold the specific algorithm implementations separate from the more general, algorithm-agnostic classes).

<br>

<br>OrderedDictionary would simply implements a common interface, and uses an instance of TreeDictionary (which implements the same interface, while perhaps adding some tree-specific functionality) for the implementation. OrderedDictionary would simply forward all method invocations to the TreeDictionary instance. This affords you the ability to change the underlying algorithm without it being a breaking change, although it does prevent you from making specific promises regarding the algorithm. (If somebody wants a tree-based dictionary, then they can just use the TreeDictionary class directly.)

I have been almost exclusively C++ programmer and recently started with C#. I think that .NET BCL collection classes' names make no sense, so feel free to potentially add to the confusion in any way you like, it's not like there's some kind of consistency you'll ruin :)

<br>In other words, I expect to have to take a look at the documentation (and maybe even in the source, unless it's obfuscated) to understand what it is anyway. I guess most ex-C++ will do the same.

<br>For me the best thing is the algorithmic complexity guarantee for various operations (in the same way STL was designed), then it doesn't really matter what is inside the collection nor how it is called.

<br>

In my opinion both should have a presence in the API. Maybe...

<br>

<br>Class: TreeDictionary

<br>Interface: IOrderedDictionary

<br>

&quot;OrderedDictionary&quot; suggests that there may also be an &quot;UnorderedDictionary&quot; or maybe just &quot;Dictionary&quot;. That's where the name shows its major problem: there are no unordered dictionaries, these beasts are ordered by default and the order property is simply implied in the concept of a dictionary.

<br>

<br>Trees at the other hand come in all flavours: AVL, binary, B, B+, parse, Red-Black and what do you have. Some of these do have a particular ordering system and some do not, such as a parsetree (sometimes called syntaxtree). Some can handle duplicate keys, others don't. So if I were to vote between these two, the TreeDictionary makes more sense.

<br>

<br>But actually I'm not satisfied at all. In my world the concept of &quot;Dictionary&quot; is at a higher abstraction level than a &quot;Tree&quot;. A functional &quot;Dictionary&quot; could be programmed on top of virtually any classic datastructure, and still fullfill the mental image it summons: a dictionary is something in which you can quickly find one or more values that belong to a unique key.

<br>

<br>What about a third variant, a mutant such as &quot;OrderedTree&quot;? The point made earlier for the &quot;OrderedDictionary&quot; holds water here as well: &quot;OrderedTree&quot; to me suggests that there's an &quot;UnorderedTree&quot; or maybe just a &quot;Tree&quot; container as well. And just having the prefix &quot;ordered&quot; leaves some ambiguity: what kind of order since there are so many? As a C++ guy I have learned to appreciate the power that &quot;traits&quot; give you, besides the neatness of separation. Why not have a &quot;Tree&quot; and various kinds of &quot;TreeTraits&quot; classes (defining the order of insertion, the order of branching and other typical tree-properties, duplicates allowed etc.), the combination of which results in a finegrained matrix of &quot;Tree&quot; containers, which we might designate as a &quot;Forest&quot;? :o)

<br>

<br>As an example: Tree&lt;String,Tree::AVL&gt; or Tree&lt;int,Tree::Binary&gt; leaves little to the imagination for me as to what each of these two are. It would of course require that the user of such classes has opened a textbook on datastructures and for those who didn't there's always a typedef. You've got typedefs in C# right?

<br>

<br>/d

<br>

<br>

Map is better than Dictionary because it is shorter.  As mentioned previously there are several species of trees,  as long as money falls from them...

I prefer TreeDictionary; I'd have prefered System.Collections.Generic.Dictionary to have been named HashDictionary, though as well.  Taking an example that's more clearly open ended in backing structures, I can implement IList cleanly with a resizable array, linked list, a balanced tree, or a skip list.  If the interface and performance are all that matter, then these might be named Vector, List, Sequence, and Catalog, with either documentation or attributes on each that describes the relative performance and size costs.  A user could learn which is which, but they might as well be named List1, List2, List3, and List4.

<br>If you care about performance to the point at which you're exploring these classes for the sake of it, then it's fair to say that you'll have at least some CS background and be able to understand what a TreeDictionary is.  The BCL already provides default implementations; a user who just wants the semantics will use those and look no further.

<br>As an aside, I thought the C++ ISO committee was looking to standardize the common hash_map/hash_set extensions, though maybe not and maybe they would be differenly named before actually being added.

My vote is as OrderedDictionary should be a interface or the common set of method that can be implemented by different underline object(tree or something.).  -Reason, I won't want to force to look up the documentation (I hate MSDN give me 500+ records on any given search or google give me even more....),  If I can't find Root property in a &quot;Tree&quot;Dictionary as same degree that if ArrayList didn't provide a item[] accessor.

<br>

<br>dbw:

<br>Yes, there is one similiar to C++'s typedef.  It is called aliasing

<br>for example you can do

<br>using mystring = System.String;

<br>

<br>Better yet, it is scoped within name space and intellisense-enabled. (you can also aliasing the name space as well.)

<br>

<br>Drazen Dotlic : C++ is not any better, as ex-C++, I found STL or StandardLibrary (stream, cin, cout, etc.) is very hard to read the code.  But it seems everyone just take it as granted.  I seriously doubt how many ex-C++ programmers really read how stream or &lt;vector&gt; or placement new are \ implemented.   The fact is that --- users don't want to read documentation unless they have to (That's why naming is so important -- what's the impression when user first see it.)  For example, When I call get_Mutex(),  I expect it work as the function name said -- return a object behave like Mutex.  Not that I care how it is be implemented.  Peter is the one who implement the library --- he have to care how people perceive the name when most users DONOT want to read the documentation.  Don't get me wrong, I love C++, there are times I miss it but not for its documentation or readable code.

<br>

<br>-Ming

<br>Class: TreeDictionary  +1

<br>Interface: IOrderedDictionary +1

<br>Sum:  +3  (it's management :)

<br>

<br>PLEASE follow the Java api as you can for collections topics

<br>MS likes simple thinks, me too but when it's about

<br>1% of the cover for things like algo It's Just Not Work

<br>

<br>i have a lot of stat stuff this times

<br>do you thinks we shoul rename

<br>* NormalDistribution &lt;- UserDistribution

<br>* StudentDistribution &lt;- BetaDistribution

<br>* PowerFit &lt;- SmartFit

<br>): thinks about search engine pain , people culture misrepresentation

<br>

TreeDictionary isn't going far enough.  You should have an AbstractrTreeDictionary that you subclass with RedBlackTreeDictionary and AVLTreeDictionary (as well as SkewTreeDictionary frankly).  

It depends on your intentions.  If you're going to write all variations then naming them specific to the algorithm makes sense, but if you're simply addressing the lack of any kind of node-based collection in the BCL, then TreeMap is probably sufficient.  I don't know whether any target-user scenarios would be addressed by being able to choose between AvlTreeMap and RedBlackTreeMap.

<br>

<br>I may misunderstand the target user, though.  Perhaps an Advanced or DataStructures namespace beneath Collections could supply implementation specific classes.  If so, it would be nice to see a generic OpenAddressHashDictionary too.

I think that the class should be named according to its *behavior* rather than according to how it happens to have been implemented this time around.

<br>

<br>For the same reason I dislike Hashtable as a class name, rather than the newer Dictionary&lt;K, V&gt;. Hashtable says nothing about what the class is or does (unless you happen to know the secret Computer Science handshake), whereas Dictionary gives you some semantic information about its behavior. The same applies here. So, OrderedDictionary is fine.

<br>

<br>As for a base class, plus descendants based on whatever is the tree algorithm du jour, give me a break. If I want a fast dictionary I'll use Dictionary, if I want the same, albeit a little slower, together with the ability to iterate the keys in order, I'll go for the Ordered Dictionary. Implement the latter with a skiplist for all I care.

+1 for OrderedDictionary

<br>+1 for what Julian said - implementation is not relevant, behaviour is. (&lt;offTopic&gt;hi Julian, long time no see/hear/e-chat etc. ! Nice to see a familiar name from the good ol' days :o) &lt;/offTopic&gt;)

<br>

dbw: There ARE unordered dictionaries - hash based dictionaries do not maintain a consistant order.  Their performance is predicated on their ability to shuffle things around in a seemingly haphazard order.

Well, I'm not seeing a very clear consensus here.

<br>

<br>I myself am uncertain what is the right way to go. Perhaps it will become more clear as more classes are added.

I've always felt like arguing for naming the class after how it works is a bit silly. There should be classes like UnorderedDictionary and OrderedDictionary that tell you nothing (at least at the surface) of their implementation. Those that really care how it's implemented will know that underneath an UnorderedDictionary defaults to using a HashTable. Those that don't care can happily go on in a state of unaware.

<br>

<br>At the same time, those who care should be able to use classes like HashTable and BinaryTree to create UnorderedDictionary implementations that work based on their individual performance concerns.

<br>

<br>I'm fine with OrderedDictionary because I like knowing how my items come out of the collection and not so much how they go in. I don't like the name HashTable much because it tells me nothing about how my items come out should I go enumerate. But I really don't know a better name for HashTable other than UnorderedDictionary.

<br>

<br>I for one would like to see the AbstractBinaryTree&lt;V&gt; implementation as well with BinaryTree&lt;V&gt;, SortedBinaryTree&lt;V&gt;, AVLTree&lt;V&gt;, RedBlackTree&lt;V&gt;, etc. for separate reasons, mainly because they can be used for other varying purposes with varying degrees of performance tradeoffs. This also leads to AbstractNAryTree&lt;V&gt; but that is another story.

<br>

<br>With generic tree implementations you could have all three traversals, postorder, preorder, and inorder.

<br>

<br>IEnumerable BinaryTree&lt;V&gt;.InOrder;

<br>IEnumerable BinaryTree&lt;V&gt;.PreOrder;

<br>IEnumerable BinaryTree&lt;V&gt;.PostOrder;

<br>

<br>But the interesting thing about a sorted tree implementation of OrderedDictionary is the fact that the ordering occurs because of both the storing nodes in the tree along with the proper traversal of the tree. Unlike say a SortedList where the ordering happens on every insert.

<br>

<br>You could implement an OrderedDictionary as any variation of SortedBinaryTree&lt;V&gt; because the default traversal would be an inorder traversal of the tree. OrderedDictionary could even be written so as to suppose a default implementation of say RedBlackTree&lt;V&gt; with an optional constructor parameter to take another SortedBinaryTree implementation.

<br>

<br>OK I think I rambled on enough. I think I hit about 5 different things here and it's time to go.

<br>

<br>

<br>

<br>

Glad to see STL mentioned, which begs the question:

<br>

<br>Why Power Collections? Why not just use the STL? Or update the STL in the context of the CLR?

<br>

<br>1. The STL is proven.

<br>2. There are good books and tutorials on STL.

<br>3. A Managed C++ implementation exists (I am *assuming* here).

<br>

Since Power Collections is supposed to be an extension to the BCL, it should follow the same naming conventions.

<br>

<br>The BCL has Dictionary&lt;K, V&gt; rather than Hashtable (the old non-generic name), since what it does for you is more important than how it does it (which might be changed in the future). The documentation can discuss the performance characteristics and get into the details of how it is implemented.

<br>

<br>Again, for consistency with the BCL, I agree with Omer van Kloeten's posting that says it should be called SortedDictionary, since SortedList already exists in the BCL.

Uneducated people don’t write good software. You have to at least know basic data structures before you can do anything useful. So, TreeDictionary works here better because it implies that you can traverse the tree in ascending, descending, and etc. orders (if provided of course).