Does std::copy_n work with overlapping ranges?

Question

I was looking in the C++ standard at N3485 25.3.1 [alg.copy], which defines 4 algorithms:

• copy
• copy_backward
• copy_if
• copy_n

In the description for copy, there is this note 25.3.1 [alg.copy]/3:

Requires: result shall not be in the range [first,last)

That is, copy does not always work correctly when the ranges overlap (similar to memcpy).

copy_backward and copy_if have similar language prohibiting overlapping ranges (25.3.1 [alg.copy]/14 and 25.3.1 [alg.copy]/8, respectively).

However, there is no such prohibition for copy_n, and there is no copy_n_backward. Does this mean that copy_n does the right thing when the ranges overlap?

(MSVC++'s implementation of copy_n appears to delegate to std::memmove, so I know it is safe here on MSVC++ 2013. But I don't want to rely on this if the standard implies otherwise)

Answer 1

It is safe*. Why? Because the standard doesn't say it isn't safe. They copy functions from 25.3.1 have Requires: for things they require (this is where the overlapping prohibition is stated in the other copy forms).

However, copy_n does not say it requires that the ranges do not overlap, which means it's okay, as it's not explicitly prohibited. If it required it, it would state it.

*Edit: When I meant "safe" I meant it's not undefined behavior or an illformed program to do so. However, the results aren't guaranteed to be what you probably intended if the memory ranges overlap. The only thing we are guaranteed is:

1. For each non-negative integer i < n, *(result + i) = *(first + i) is performed
2. Calling the function with overlapping ranges is not prohibited and does not result in undefined behavior.

We can thus deduce that if the ranges overlap, then the results stored in the destination are no longer guaranteed to be an exact (in-order) copy of the source. We are guaranteed that every value in the destination will have come from the source, though exactly which values those are depends on the overlap and the exact order in which elements are copied.

So if by "safe" you mean that the destination always has a perfect copy of the source (like memmove), then no, it's not "safe". But it is safe in the sense that it won't cause undefined/invalid behavior in and of itself.

To recap, we are guaranteed that *(result + i) = *(first + i) will be done for every element in the entire range. We are guaranteed that if the ranges overlap, the program is still not undefined. We are not guaranteed the order in which the elements are copied. We are not guaranteed that if the ranges overlap, what the exact values stored in the result will be (but we do know that they all came from the source).

Answer 2

I agree with Cornstalks' answer, and +1 to it. But, theory must be backed by practice.

A quick peek at the implementations of GCC (libstdc++-v3) and Clang (libc++) shows that their copy_n is the same as (or delegates to) copy, with no support for overlapping when moving objects to higher addresses.

So, MSVC wins this round, at least in the POD case which delegates to memmove.