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