dcollections 1.0 and 2.0a beta released

[Andrei Alexandrescu]

On 05/19/2010 03:07 PM, Steven Schveighoffer wrote:
> Ellery Newcomer Wrote:
>
>> Are the collections supposed to not have isEmpty members?
>
> No.  Use length == 0.  O(1) length is always supported for all
> collections.

One thing before I forget: I think any good collection abstraction must
be concretized back to the classic collection instances. Singly-linked
lists definitely can't be left off the list! It would be an epic 
failure. Imagine the papers! New York Times: "D has containers, but no 
singly-linked lists". The New Yorker: "D's abstractions are too 
abstract". The National Enquirer: "The Bat Boy stole D's singly-linked 
lists". Pyongyang Times: "Another failure of the so-called Western 
Democracy -- yet Juche doesn't need singly-linked lists anyway."

Keeping the length cached in a singly-linked list is a costly mistake.
It works against splicing (an important list primitive) and most of the
time you don't need it so why waste time updating it. Adding any cruft
beyond { T payload; List* next; } is very strong incentive for the coder
to write their own. Why do you think they're using an SLL in the first
place? Because it's simple and has efficient primitives!

>> OTish: What are your thoughts on a bimap implementation and a
>> child/sibling or general tree implementation as part of
>> dcollections?
>
> I haven't the slightest what a bimap is :)  I am not an expert in
> collections or data structures, I just reimplement things I have
> understood.  My implementations are basically copied from my
> algorithm book, and refined as much as I can do.
>
> That being said, if you have any implementation of a tree or hash, it
> should be easy to insert into dcollections.  If you have ideas for
> other collection types (i.e. other than Map, Set, Multiset or List),
> then I can look into that if you point me at an implementation or
> have one of your own.  I purposefully left out multi-map because I've
> never had a huge use for it, and it seemed like a awkward thing to
> create an interface for...

Tries of various kinds come up again and again. I don't think 
dcollections' current abstractions capture them, which further supports 
my point that containers have too much personality to be caught in the 
straitjacket of class hierarchies.


Andrei