Talk:cpp/algorithm/move

Non-overlapping ranges

Actually, what is the best way to express the requirement here and in std::copy that "d_first shall not be in the range [first,last)." 25.3.2[alg.move]/3 and 25.3.1[alg.copy]/3? Or what about the note that copy_backwards/move_backwards must be used instead of copy/move "when last is in the range [d_first - (last - first), d_first) " (footnotes 269 and 270) --Cubbi 21:21, 17 August 2011 (PDT)

I think we can rewrite the first requirement as is. As of the second, I don't yet understand the rationale for doing that.P12 01:13, 18 August 2011 (PDT)

I think I can rephrase it as: "copy is not allowed if the beginning of the output range is inside input range" and "copy_backward is not allowed if the end of the output range is inside the input range", as in:

int a[10] = {0,1,2,3,4,5,6,7,8,9};
 
    // non-overlapping copy of the two elements from [1..3) to [8..10) can be done either way
    copy(a+1, a+3, a+8); // OK
    copy_backward(a+1, a+3, a+10); // OK
 
    // overlapping copy of the four elements from [1..5) to [2..6)
    // cannot be done with copy(), but can be done with copy_backward()
    copy(a+1, a+5, a+2); // BAD 
    copy_backward(a+1, a+5, a+6); // OK
 
    // overlapping copy of the four elements from [2..6) to [1..5)
    // cannot be done with copy_backward(), but can be done with copy()
    copy(a+2, a+6, a+1); // OK
    copy_backward(a+2, a+6, a+5); // BAD

--Cubbi 07:18, 18 August 2011 (PDT)

I still do not understand the rationale of that footnote 'copy_backwards/move_backwards must be used instead of copy/move "when last is in the range [d_first - (last - first), d_first)'. If d_first does not overlap with [first, last), we'll never overwrite any of the elements, so there should be no problem. Maybe it's a deficiency of the Standard draft? P12 07:33, 18 August 2011 (PDT)

The deficiency is that they didn't specify whether first/last/result in the footnote are the first/last/result of copy() or the first/last/result of copy_backward() and I got confused translating it to the terminology used here (this wiki calls result of copy() d_first and result of copy_backward() d_last). I should have written "copy_backward should be used instead of copy when last is in the range [d_last - (last - first), d_last)" , that is a+5 is in the range [a+2, a+6) in my second example above. --Cubbi 08:08, 18 August 2011 (PDT)

Ok, now the idea is clear to me. It seems this is a complex wording of d_first shall not be in the range [first,last), otherwise use copy_backward, since both conditions last in [d_last - (last - first), d_last) and d_first in [first, last) are equivalent, except for the edge cases.

Explanation: d_last - (last - first) is equivalent to d_first as last-first == d_last-d_first. So last in [d_last - (last - first), d_last) is equivalent to last in [d_first, d_last), or d_first <= last, last < d_last. The second inequality is equivalent to first < d_first. So we get first < d_first <= last or d_first in (first, last].P12 11:48, 18 August 2011 (PDT)