DList and SList missing length property?

[Paulo Pinto]

Am 28.05.2013 20:16, schrieb Jonathan M Davis:
> On Tuesday, May 28, 2013 20:03:49 Paulo Pinto wrote:
>> Hi,
>>
>> maybe this is more indicated for d.learn, but I am not sure if
>> it is not a bug in the documentation/implementation.
>>
>> According to the phobos documentation, all containers in std.container
>> should provide a length property.
>
> It never says that. It lists what complexity each operation must have in order
> for a container to have that operation. It doesn't guarantee that any
> particular operation will be present on all containers (though any that's O(n)
> or worse is pretty much bound to be on all containers unless in does something
> fundamentally incompatible with a particular container's data structure).
>
>> However it is only available for arrays.
>>
>> Sure one could use the std.algorithm.count() or std.range.walkLength(),
>> but I don't see a reason why SList and DList aren't aware of their
>> current size.
>>
>> Is this on purpose?
>
> Yes. It's on purpose. When dealing with lists, because you can insert at any
> point, you have two choices:
>
> 1. Make length efficent.
>
> 2. Make splicing efficient.
>
> If you keep track of the length, then you have to count all of the elements
> when you splice two lists, so splicing is O(n) instead of O(1). If you don't
> keep track of the length, then splicing is O(1), but then length is O(n), and
> length can't be O(n) per std.container's complexity requirements.
>
> Now, that being said, I don't see a splice operation on either SList or DList
> (and I don't think that splicing an SList can be done in O(1) anyway), so it
> would appear that the implementation is optimizing for an operation that it
> doesn't currently support.
>
> The same situation exists with C++'s std::list type though - size() is O(n)
> and splicing is O(1). However, we opted for not having containers implement
> inefficient operations like that (which C++ mostly did as well, but not in this
> case).
>
> If you want the length of a container which doesn't have a length property,
> then use walkLength on its range - e.g. walkLength(container[]).
>
> - Jonathan M Davis
>

Ok, maybe the documentation should explicitly state to which containers 
each operation applies to.

Currently it is a bit confusing to see the complexity listed, but not 
finding the methods.

Thanks for the lengthy explanation, it is actually in sync with what I 
was thinking might be the reason.

--
Paulo