dcollections 1.0 and 2.0a beta released

[Andrei Alexandrescu]

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?

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

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

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

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

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.


Andrei