On Sat, 22 May 2010 16:58:12 -0400, Andrei Alexandrescu
<[email protected]> wrote:
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!
length is allowed to return NO_LENGTH_SUPPORT if O(1) length isn't
possible, but all dcollections define length. In that case, you can do
coll.begin.empty to determine if the collection has any elements.
But all dcollections are bi-directional anyways, there is no singly linked
list. That was a decision I made early on, because it allows more
assumptions about dcollections' containers. I think length-less singly
linked lists would be a good addition to phobos that are not part of the
collection hierarchy, they are almost on par with builtin arrays as being
so simple.
And singly linked vs. doubly linked does not make any difference whether
O(1) length is possible or not. As you say, it's O(1) splicing or O(1)
length, regardless of single or double links.
I disagree with your assessment that length is a less used operation than
splicing. I think I have never used splicing with std::list. C++'s
default is O(1) length, and I followed that design.
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.
I am not familiar with tries, and dcollections has no class hierarchy.
-Steve
