range algorithms on container class

[Ali Çehreli]

On 1/14/20 8:15 PM, Alex Burton wrote:> On Thursday, 9 January 2020 at 
10:26:07 UTC, Jonathan M Davis wrote:
 >> On Wednesday, January 8, 2020 10:56:20 PM MST rikki cattermole via
 >> Digitalmars-d-learn wrote:
 >>> Slicing via the opSlice operator overload is a convention, not a
 >>> requirement.
 >>
 >> It's not a requirement, but it's more than a convention. If you use
 >> the container with foreach, the compiler will call opSlice on the
 >> container to get a range. So, there's no need to implement opApply to
 >> iterate over a container with foreach. You could choose to implement a
 >> container with opApply and use a function other than opSlice for
 >> getting a range, but the compiler understands enough to try to slice
 >> the container for you automatically when using it with foreach.
 >>
 >> - Jonathan M Davis
 >
 > Implementing opApply allowed me to use foreach on the container.

However, that method does not allow you to have more than one iteration 
on the same container. Once opApply is running, the state of iteration 
is in function call stack. (opApply is calling out to the body of the 
foreach loop until the loop is over.)

In contrast, you can have multiple range objects over the same container:

   auto a = cont[];
   auto b = cont[];

Now the state of iteration are independently handled by a and b.

There is only one case that comes to mind where opApply is superior: 
When iteration involves recursion like tree traversal, then the way 
opApply takes advantage of function call stack is vastly easier (to me 
at least :) ). Even in that case, one can use fibers but it is a little 
bit more complication over opApply.

 > I would expect that returning a slice would not be logically possible
 > for many container types.

That is true if you're thinking about a slice as a RandomAccessRange, 
which is the case for arrays. However, if we think of slicing as 
"returning a range object over all elements" (i.e. an InputRange 
suffices), then it fits all containers.

 > A slice cannot be a range either, otherwise
 > you would need to call the array algorithm to assign a slice of an array
 > to another array.

Part of this confusion (for me as well) is due to D's conflation of 
slices with dynamic arrays. When we see the slice as the range and think 
of the memory location as the sometimes anonymous container, then slice 
assignment may be valid for user-defined containers. The name of the 
operator is not clear (opIndexAssign):

   https://dlang.org/spec/operatoroverloading.html#slice_assignment_operator

I have two sections that show examples of its single-dimensional and 
multi-dimensional uses:

 
http://ddili.org/ders/d.en/operator_overloading.html#ix_operator_overloading.opIndexAssign

The multi-dimensional use case shows how a container and its range types 
are different types:

 
http://ddili.org/ders/d.en/templates_more.html#ix_templates_more.opIndexAssign%20template

That example was difficult for me to understand. :)

 > So the compiler must be creating a forward iterating range to pass into
 > the range algorithms in these cases.

Exactly and should do the same with user-defined types.

 > That foreach, and range algorithms can work on a native array but only
 > foreach can work on custom container type looks like a gap in the 
language.

I think there are some corner cases but not for most (all?) cases.

Ali