dcollections 1.0 and 2.0a beta released

[Andrei Alexandrescu]

On 05/24/2010 10:23 AM, Steven Schveighoffer wrote:
> 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.

That doesn't matter. Since you define NO_LENGTH_SUPPORT and you have 
interfaces, the door is ajar forever. Client code can't write this:

auto total = cont1.length + cont2.length;

because that is incorrect code (that compiles, runs, and produces some 
odd result).

So don't take it lightly. NO_LENGTH_SUPPORT means no length support. 
Then pretending it's supported will only harm everyone.

>>> 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 :)

Not moot because you have interfaces.

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

What's the required complexity of concat? Is add expected to put things 
in a specific place? How does slist implement back()?

slist does not fit 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 understand. The problem is when you many such lists or when you 
manipulate a few intensively.

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

That's what STL said about slists. Next thing you know... forward_list 
is being standardized.


Andrei