Thread overview
range algorithms on container class
January 09
I am writing a specialised container class, and want to make it work like a normal array with range functions.
After some struggle, I look at the code for std.container.array and see this comment :

When using `Array` with range-based functions like those in `std.algorithm`,
 * `Array` must be sliced to get a range (for example, use `array[].map!`
 * instead of `array.map!`). The container itself is not a range.


I had thought the compiler would make a generic random access range that works with the built in array for anything else with a simililar interface, but it doesn't.

Does that mean it is not possible to have a library container implementation that works nicely with range algorithms ? Do you have to slice it like the comment suggests ?


January 09
On 09/01/2020 6:28 PM, Alex Burton wrote:
> I am writing a specialised container class, and want to make it work like a normal array with range functions.
> After some struggle, I look at the code for std.container.array and see this comment :
> 
> When using `Array` with range-based functions like those in `std.algorithm`,
>   * `Array` must be sliced to get a range (for example, use `array[].map!`
>   * instead of `array.map!`). The container itself is not a range.
> 
> 
> I had thought the compiler would make a generic random access range that works with the built in array for anything else with a simililar interface, but it doesn't.
> 
> Does that mean it is not possible to have a library container implementation that works nicely with range algorithms ? Do you have to slice it like the comment suggests ?

Slicing via the opSlice operator overload is a convention, not a requirement.

The reason this is necessary is because you do not want to be calling input range methods directly on a container. If you do this, the container itself will have the state of the input range, with no way to reset it to the full contents.

The trick is to store this into a Voldemort type returned by the opSlice operator overload.

If you want it to behave like an actual array and not the Array container in Phobos, you will have to use a lot more operator overloads (which you should be doing for a list). These will be on the container itself. One of these is opApply which allows for iterating over it.
January 09
On Wednesday, January 8, 2020 10:28:23 PM MST Alex Burton via Digitalmars-d- learn wrote:
> I am writing a specialised container class, and want to make it
> work like a normal array with range functions.
> After some struggle, I look at the code for std.container.array
> and see this comment :
>
> When using `Array` with range-based functions like those in
> `std.algorithm`,
>   * `Array` must be sliced to get a range (for example, use
> `array[].map!`
>   * instead of `array.map!`). The container itself is not a range.
>
>
> I had thought the compiler would make a generic random access range that works with the built in array for anything else with a simililar interface, but it doesn't.
>
> Does that mean it is not possible to have a library container implementation that works nicely with range algorithms ? Do you have to slice it like the comment suggests ?

You could make a container a range, but then iterating over it would pop elements off of the container, which almost certainly isn't something that you want. Containers are normally supposed to overload opSlice which returns a range over the container so that you can iterate over the container without altering it. And if you use a container with foreach, the compiler will actually insert the opSlice call for you. Alternatively, you can define opApply on the container. Outside of foreach though, you'd have to explicitly slice the container.

- Jonathan M Davis



January 09
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



January 15
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.

I would expect that returning a slice would not be logically possible for many container types. 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.

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

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.


January 15
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

January 15
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

Is this documented in the language spec anywhere? I don't see anything about it in the section on foreach [1] or the section on slice operator overloading [2].

[1] https://dlang.org/spec/statement.html#foreach-statement
[2] https://dlang.org/spec/operatoroverloading.html#slice
January 18
On Wednesday, January 15, 2020 9:13:05 AM MST Paul Backus via Digitalmars-d- learn 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
>
> Is this documented in the language spec anywhere? I don't see anything about it in the section on foreach [1] or the section on slice operator overloading [2].
>
> [1] https://dlang.org/spec/statement.html#foreach-statement [2] https://dlang.org/spec/operatoroverloading.html#slice

I don't know if it's in the spec or not, but IIRC, it was in TDPL. Either way, I'm sure that it's been implemented. IIRC, there was even a bug related to filter, because it had opSlice implemented on it for some reason when it really shouldn't have, resulting in unexpected behavior when using the range with foreach.

- Jonathan M Davis