Does std::copy handle overlapping ranges?

Question

When copying data from one range to another, you have to be careful if there's partial overlap between the source and destination ranges. If the beginning of the destination range overlaps the tail of the source range, a plain sequential copy will garble the data. The C run-time library has memmove in addition to memcpy to handle such overlap problems.

I assume std::copy works like memcpy, in that it doesn't pay any regard to overlap between the source and destination regions. If you try to shift objects "down" in a std::vector with std::copy, you'll corrupt the data. Is there an STL algorithm analogue of memmove to handle situations like this? Or should I roll my own with reverse iterators?

score 25 · Accepted Answer · edited May 10 '22 at 18:11

25

It doesn't handle overlapping ranges if the beginning of the output range overlaps with the input range.

Fortunately, you can use std::copy_backward instead (which requires that you don't overlap the end of the output range with the input range).

edited May 10 '22 at 18:11

scx

3,221
1
19
37

answered Dec 23 '09 at 14:04

John Feminella

303,634
46
339
357

`std::copy_backward` would be useful in trying to implement and analogue of `memmove`. I want to take the checking for overlap burden off of the caller. – Adrian McCarthy Dec 23 '09 at 14:16

score 9 · Answer 2 · edited Jun 02 '12 at 10:42

9

Preconditions for std::copy, prohibits an overlap:

Prototype
template <class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last,
                    OutputIterator result);
Preconditions

[first, last) is a valid range.

result is not an iterator within the range [first, last).

There is enough space to hold all of the elements being copied. More formally, the requirement is that [result, result + (last - first)) is a valid range. [1]

edited Jun 02 '12 at 10:42

Flexo

87,323
22
191
272

answered Dec 23 '09 at 14:03

Alon

4,862
19
27

That answers the question in the title. The remaining question is whether there's an analogue of `memmove` or if I have to roll my own. – Adrian McCarthy Dec 23 '09 at 14:14
3

That only prohibits an overlap with the start of the destination range. As John says, an overlap with the middle or end is allowed, and `std::copy_backward` allows an overlap with the start (but not the end). – Mike Seymour Dec 23 '09 at 14:34

Ciro Santilli OurBigBook.com · Answer 3 · 2018-11-28T09:03:22.247

C++17 standard draft

The C++17 n4659 standard draft says:

28.6.1 "Copy":

template<class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last,
                    OutputIterator result);
1 Requires: result shall not be in the range [first, last).

2 Effects: Copies elements in the range [first, last) into the range [result, result + (last - first)) starting from first and proceeding to last.

and:

template<class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2
copy_backward(
    BidirectionalIterator1 first,
    BidirectionalIterator1 last,
    BidirectionalIterator2 result);
17 Requires: result shall not be in the range (first, last].

18 Effects: Copies elements in the range [first, last) into the range [result - (last-first), result) starting from last - 1 and proceeding to first. (263) For each positive integer n <= (last - first), performs *(result - n) = *(last - n).

The note then explains when to use copy_backward:

263) copy_backward should be used instead of copy when last is in the range [result - (last - first), result)

Therefore, there is no requirement of no overlap for those functions, and unlike for memcpy, the behavior of overlaps is clearly defined in the Effects sections.

You just choose between them because you usually want std::copy for copying left and std::copy_backward for copying right.

C++ also has a ranged version of std::move in <algorithm> which moves instead of copying.

The gist of the question was whether there's an analog of `std::memmove` that takes the responsibility of checking for overlap off of the caller. The answer is no. — Adrian McCarthy, Nov 27 '18 at 22:36
@AdrianMcCarthy thanks for feedback. My answer also implies that, but with standard quote :-) — Ciro Santilli OurBigBook.com, Nov 27 '18 at 23:24
This does not take care of the occation where std::copy is optimized with parallel method such as omp, is this ? Since in parallel senario there will still be overlap even if we copy from backward. — coin cheung, Aug 03 '22 at 01:08
@coincheung no idea, but it would be insane to break C++ standard requirements on a function with the same name. — Ciro Santilli OurBigBook.com, Aug 03 '22 at 07:23

score 0 · Answer 4 · answered Dec 23 '09 at 14:04

0

It seems the most straight forward way would be to create a temporary vector of the range you want to copy:

std::vector copiedRange( srcVecIterBegin, srcVecIterEnd);
std::copy( copiedRange.begin(), copiedRange.end(), srcVecIterCopyLocIter);

You can wrap this in a templated function that should be ably to do an overlapped using any container/iterator type.

answered Dec 23 '09 at 14:04

Doug T.

64,223
27
138
202

2

Yeah, but that might lead to a lot more copying than necessary. I'd rather right a function that tests for overlap and then uses the right copy technique to do it in place. – Adrian McCarthy Dec 23 '09 at 14:17

Does std::copy handle overlapping ranges?

4 Answers4

Linked