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