2014-02-15 23:17 GMT+01:00 Adam Wulkiewicz :

Hi,

Krzysztof Czainski wrote:

...

2014-02-15 1:05 GMT+01:00 Adam Wulkiewicz :

Hmm, how about:

...

boost::copy( range | movable, out_it );

Yes, of course this should also be possible. There is already boost::move_iterator in Boost.Move. To be consistent with the standard we should probably also have boost::move() algorithm and a range adaptor. But the naming scheme for Range adaptors is different, the past tense should be used, right? Hence "moved".

The name 'moved' would misleadingly suggest that something already moved. But then, so does 'move'. Regards, Kris

On 02/15/2014 02:17 PM, Adam Wulkiewicz wrote:

There is already boost::move_iterator in Boost.Move

Please make sure that move iterators and ranges are Input and not anything else, regardless of what the standard says. The standard is dangerously wrong in this regard. Eric

On 02/18/2014 09:16 AM, Adam Wulkiewicz wrote:

Hi Eric,

Eric Niebler wrote:

...

On 02/15/2014 02:17 PM, Adam Wulkiewicz wrote:

...

There is already boost::move_iterator in Boost.Move Please make sure that move iterators and ranges are Input and not anything else, regardless of what the standard says. The standard is dangerously wrong in this regard.

Thanks for the advice. It's because the user might by mistake go through some elements more than once which would result in some number of moves from the same element or do you have something more surprising in mind?

That's it precisely. And using move iterators in standard algorithms that assume anything other than Input is pretty much guaranteed to make you very unhappy.

Unfortunately the boost::move_iterator follows the standard here. And since it's already in Boost it probably shouldn't be changed to ensure backward compatibility. We could of course implement different one and use it in Boost.Range but I'm not sure if this is a good idea. Should we have two different move_iterators in Boost?

I take a hard stand on this. A Forward move iterator is totally broken. I have *no* sympathy for people who are using move iterators where Forward is needed. Their code is buggy. We should change boost::move_iterator and help people find their bugs. I have zero compunction about doing this. Eric

El 18/02/2014 19:21, Adam Wulkiewicz escribió:

I'll wait for the feedback from the rest of the community. Ion are you ok with this?

A forward move iterator is very useful when inserting values in containers. The forward property is used to know how many elements are in the range. After that, each element is only moved once. I see no problem with this approach. Ion

On 19 Feb 2014 20:22, "Eric Niebler" wrote:

On 02/19/2014 10:54 AM, Ion Gaztañaga wrote:

...

El 18/02/2014 19:21, Adam Wulkiewicz escribió:

...

I'll wait for the feedback from the rest of the community. Ion are you ok with this?

A forward move iterator is very useful when inserting values in containers. The forward property is used to know how many elements are in the range. After that, each element is only moved once. I see no problem with this approach.

That's a very good example. Thanks. I need to think about whether that use case justifies the danger.

That isn't a compromise you need to make. I believe you are trying to prevent cases of multiple moves where that is invalid. This doesn't and shouldn't be done by piggybacking on traversal concepts. There are a number of valid use cases that would be broken: 1. Distance before traversal. I have no concrete use cases of this one. 2. Reverse traversal. I have numerous examples of this in production. 3. Multipass traversal moving subsets of objects with each pass while correctly avoiding multiple moves of an individual object. I have numerous examples of this in production. In many cases one can refactor to a less elegant single pass solution, however where I have state from initial passes the refactoring would be very significant and make the code worse. I would have to include additional copies or fork the move iterator. I think the danger you highlight is real, but I think the problem is erroneous moves and the solution of adding tracking and assertions for this is much more comprehensive and direct in addressing the problem. Please don't increase restrictions on the move iterator. I know I can fork the old code but I cannot believe I will be the only person left with broken code from this change.

Eric

