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
