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-linkedlists 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