I am sorry if I have repated myself. For my random access stride, sure it only suffers an unnecessary performance penalty, but reverse is broken and so are the other cases outlined above. Just having suboptimal striding was enough to convince me since my applications are often very performance oriented. I hope I haven't annoyed anyone with my posts. I'm certainly trying not to. Regards, Neil Groves

Hi, Eric Niebler wrote:

On 02/19/2014 12:56 PM, Neil Groves wrote:

...

Please don't increase restrictions on the move iterator. I know I can fork the old code but I cannot believe I will be the only person left with broken code from this change. No, I won't change it. I think Ion convinced me.

Ok, I see that everything is clear now. I've prepared an implementation, here's the pull request: https://github.com/boostorg/range/pull/2. In short it adds: 1. boost::move() algorithm using the one provided by Boost.Move. 2. boost::move_backward() algorithm using the one provided by Boost.Move. 3. moved_range<> wrapping Boost.Move boost::move_iterator<> 4. adaptor::move() and moved forwarder 5. tests for the above 6. fix for boost::copy_backward() test I'd be glad if you check it out and see if everything is ok. Regards, Adam

On Tue, Feb 18, 2014 at 6:30 PM, Neil Groves wrote:

On Tue, Feb 18, 2014 at 5:32 PM, Eric Niebler wrote:

...

On 02/18/2014 09:16 AM, Adam Wulkiewicz wrote:

...

Hi Eric,

Eric Niebler wrote:

...

On 02/15/2014 02:17 PM, Adam Wulkiewicz wrote:

...

There is already boost::move_iterator in Boost.Move Please make sure that move iterators and ranges are Input and not anything else, regardless of what the standard says. The standard is dangerously wrong in this regard.

Thanks for the advice. It's because the user might by mistake go through some elements more than once which would result in some number of moves from the same element or do you have something more surprising in mind?

That's it precisely. And using move iterators in standard algorithms that assume anything other than Input is pretty much guaranteed to make you very unhappy.

I agree that many scenarios would end in much unhappiness! I disagree that unhappiness is pretty much guaranteed. I believe there are valid scenarios that would be broken by increasing the requirements to demand single-pass traversal. The most common case that I think would be broken in my own code is where I am using a random-access iterator to stride. Currently I can stride and move ever n-th element. Isn't this perfectly acceptable? I'm not convinced we should break any valid use-cases to detect more errors. Perhaps we can find a better mechanism to detect double moves in debug builds instead?

...

...

Unfortunately the boost::move_iterator follows the standard here. And since it's already in Boost it probably shouldn't be changed to ensure backward compatibility. We could of course implement different one and use it in Boost.Range but I'm not sure if this is a good idea. Should we have two different move_iterators in Boost?

I take a hard stand on this. A Forward move iterator is totally broken. I have *no* sympathy for people who are using move iterators where Forward is needed. Their code is buggy. We should change boost::move_iterator and help people find their bugs. I have zero compunction about doing this.

If my previous paragraph is correct I believe we should not break working user code. Under my current understanding I don't think multiple (and therefore invalid) moves should be prevented by increasing the limits of the traversal. I think that the problem is a multiple moves and this can and should be dealt with directly instead. I wonder if the standard is liberal in the traversal requirements for similar reasons?

...

Eric

I'm conscious that I could easily be misunderstanding some information and therefore my chain of reasoning may be broken.

I apologize for missing this section in my previous post. This is a response to my own post. This is the standard section referring to moved types that appears relevant: *17.6.5.15 Moved-from state of library types [lib.types.movedfrom]* Objects of types defined in the C++ standard library may be moved from (12.8). Move operations may be explicitly specified or implicitly generated. Unless otherwise specified, such moved-from objects shall be placed in a valid but unspecified state. To me this indicates that I may have types where my "moved from" object is valid and in a specified state. I extrapolate from this that therefore it may be valid to move from the same object multiple times. I see no reason why I should not implement a pimpl idiom where the moved-from object has the pointer assigned to null and have valid multiple move operations from the same type. I therefore think there are a number of reasons to strongly disagree with the notion that a move iterator must be an Input Iterator. Neil Groves

