dcollections 1.0 and 2.0a beta released

[Steven Schveighoffer]

On Mon, 24 May 2010 10:10:51 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail at erdani.org> wrote:

> On 05/24/2010 06:54 AM, Steven Schveighoffer wrote:
>> length is allowed to return NO_LENGTH_SUPPORT if O(1) length isn't
>> possible,
>
> Do you agree that's an awkwardness?

Yes, at that point it's an optimization.  The only place where I assume  
length could be invalid is when working with the Iterator!V type, which  
might not be a dcollections object.

>
>> but all dcollections define length.
>
> I was hoping we're on the verge of agreeing to yank all interfaces and  
> let the collection roam free. If that's a possibility, then your design  
> isn't constrained to define length anymore unless in can.

I agree, removing all the interfaces would get rid of the need for  
NO_LENGTH_SUPPORT.  But all dcollections define a valid length, so that  
point is kinda moot :)  However, supporting non-length containers via  
generic programming vs. interfaces would be much smoother.

>> In that case, you can do
>> coll.begin.empty to determine if the collection has any elements.
>
> Then why not make length optional and define empty? From the above it  
> looks like an obviously better design.
>
>> 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.
>
> Do you see dcollections' inability to express slists as a problem?

I don't see them as unable to express slists.  They would break the design  
guidelines that I set for collections being iterable in both directions,  
but an slist fits fine within the List interface.

>> 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.
>
> I didn't assess that.

I felt like you did.  Your statement was: "It works against splicing (an  
important list primitive) and most of the time you don't need it so why  
waste time updating it."

While you didn't specifically say it was used more, you mentioned the  
importance of splicing, and the non-importance of length.  I guess I  
should have said, I disagree that splicing is more important than caching  
length.

> My main point was that if one defines an slist, in many cases one  
> defines it to be very small, simple, and cheap. Maintaining size will  
> come on the radar and would discourage the use of the abstraction in  
> favor of a hand-rolled implementation. This is failure to abstract.

All dcollections own their elements, it is not like an array, where there  
can be multiple references to subsets of the data.  An slist would simply  
be an slist as you describe with a slightly bigger head.  In other words,  
the head node has the length cache and allocator, and object monitor, and  
whatever else you need for the whole list.  The nodes themselves would be  
a simple element and pointer.  But the elements are never exposed except  
via ranges and cursors.  The ranges and cursors cannot affect the topology  
of the list, you need the head "owner" node to do that.

I look at it this way, dcollections are "good enough" for most uses, if  
you need highly tailored data structures with specific uses in mind, you  
can make those on your own.

For example, dcollections' LinkList can easily take the place of a simple  
slist.  It may not be as fast with your specific requirements in mind, but  
it works.  The benefit is, it works like all the other collection types  
and it's easy to learn all of them together because they all have certain  
properties.

> I don't know of a word for "hierarchy with interfaces as root and inner  
> nodes and classes as leaf nodes" so I just call that class hierarchy.

I view them as classes with interfaces tacked on because the  
implementations are similar :)

-Steve