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

3868. Constrained algorithms should not require output_iterator

Section: 27.7.5 [alg.replace], 27.7.6 [alg.fill] Status: LEWG Submitter: Hewill Kang Opened: 2023-01-29 Last modified: 2023-02-06

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.

Proposed resolution:

This wording is relative to N4928.

  1. Modify 27.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);
      }
      […]
    }
    
  2. Modify 27.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

    […]

  3. Modify 27.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.

    […]