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
