This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of New status.

4262. copy_if, remove_copy, remove_copy_if, unique_copy have too strong preconditions

Section: 26.7.1 [alg.copy], 26.7.8 [alg.remove], 26.7.9 [alg.unique] Status: New Submitter: Alex Guteniev Opened: 2025-05-12 Last modified: 2025-10-21

Priority: 3

View other active issues in [alg.copy].

View all other issues in [alg.copy].

View all issues with New status.

Discussion:

26.7.1 [alg.copy]/16 , 26.7.8 [alg.remove]/11, 26.7.9 [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 26.7.1 [alg.copy]/2:

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

[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."

Proposed resolution:

This wording is relative to N5008.

  1. Modify 26.7.1 [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 26.7.8 [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 26.7.9 [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) — […]