dcollections 1.0 and 2.0a beta released

[Andrei Alexandrescu]

On 05/24/2010 11:14 AM, Steven Schveighoffer wrote:
> On Mon, 24 May 2010 11:45:44 -0400, Andrei Alexandrescu
> <SeeWebsiteForEmail at erdani.org> wrote:
>
>> 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.
>
> I get what you are saying. What I meant was it's moot if you are not
> using interfaces. If you don't know what the underlying type is, then
> you have to do a runtime check.
>
> I agree it's awkward, and I could have not included length as a member
> of Iterator, in which case it would be on all the container types and
> NO_LENGTH_SUPPORT would not exist. All containers are meant to have a
> valid length, it is only with non-container Iterators that length can be
> NO_LENGTH_SUPPORT.
>
>>> 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?
>
> O(n) with n being the number of elements added
>
>> Is add expected to put things in a specific place? How does slist
>> implement back()?
>>
>> slist does not fit the List interface.
>
> A pointer to the end element would be required for both appending and
> back().

This further erodes my confidence. Size needs to be maintained _and_ a 
pointer to the last element must be maintained. For many uses, all of 
this stuff is unnecessary overhead.

I think we need to build the shared vision that in Phobos we're 
competing against hand-written, highly-optimized code. This is the fight 
STL took and largely won. We can't afford to lower our standards for one 
tiny bit.

I was once talking over a beer about the advantages of container 
abstractions. Walter slapped my face by defining the fastest SLL in the 
world on a napkin. It looked like this:

struct List { int v; List * next; }

He took so little time to define that, and the primitives he needed were 
so simple and fast, that it was an absolute overkill to replace that 
with a generic whiz-bang container. If I'd mentioned there'd be any 
extra data involved, that would mean the end of negotiation. "Why do you 
need that?" "For length()!" "But I don't need length()!" "Well you have 
to." "That's Communism in design!"

And I agree.


Andrei