Range length property

[Jonathan M Davis]

On Tuesday, April 10, 2018 19:47:10 Nordlöw via Digitalmars-d-learn wrote:
> On Tuesday, 10 April 2018 at 14:34:40 UTC, Adam D. Ruppe wrote:
> > On Tuesday, 10 April 2018 at 14:25:52 UTC, Nordlöw wrote:
> >> Should ranges always provide a length property?
> >
> > No.
> >
> >> If so, in which cases is a length property an advantage or a
> >> requirement?
> >
> > Just provide it whenever it is cheap to do so. If you need to
> > do complex calculations or especially loop over contents to
> > figure out the length, do NOT provide it.
> >
> > But if it is as simple as returning some value, provide it and
> > algorithms can take advantage of it for optimizations etc. as
> > needed.
>
> I'm thinking of my own container Hashmap having its range
> ByKeyValue requiring one extra word of memory to store the
> iteration count which, in turn, can be used to calculate the
> length of the remaining range. Is this motivated?

That would depend entirely on what you're trying to do, but in general, if a
range has length, then some algorithms will be more efficient, and some
algorithms do require length. So, if you can provide length, then the range
will be more useful, just like a bidirectional range can be more useful than
a forward range or a random-access range can be more useful than either.
However, if you're not doing anything that ever benefits from it having
length, then it doesn't buy you anything. So, it ultimately depends on what
you're doing. In a general purpose library, I'd say that it should have
length if it can do so in O(1), but if it's just for you, then it may or may
not be worth it.

The other thing to consider is what happens when the container is mutated. I
don't think that ranges necessarily behave all that well when an underlying
container is mutated, but it is something that has to be considered when
dealing with a range over a container. Even if mutating the underlying
container doesn't necessarily invalidate a range, maintaining the length in
the manner that you're suggesting probably makes it so that it would be
invalidated in more cases, since if any elements are added or removed in the
portion that was already popped off the range, then the iteration count
couldn't be used to calculate the length in the same way anymore. Now, with
a hash map, the range is probably fully invalidated when anything gets added
or removed anyway, since that probably screws with the order of the elements
in the range, but how the range is going to behave when the underlying
container is mutated and how having the length property does or doesn't
affect that is something that you'll need to consider.

- Jonathan M Davis