www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Should std.algorithm.find demand a reference to range elements?

reply "Eduardo Pinho" <enet4mikeenet gmail.com> writes:
Good day. I came across something strange in the Phobos library, 
and would like to understand whether this is an issue in the 
implementation or something that I overlooked. I have kept the 
question in Stack Overflow for a while (still unanswered), but I 
will put the essentials in this post as well. 
http://stackoverflow.com/questions/28304856/should-std-algorithm-find-demand-a-reference-to-range-elements

I was implementing a class-based finite random access range, and 
wished to test it with functions in the algorithm library. Once I 
came into `std.algorithm.find` (the find_if variant), a 
compilation error popped up: "algorithm.d|4838|error: foreach: 
cannot make e ref"

This was in GDC 4.9.2, but the same snippet can be found in the 
repository here: 
https://github.com/D-Programming-Language/phobos/blob/master/std/algorithm/searching.d#L1492

I actually understand why this happened, since I did not provide 
either range properties returning by reference or `opApply` 
taking a delegate with a `ref` argument. The thing is that I feel 
that I should not be obliged to provide them at all. It is not a 
requirement for an input range to provide elements by reference, 
and find_if does not seem to need them either. I can change the 
`foreach` to take elements by value, and my tests would work just 
fine.

Some assistance on understanding what is wrong here is greatly 
appreciated.
Feb 05 2015
parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Thursday, 5 February 2015 at 10:36:34 UTC, Eduardo Pinho wrote:

 Some assistance on understanding what is wrong here is greatly 
 appreciated.


There's definitely nothing wrong with your code.

I always thought foreach preferred opApply when available because 
internal iteration can in theory be faster than external 
iteration (although it rarely is with current compilers because 
the indirect call to the delegate is often the bottleneck), but 
as you've pointed out, the specification claims external 
iteration is be preferred. Either the specification has to be 
changed, or the compiler has to be changed.

If internal iteration remains preferred, `find` should probably 
be changed to use an explicit for-loop:
---
     size_t i = 0;
     for (auto h = haystack.save; !h.empty; h.popFront())
     {
         if (predFun(h.front))
             return haystack[i .. $];
         ++i;
     }
     return haystack[$ .. $];
---
(`haystack` is known to be a forward range in this portion of the 
code)

However, this would set a possibly disruptive precedent that 
range algorithms must no longer use foreach on aggregate types...
Feb 05 2015
parent reply "Daniel Murphy" <yebbliesnospam gmail.com> writes:
"Jakob Ovrum"  wrote in message news:flxonctqqtzmtyintbtj forum.dlang.org...


 However, this would set a possibly disruptive precedent that range 
 algorithms must no longer use foreach on aggregate types...


I think this precedent already exists thanks to the bad behavior of foreach 
over narrow strings.
Feb 05 2015
parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Thursday, 5 February 2015 at 11:04:41 UTC, Daniel Murphy wrote:

 "Jakob Ovrum"  wrote in message 
 news:flxonctqqtzmtyintbtj forum.dlang.org...


 However, this would set a possibly disruptive precedent that 
 range algorithms must no longer use foreach on aggregate 
 types...


 I think this precedent already exists thanks to the bad 
 behavior of foreach over narrow strings.


Good point.

I'll file a PR for `find` in any case.
Feb 05 2015
parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Thursday, 5 February 2015 at 11:06:39 UTC, Jakob Ovrum wrote:

 On Thursday, 5 February 2015 at 11:04:41 UTC, Daniel Murphy 
 wrote:

 "Jakob Ovrum"  wrote in message 
 news:flxonctqqtzmtyintbtj forum.dlang.org...


 However, this would set a possibly disruptive precedent that 
 range algorithms must no longer use foreach on aggregate 
 types...


 I think this precedent already exists thanks to the bad 
 behavior of foreach over narrow strings.


 Good point.

 I'll file a PR for `find` in any case.


https://github.com/D-Programming-Language/phobos/pull/2964
Feb 05 2015
parent "Eduardo Pinho" <enet4mikeenet gmail.com> writes:
On Thursday, 5 February 2015 at 11:11:37 UTC, Jakob Ovrum wrote:

 On Thursday, 5 February 2015 at 11:06:39 UTC, Jakob Ovrum wrote:

 On Thursday, 5 February 2015 at 11:04:41 UTC, Daniel Murphy 
 wrote:

 "Jakob Ovrum"  wrote in message 
 news:flxonctqqtzmtyintbtj forum.dlang.org...


 However, this would set a possibly disruptive precedent that 
 range algorithms must no longer use foreach on aggregate 
 types...


 I think this precedent already exists thanks to the bad 
 behavior of foreach over narrow strings.


 Good point.

 I'll file a PR for `find` in any case.


 https://github.com/D-Programming-Language/phobos/pull/2964


I'm glad to see this resolved so quickly! I hope to also see your 
answer in my SO question. Otherwise, I can answer it myself, 
though your words and experience might make a better one.
Feb 05 2015