Issue 3868: Constrained algorithms should not require output

3868. Constrained algorithms should not require `output_iterator`

Section: 26.7.5 [alg.replace], 26.7.6 [alg.fill] Status: LEWG Submitter: Hewill Kang Opened: 2023-01-29 Last modified: 2024-06-28

Priority: 4

View all other issues in [alg.replace].

View all issues with LEWG status.

Discussion:

In C++20, output_iterator is required to support *o++ = t mainly for backward compatibility, that is to say, in addition to avoiding needless breakage, this semantic is actually not very useful, as it can be equivalently replaced by *o = t; ++o;.

This is reflected in the current implementation for constrained algorithms in libstdc++ and MSVC-STL. Even if the algorithm explicitly requires output_iterator, there is no code of the form *o++ = t in practice, and the latter of a more generic form is used instead.

It seems to me that constrained algorithms should never require output_iterator, since there really isn't any desirable reason to use *o++ = t in the new iterator system. It would be more appropriate to relax output_iterator to weakly_incrementable (or input_or_output_iterator) and indirectly_writable, given that many constrained algorithms already do that.

[2023-02-06; Reflector poll]

Set priority to 4 after reflector poll. Send to LEWG. Several votes for NAD.

[St. Louis 2024-06-28; LWG and SG9 joint session]

Poll: SG9 and LWG believe this is not a defect, but we do agree that there are inconsistencies that need a paper to address more thoroughly

|SF| F| N| A|SA|
| 6| 2| 0| 0| 0|

Proposed resolution:

This wording is relative to N4928.

Modify 26.4 [algorithm.syn], header <algorithm> synopsis, as indicated:

#include <initializer_list>     // see 17.10.2 [initializer.list.syn]

namespace std {
  […]
  namespace ranges {
    template<class I, class O>
      using replace_copy_result = in_out_result<I, O>;

    template<input_iterator I, sentinel_for<I> S, class T1, class T2,
             weakly_incrementableoutput_iterator<const T2&> O, class Proj = identity>
      requires indirectly_writable<O, const T2&> && indirectly_copyable<I, O> &&
               indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T1*>
      constexpr replace_copy_result<I, O>
        replace_copy(I first, S last, O result, const T1& old_value, const T2& new_value,
                     Proj proj = {});
    template<input_range R, class T1, class T2, weakly_incrementableoutput_iterator<const T2&> O,
             class Proj = identity>
      requires indirectly_writable<O, const T2&> && indirectly_copyable<iterator_t<R>, O> &&
               indirect_binary_predicate<ranges::equal_to,
                                         projected<iterator_t<R>, Proj>, const T1*>
      constexpr replace_copy_result<borrowed_iterator_t<R>, O>
        replace_copy(R&& r, O result, const T1& old_value, const T2& new_value,
                     Proj proj = {});

    template<class I, class O>
      using replace_copy_if_result = in_out_result<I, O>;

    template<input_iterator I, sentinel_for<I> S, class T, weakly_incrementableoutput_iterator<const T&> O,
             class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
      requires indirectly_writable<O, const T&> && indirectly_copyable<I, O>
      constexpr replace_copy_if_result<I, O>
        replace_copy_if(I first, S last, O result, Pred pred, const T& new_value,
                        Proj proj = {});
    template<input_range R, class T, weakly_incrementableoutput_iterator<const T&> O, class Proj = identity,
             indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
      requires indirectly_writable<O, const T&> && indirectly_copyable<iterator_t<R>, O>
      constexpr replace_copy_if_result<borrowed_iterator_t<R>, O>
        replace_copy_if(R&& r, O result, Pred pred, const T& new_value,
                        Proj proj = {});
  }
  […]
  namespace ranges {
    template<class T, input_or_output_iteratoroutput_iterator<const T&> O, sentinel_for<O> S>
      requires indirectly_writable<O, const T&>
      constexpr O fill(O first, S last, const T& value);
    template<class T, output_range<const T&> R>
      constexpr borrowed_iterator_t<R> fill(R&& r, const T& value);
    template<class T, input_or_output_iteratoroutput_iterator<const T&> O>
      requires indirectly_writable<O, const T&>
      constexpr O fill_n(O first, iter_difference_t<O> n, const T& value);
  }
  […]
}

Modify 26.7.5 [alg.replace] as indicated:

[…]
template<input_iterator I, sentinel_for<I> S, class T1, class T2, weakly_incrementableoutput_iterator<const T2&> O, 
         class Proj = identity>
  requires indirectly_writable<O, const T2&> && indirectly_copyable<I, O> &&
           indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T1*>
constexpr ranges::replace_copy_result<I, O>
  ranges::replace_copy(I first, S last, O result, const T1& old_value, const T2& new_value,
                       Proj proj = {});
template<input_range R, class T1, class T2, weakly_incrementableoutput_iterator<const T2&> O,
         class Proj = identity>
  requires indirectly_writable<O, const T2&> && indirectly_copyable<iterator_t<R>, O> &&
           indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T1*>
constexpr ranges::replace_copy_result<borrowed_iterator_t<R>, O>
  ranges::replace_copy(R&& r, O result, const T1& old_value, const T2& new_value,
                       Proj proj = {});

template<input_iterator I, sentinel_for<I> S, class T, weakly_incrementableoutput_iterator<const T&> O,
         class Proj = identity, indirect_unary_predicate<projected<I, Proj>> Pred>
  requires indirectly_writable<O, const T&> && indirectly_copyable<I, O>
constexpr ranges::replace_copy_if_result<I, O>
  ranges::replace_copy_if(I first, S last, O result, Pred pred, const T& new_value,
                          Proj proj = {});
template<input_range R, class T, weakly_incrementableoutput_iterator<const T&> O, class Proj = identity,
         indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
  requires indirectly_writable<O, const T&> && indirectly_copyable<iterator_t<R>, O>
constexpr ranges::replace_copy_if_result<borrowed_iterator_t<R>, O>
  ranges::replace_copy_if(R&& r, O result, Pred pred, const T& new_value,
                          Proj proj = {});

-6- Let E be
[…]

Modify 26.7.6 [alg.fill] as indicated:

[…]
template<class T, input_or_output_iteratoroutput_iterator<const T&> O, sentinel_for<O> S>
  requires indirectly_writable<O, const T&>
  constexpr O ranges::fill(O first, S last, const T& value);
template<class T, output_range<const T&> R>
  constexpr borrowed_iterator_t<R> ranges::fill(R&& r, const T& value);
template<class T, input_or_output_iteratoroutput_iterator<const T&> O>
  requires indirectly_writable<O, const T&>
  constexpr O ranges::fill_n(O first, iter_difference_t<O> n, const T& value);

-1- Let N be max(0, n) for the fill_n algorithms, and last - first for the fill algorithms.
[…]

3868. Constrained algorithms should not require output_iterator

3868. Constrained algorithms should not require `output_iterator`