dcollections 0.01 release

[Robert Fraser]

Some guy wrote:
> Steven Schveighoffer Wrote:
> 
>> I've been tinkering with a collection package that is a hybrid between C++, 
>> Java, and Tango, utilizing the best D features (such as slicing, foreach, 
>> etc.).
>>
>> The result is dcollections.  Here is a list of the features:
>>
>>     * Hash, RBTree, Link, and Array implementations for appropriate 
>> containers.
>>     * List, Set, Map, and Multiset containers provided.
>>     * Able to swap out underlying implementation of a container, or 
>> customize implementation.
>>     * Minimized heap activity. All cursors are struct-based.
>>     * Should be compatible with both Tango and Phobos (tested with Tango).
>>     * Slicing where appropriate (currently only ArrayList, but will add to 
>> other containers).
>>     * Removal while traversing.
>>     * Removal of elements does not invalidate cursors where possible.
>>     * Cursors can be kept for later use (such as O(1) removal if supported 
>> by the container).
>>     * Interfaces for implementation-independent code.
>>     * Concatenation and appending for lists.
>>     * dup functions.
>>     * Set/Map intersection.
>>     * Handy filter, transform, and chain iterators.
>>
>> There's a lot left to be done, especially on the documentation and testing 
>> side, so don't expect everything to be properly documented or actually work 
>> :)  But I think it's at a point where it can be useful.
>>
>> Enjoy!
>>
>> http://www.dsource.org/projects/dcollections
>>
>> -Steve 
>>
>>
> 
> Just wondering why people (especially from the U.S.) always build red-black trees instead of AVL trees ( http://en.wikipedia.org/wiki/Avl_tree ) which are faster, simpler to understand, simpler to implement and support the same set of operations?

Well, according to my data structures prof...

- For data inserted perfectly randomly, plain BSTs work best
- For data inserted mostly randomly but with occasional ordering, 
red-black trees work best. This is why Java's collection framework uses 
them, since for unknown user data they're probably the best choice
- For data inserted in a mostly-ordered fashion, AVL trees work best
- For data retrieved in an ordered or clumped fashion, Splay trees are best
- For data that won't fit entirely in memory, B+trees are best (but 
that's sort of a special niche)