Title
`copy_if`, `remove_copy`, `remove_copy_if`, `unique_copy` have too strong preconditions
Status
new
Section
[alg.copy][alg.remove][alg.unique]
Submitter
Alex Guteniev

Created on 2025-05-12.00:00:00 last changed 1 month ago

Messages

Date: 2025-10-21.11:45:47

Proposed resolution:

This wording is relative to N5008.

  1. Modify [alg.copy] as indicated:

    template<class InputIterator, class OutputIterator, class Predicate>
      constexpr OutputIterator copy_if(InputIterator first, InputIterator last,
                                       OutputIterator result, Predicate pred);
    […]
    template<input_range R, weakly_incrementable O, class Proj = identity,
             indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
      requires indirectly_copyable<iterator_t<R>, O>
      constexpr ranges::copy_if_result<borrowed_iterator_t<R>, O>
        ranges::copy_if(R&& r, O result, Pred pred, Proj proj = {});
    

    -15- Let E be: […]

    -16 Preconditions: `result` is not in the range `[first, last)`The ranges `[first, last)` and `[result, result + (last - first))` do not overlap.

  2. Modify [alg.remove] as indicated:

    template<class InputIterator, class OutputIterator,
             class T = iterator_traits<InputIterator>::value_type>
      constexpr OutputIterator
        remove_copy(InputIterator first, InputIterator last,
                    OutputIterator result, const T& value);
    […]
    template<input_range R, weakly_incrementable O, class Proj = identity,
             indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
      requires indirectly_copyable<iterator_t<R>, O>
      constexpr ranges::remove_copy_if_result<borrowed_iterator_t<R>, O>
        ranges::remove_copy_if(R&& r, O result, Pred pred, Proj proj = {});
    

    -8- Let E be […]

    […]

    -11 Preconditions: `result` is not in the range `[first, last)`The ranges `[first, last)` and `[result, result + (last - first))` do not overlap.

  3. Modify [alg.unique] as indicated:

    template<class InputIterator, class OutputIterator>
      constexpr OutputIterator
        unique_copy(InputIterator first, InputIterator last,
                    OutputIterator result);
    […]
    template<input_range R, weakly_incrementable O, class Proj = identity,
             indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
      requires indirectly_copyable<iterator_t<R>, O> &&
              (forward_iterator<iterator_t<R>> ||
              (input_iterator<O> && same_as<range_value_t<R>, iter_value_t<O>>) ||
              indirectly_copyable_storable<iterator_t<R>, O>)
      constexpr ranges::unique_copy_result<borrowed_iterator_t<R>, O>
        ranges::unique_copy(R&& r, O result, C comp = {}, Proj proj = {});
    

    -6- Let `pred` be […]

    -7- Mandates: […]

    -8 Preconditions:

    1. (8.1) — `result` is not in the range `[first, last)`The ranges `[first, last)` and `[result, result + (last - first))` do not overlap.

    2. (8.2) — […]

Date: 2025-10-15.00:00:00

[ 2025-10-21; Reflector poll. ]

Set priority to 3 after reflector poll.

"The proposed resolution is incorrect, because the output iterator could ‘enter’ the range [first, last) via being incremented. If the output iterator is a reverse iterator, it starts writing to the end of [first,last) before we need to read from there."

"NAD - nothing is broken with the existing constraint. Relaxing it is a design change."

"NAD. The right behavior, if the algorithm runs out of output space, is to return the last processed input iterator and the "next spot" output iterator. This is what P3179 (parallel ranges algorithms) does with its range-as-output algorithms. I would not want the proposed resolution without this change. Otherwise, we would be introducing new UB unnecessarily."

Date: 2025-05-12.00:00:00

[alg.copy]/16 , [alg.remove]/11, [alg.unique]/8.1 all say:

Preconditions: The ranges `[first, last)` and `[result, result + (last - first))` do not overlap.

These algorithms may produce fewer elements than `(last - first)`. If this is known in advance, a smaller output range may be used, so that the precondition will not be satisfied.

Example from LLVM test suite ( /libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/ranges.copy_if.pass.cpp):

std::array<S, 4> in = {{{4, 2}, {1, 3}, {3, 4}, {3, 5}}};
std::array<S, 2> out;
auto ret = std::ranges::copy_if(in.begin(), in.end(), out.begin(), [](int i) { return i == 3; }, &S::val);

I think there should be a weaker precondition, like [alg.copy]/2:

Preconditions: `result` is not in the range `[first, last)`.

History
Date User Action Args
2025-10-21 11:45:47adminsetmessages: + msg15299
2025-05-18 11:05:56adminsetmessages: + msg14760
2025-05-12 00:00:00admincreate