On 19-02-2014 02:55, Eric Niebler wrote:

...

I therefore think there are a number of reasons to strongly disagree with the notion that a move iterator must be an Input Iterator.

Yes, it's safe to assume that moved-from objects are in some valid state. That's not the issue. The moved-from state is almost guaranteed to be different from the state the object had before the move. The issue here is that the *algorithms* don't expect values in the sequence changing out from under them. This breaks assumptions all over the place. Algorithms *will* give nonsensical results when called with move iterators. It's practically guaranteed.

What would be the guarantees that an algorithm had to give for it to work. Would the following be sufficient: a. elements are only moved around by swap() (which moves) b. no element is ever assigned to local variable (reference type or not) ? -Thorsten

On 02/18/2014 10:30 AM, Neil Groves wrote:

On Tue, Feb 18, 2014 at 5:32 PM, Eric Niebler wrote:

...

On 02/18/2014 09:16 AM, Adam Wulkiewicz wrote:

...

Hi Eric,

Eric Niebler wrote:

...

On 02/15/2014 02:17 PM, Adam Wulkiewicz wrote:

...

There is already boost::move_iterator in Boost.Move Please make sure that move iterators and ranges are Input and not anything else, regardless of what the standard says. The standard is dangerously wrong in this regard.

Thanks for the advice. It's because the user might by mistake go through some elements more than once which would result in some number of moves from the same element or do you have something more surprising in mind?

That's it precisely. And using move iterators in standard algorithms that assume anything other than Input is pretty much guaranteed to make you very unhappy.

I agree that many scenarios would end in much unhappiness! I disagree that unhappiness is pretty much guaranteed. I believe there are valid scenarios that would be broken by increasing the requirements to demand single-pass traversal. The most common case that I think would be broken in my own code is where I am using a random-access iterator to stride.

Why in the world does a stride iterator need to be random-access? Here is a strided range adaptor that works with input iterators: https://github.com/ericniebler/range-v3/blob/master/include/range/v3/view/st... It's not even hard. Eric

...

Why in the world does a stride iterator need to be random-access? Here is a strided range adaptor that works with input iterators:

https://github.com/ericniebler/range-v3/blob/ master/include/range/v3/view/stride.hpp

It's not even hard.

I guess it may have been because it was the easiest. I see you have special handling of bidirectional iterators. Anyway, nice to see your improvements. :-)

I think this implies that the current implementation in Boost.Range doesn't optimise for bidirectional and random-access which is wrong. My implementation requires at least a single-pass traversal but handles bidirectional and random-access fine.

-Thorsten

Neil Groves

On Wed, Feb 19, 2014 at 1:51 AM, Eric Niebler wrote:

...

On Tue, Feb 18, 2014 at 5:32 PM, Eric Niebler wrote:

...

On 02/18/2014 09:16 AM, Adam Wulkiewicz wrote:

...

Hi Eric,

I agree that many scenarios would end in much unhappiness! I disagree

On 02/18/2014 10:30 AM, Neil Groves wrote: that

...

unhappiness is pretty much guaranteed. I believe there are valid scenarios that would be broken by increasing the requirements to demand single-pass traversal. The most common case that I think would be broken in my own code is where I am using a random-access iterator to stride.

Why in the world does a stride iterator need to be random-access? Here is a strided range adaptor that works with input iterators:

https://github.com/ericniebler/range-v3/blob/master/include/range/v3/view/st...

It's not even hard.

I understand fully that a stride can be implemented with a single-pass traversal, but this is not optimal for striding by large values as I'm sure you know. Why should combining with move make my stride less efficient? I am, of course, only using this as an example. I think there are many cases where we use the random-access traversal and dereference a subset of the elements of the underlying range. It is then valid to pass over the source range again starting from another point and stride, or do a number of other operations. This is before we allow well-defined semantics for multiple moves, which I believe is also valid.

Eric

Neil Groves