Range length property

[Jonathan M Davis]

On Tuesday, April 10, 2018 14:25:52 Nordlöw via Digitalmars-d-learn wrote:
> Should ranges always provide a length property?
>
> If so, in which cases is a length property an advantage or a
> requirement?

Whether a range has a length property or not is primarily dependent on how
efficient it is to implement length.
https://dlang.org/phobos/std_container.html lists the Big-O complexity of
the various functions and properties that are expected for containers, and
in the case of length, that also applies to ranges. It lists O(log n) as the
Big-O complexity of length, so length should only be implemented if its
Big-O complexity is no worse than O(log n). In most cases, that means
implementing it only if it's O(1) (I think that it's O(log n) rather than
O(1) because of binary trees), and length should certainly never be
implemented if it's O(n). Basically, if you can just return the length
without calculating it, then it makes sense to implement it, but if you have
to calculate it, then in most cases, it shouldn't be there. Range-based
functions are going to expect length to be very cheap to call if it is
present, and any function that needs to ascertain the length of a range even
if it doesn't have length will call walkLength (which returns length if
present and iterates the entire range to count it if it's not). As iterating
the entire range to count it, is O(n), most algorithms won't do that are
more likely to require length if they need to know how many elements there
are in the range, but that depends on what they're doing.

A function that requires a length property or which has a path optimized for
ranges that have a length property checks for that with
std.range.primitives.hasLength. Random access ranges are required to either
be infinite or provide length, but for other range types, it's optional and
must be checked for if an algorithm is going to use it.

And actually, a large percentage of ranges are lazy, in which case, it's
pretty rare that they can have a length property, because you usually have
no way of knowing how long they're going to be without actually iterating
through the range. So, while it's not uncommon for a range to define length,
it's very common that they don't.

- Jonathan M Davis