dcollections 1.0 and 2.0a beta released

Steven Schveighoffer schveiguy at yahoo.com
Mon May 24 09:14:59 PDT 2010


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

-Steve


More information about the Digitalmars-d-announce mailing list