DList and SList missing length property?

[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