dcollections 1.0 and 2.0a beta released

[Steven Schveighoffer]

On Sat, 22 May 2010 16:58:12 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> 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