3089. copy_n should require non-overlapping ranges

Section: 26.7.1 [alg.copy] Status: New Submitter: Marshall Clow Opened: 2018-03-21 Last modified: 2022-11-06

Priority: 3

View other active issues in [alg.copy].

View all other issues in [alg.copy].

View all issues with New status.

Discussion:

All the copy algorithms have some kind of prohibition on having the input and output ranges overlap.

The serial version of copy says:

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

The parallel version of copy says:

Requires: The ranges [first, last) and [result, result + (last - first)) shall not overlap.

copy_if says:

Requires: The ranges [first, last) and [result, result + (last - first)) shall not overlap.

copy_backwards says:

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

But copy_n has no such requirement.

I think it should. I checked the minutes of the LWG discussion from 2008 when this was added, and there was no discussion of overlapping ranges.

What formulation do we want here? Is it sufficient to say "... shall not be in the range ..." or should we use the stronger "... shall not overlap ..."? Some copy variants use one, some use the other. Should we be consistent? Issue 3085 is a similar issue for char_traits::copy.

[2018-06-18 after reflector discussion]

Priority set to 3

Previous resolution [SUPERSEDED]:

This wording is relative to N4727.

1. Edit 26.7.1 [alg.copy] as indicated:

   [Drafting note: I'm using the permission in 26.2 [algorithms.requirements]/10 to do random-access arithmetic on (possibly) input iterators.]

   template<class InputIterator, class Size, class OutputIterator>
     constexpr OutputIterator copy_n(InputIterator first, Size n,
                                     OutputIterator result);
   template<class ExecutionPolicy, class ForwardIterator1, class Size, class ForwardIterator2>
     ForwardIterator2 copy_n(ExecutionPolicy&& exec,
                             ForwardIterator1 first, Size n,
                             ForwardIterator2 result);
   

   -?- Requires: result shall not be in the range [first, first + n).

   -9- Effects: For each non-negative integer i < n, performs *(result + i) = *(first + i).

   -10- Returns: result + n.

   -11- Complexity: Exactly n assignments.

[2022-11-06; Daniel syncs wording with recent working draft]

Proposed resolution:

This wording is relative to N4917.

1. Edit 26.7.1 [alg.copy] as indicated:

   [Drafting note: I'm using the permission in 26.2 [algorithms.requirements]/10 to do random-access arithmetic on (possibly) input iterators.]

   template<class InputIterator, class Size, class OutputIterator>
     constexpr OutputIterator copy_n(InputIterator first, Size n,
                                     OutputIterator result);
   template<class ExecutionPolicy, class ForwardIterator1, class Size, class ForwardIterator2>
     ForwardIterator2 copy_n(ExecutionPolicy&& exec,
                             ForwardIterator1 first, Size n,
                             ForwardIterator2 result);
   template<input_iterator I, weakly_incrementable O>
     requires indirectly_copyable<I, O>
     constexpr ranges::copy_n_result<I, O>
       ranges::copy_n(I first, iter_difference_t<I> n, O result);
   

   -10- Let N be max(0, n).

   -11- Mandates: The type Size is convertible to an integral type (7.3.9, 11.4.8).

   -?- Preconditions: result is not in the range [first, first + n).

   -12- Effects: For each non-negative integer i < N, performs *(result + i) = *(first + i).

   -13- Returns:

   1. (13.1) — result + N for the overloads in namespace std.

   2. (13.2) — {first + N, result + N} for the overload in namespace ranges.

   -14- Complexity: Exactly N assignments.