dcollections 1.0 and 2.0a beta released

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Sat May 22 13:58:12 PDT 2010


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


More information about the Digitalmars-d-announce mailing list