www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - range algorithms on container class

reply Alex Burton <ab bab.com> writes:
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 ?
Jan 08 2020
next sibling parent reply rikki cattermole <rikki cattermole.co.nz> writes:
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.
Jan 08 2020
parent reply Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
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
Jan 09 2020
next sibling parent reply Alex Burton <ab bab.com> writes:
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.
Jan 14 2020
parent =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
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
Jan 15 2020
prev sibling parent reply Paul Backus <snarwin gmail.com> writes:
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
Jan 15 2020
parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
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
Jan 18 2020
prev sibling parent Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
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
Jan 09 2020