Title
copy_n should require non-overlapping ranges
Status
new
Section
[alg.copy]
Submitter
Marshall Clow

Created on 2018-03-21.00:00:00 last changed 1 month ago

Messages

Date: 2022-11-06.14:24:48

Proposed resolution:

This wording is relative to N4917.

  1. Edit [alg.copy] as indicated:

    [Drafting note: I'm using the permission in [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.

Date: 2022-11-15.00:00:00

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

Date: 2018-06-18.00:00:00

[ 2018-06-18 after reflector discussion ]

Priority set to 3

Previous resolution [SUPERSEDED]:

This wording is relative to N4727.

  1. Edit [alg.copy] as indicated:

    [Drafting note: I'm using the permission in [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.

Date: 2018-03-29.13:21:28

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.

History
Date User Action Args
2022-11-06 14:24:48adminsetmessages: + msg12939
2018-06-19 05:49:11adminsetmessages: + msg9937
2018-03-25 13:39:20adminsetmessages: + msg9786
2018-03-21 00:00:00admincreate