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

3186. ranges removal, partition, and partial_sort_copy algorithms discard useful information

Section: 27.7.8 [alg.remove], 27.7.9 [alg.unique], 27.8.2.4 [partial.sort.copy], 27.8.5 [alg.partitions] Status: C++20 Submitter: Tomasz Kamiński Opened: 2019-02-05 Last modified: 2021-02-25

Priority: 1

View all other issues in [alg.remove].

View all issues with C++20 status.

Discussion:

This is direct follow-up on the LWG issue 3169, that proposed to change additional algorithms that drop the iterator value equal to sentinel, that needs to be always computed. These set include removal (remove, remove_if, and unique), partition (partition, stable_partition), and partial_sort_copy.

For removal algorithms, the end of "not-erased" objects, and the "end-of-range" iterator forms a valid range of objects with unspecified value (that can be overwritten), thus we propose to return subrange.

For partition algorithms, the end of "true" object, and the "end-of-range" iterator forms a valid range of objects for which predicate returns "false", thus we propose to return subrange.

For partial_sort_copy we propose to return partial_sort_copy_result as an alias to copy_result to match other copy algorithms.

[2019-02-12; Tomasz comments and improves proposed wording]

Proposed wording is updated to incorporate wording comments from Casey Carter:

The placeholder e is replaced with j that seems not to be used in the specification of above algorithms.

[2019-02 Priority set to 1 after reflector discussion]

[2019-02; Kona Wednesday night issue processing]

Status to Ready

Proposed resolution:

This wording is relative to N4800.

  1. Change header <algorithm> synopsis, 27.4 [algorithm.syn], as indicated:

    […]
    //27.7.8 [alg.remove], remove
    […]
    namespace ranges {
    template<Permutable I, Sentinel<I> S, class T, class Proj = identity>
      requires IndirectRelation<ranges::equal_to<>, projected<I, Proj>, const T*>
      constexpr subrange<I> remove(I first, S last, const T& value, Proj proj = {});
    template<ForwardRange R, class T, class Proj = identity>
      requires Permutable<iterator_t<R>> &&
               IndirectRelation<ranges::equal_to<>, projected<iterator_t<R>, Proj>, const T*>
      constexpr safe_subrangeiterator_t<R>
        remove(R&& r, const T& value, Proj proj = {});
    template<Permutable I, Sentinel<I> S, class Proj = identity,
             IndirectUnaryPredicate<projected<I, Proj>> Pred>
      constexpr subrange<I> remove_if(I first, S last, Pred pred, Proj proj = {});
    template<ForwardRange R, class Proj = identity,
             IndirectUnaryPredicate<projected<iterator_t<R>, Proj>> Pred>
      requires Permutable<iterator_t<R>>
      constexpr safe_subrangeiterator_t<R>
        remove_if(R&& r, Pred pred, Proj proj = {});
    }
    […]
    // 27.7.9 [alg.unique], unique
    […]
    namespace ranges {
      template<Permutable I, Sentinel<I> S, class Proj = identity,
               IndirectRelation<projected<I, Proj>> C = ranges::equal_to<>>
        constexpr subrange<I> unique(I first, S last, C comp = {}, Proj proj = {});
      template<ForwardRange R, class Proj = identity,
               IndirectRelation<projected<iterator_t<R>, Proj>> C = ranges::equal_to<>>
        requires Permutable<iterator_t<R>>
        constexpr safe_subrangeiterator_t<R>
          unique(R&& r, C comp = {}, Proj proj = {});
    }
    […]
    // 27.8.2 [alg.sort], sorting
    […]
    namespace ranges {
      template<class I, class O> using partial_sort_copy_result = copy_result<I, O>;
    
      template<InputIterator I1, Sentinel<I1> S1, RandomAccessIterator I2, Sentinel<I2> S2,
               class Comp = ranges::less<>, class Proj1 = identity, class Proj2 = identity>
        requires IndirectlyCopyable<I1, I2> && Sortable<I2, Comp, Proj2> &&
                 IndirectStrictWeakOrder<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
        constexpr partial_sort_copy_result<I1, I2>
          partial_sort_copy(I1 first, S1 last, I2 result_first, S2 result_last,
                            Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
      template<InputRange R1, RandomAccessRange R2, class Comp = ranges::less<>,
               class Proj1 = identity, class Proj2 = identity>
        requires IndirectlyCopyable<iterator_t<R1>, iterator_t<R2>> &&
                 Sortable<iterator_t<R2>, Comp, Proj2> &&
                 IndirectStrictWeakOrder<Comp, projected<iterator_t<R1>, Proj1>,
                                         projected<iterator_t<R2>, Proj2>>
        constexpr partial_sort_copy_result<safe_iterator_t<R1>, safe_iterator_t<R2>>
          partial_sort_copy(R1&& r, R2&& result_r, Comp comp = {},
                            Proj1 proj1 = {}, Proj2 proj2 = {});
    }
    […]
    // 27.8.5 [alg.partitions], partitions
    […]
    namespace ranges {
      template<Permutable I, Sentinel<I> S, class Proj = identity,
               IndirectUnaryPredicate<projected<I, Proj>> Pred>
        constexpr subrange<I>
          partition(I first, S last, Pred pred, Proj proj = {});
      template<ForwardRange R, class Proj = identity,
               IndirectUnaryPredicate<projected<iterator_t<R>, Proj>> Pred>
        requires Permutable<iterator_t<R>>
        constexpr safe_subrangeiterator_t<R>
          partition(R&& r, Pred pred, Proj proj = {});
    }
    […]
    namespace ranges {
      template<BidirectionalIterator I, Sentinel<I> S, class Proj = identity,
               IndirectUnaryPredicate<projected<I, Proj>> Pred>
        requires Permutable<I>
          subrange<I> stable_partition(I first, S last, Pred pred, Proj proj = {});
      template<BidirectionalRange R, class Proj = identity,
               IndirectUnaryPredicate<projected<iterator_t<R>, Proj>> Pred>
        requires Permutable<iterator_t<R>>
          safe_subrangeiterator_t<R> stable_partition(R&& r, Pred pred, Proj proj = {});
    }
    […]
    
  2. Change 27.7.8 [alg.remove] as indicated:

    […]
    namespace ranges {
    template<Permutable I, Sentinel<I> S, class T, class Proj = identity>
      requires IndirectRelation<ranges::equal_to<>, projected<I, Proj>, const T*>
      constexpr subrange<I> remove(I first, S last, const T& value, Proj proj = {});
    template<ForwardRange R, class T, class Proj = identity>
      requires Permutable<iterator_t<R>> &&
               IndirectRelation<ranges::equal_to<>, projected<iterator_t<R>, Proj>, const T*>
      constexpr safe_subrangeiterator_t<R>
        remove(R&& r, const T& value, Proj proj = {});
    template<Permutable I, Sentinel<I> S, class Proj = identity,
             IndirectUnaryPredicate<projected<I, Proj>> Pred>
      constexpr subrange<I> remove_if(I first, S last, Pred pred, Proj proj = {});
    template<ForwardRange R, class Proj = identity,
             IndirectUnaryPredicate<projected<iterator_t<R>, Proj>> Pred>
      requires Permutable<iterator_t<R>>
      constexpr safe_subrangeiterator_t<R>
        remove_if(R&& r, Pred pred, Proj proj = {});
    }
    

    […]

    -4- Returns: Let j be tThe end of the resulting range. Returns:

    1. (4.?) — j for the overloads in namespace std, or

    2. (4.?) — {j, last} for the overloads in namespace ranges.

    […]

  3. Change 27.7.9 [alg.unique] as indicated:

    […]
    namespace ranges {
      template<Permutable I, Sentinel<I> S, class Proj = identity,
               IndirectRelation<projected<I, Proj>> C = ranges::equal_to<>>
        constexpr subrange<I> unique(I first, S last, C comp = {}, Proj proj = {});
      template<ForwardRange R, class Proj = identity,
               IndirectRelation<projected<iterator_t<R>, Proj>> C = ranges::equal_to<>>
        requires Permutable<iterator_t<R>>
        constexpr safe_subrangeiterator_t<R>
          unique(R&& r, C comp = {}, Proj proj = {});
    }
    

    […]

    -4- Returns: Let j be tThe end of the resulting range. Returns:

    1. (4.?) — j for the overloads in namespace std, or

    2. (4.?) — {j, last} for the overloads in namespace ranges.

    […]

  4. Change 27.8.2.4 [partial.sort.copy] as indicated:

    […]
    namespace ranges {
      template<InputIterator I1, Sentinel<I1> S1, RandomAccessIterator I2, Sentinel<I2> S2,
               class Comp = ranges::less<>, class Proj1 = identity, class Proj2 = identity>
        requires IndirectlyCopyable<I1, I2> && Sortable<I2, Comp, Proj2> &&
                 IndirectStrictWeakOrder<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
        constexpr partial_sort_copy_result<I1, I2>
          partial_sort_copy(I1 first, S1 last, I2 result_first, S2 result_last,
                            Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
      template<InputRange R1, RandomAccessRange R2, class Comp = ranges::less<>,
               class Proj1 = identity, class Proj2 = identity>
        requires IndirectlyCopyable<iterator_t<R1>, iterator_t<R2>> &&
                 Sortable<iterator_t<R2>, Comp, Proj2> &&
                 IndirectStrictWeakOrder<Comp, projected<iterator_t<R1>, Proj1>,
                                         projected<iterator_t<R2>, Proj2>>
        constexpr partial_sort_copy_result<safe_iterator_t<R1>, safe_iterator_t<R2>>
          partial_sort_copy(R1&& r, R2&& result_r, Comp comp = {},
                            Proj1 proj1 = {}, Proj2 proj2 = {});
    }
    

    […]

    -4- Returns:

    1. (4.?) — result_first + N for the overloads in namespace std, or

    2. (4.?) — {last, result_first + N} for the overloads in namespace ranges.

    […]

  5. Change 27.8.5 [alg.partitions] as indicated:

    […]
    namespace ranges {
      template<Permutable I, Sentinel<I> S, class Proj = identity,
               IndirectUnaryPredicate<projected<I, Proj>> Pred>
        constexpr subrange<I>
          partition(I first, S last, Pred pred, Proj proj = {});
      template<ForwardRange R, class Proj = identity,
               IndirectUnaryPredicate<projected<iterator_t<R>, Proj>> Pred>
        requires Permutable<iterator_t<R>>
        constexpr safe_subrangeiterator_t<R>
          partition(R&& r, Pred pred, Proj proj = {});
    }
    

    […]

    -7- Returns: Let i be aAn iterator i such that E(*j) is true for every iterator j in [first, i) and false for every iterator j in [i, last). Returns:

    1. (7.?) — i for the overloads in namespace std, or

    2. (7.?) — {i, last} for the overloads in namespace ranges.

    […]

    […]
    namespace ranges {
      template<BidirectionalIterator I, Sentinel<I> S, class Proj = identity,
               IndirectUnaryPredicate<projected<I, Proj>> Pred>
        requires Permutable<I>
          subrange<I> stable_partition(I first, S last, Pred pred, Proj proj = {});
      template<BidirectionalRange R, class Proj = identity,
               IndirectUnaryPredicate<projected<iterator_t<R>, Proj>> Pred>
        requires Permutable<iterator_t<R>>
          safe_subrangeiterator_t<R> stable_partition(R&& r, Pred pred, Proj proj = {});
    }
    

    […]

    -11- Returns: Let i be aAn iterator i such that for every iterator j in [first, i), E(*j) is true, and for every iterator j in the range [i, last), E(*j) is false,. Returns:

    1. (11.?) — i for the overloads in namespace std, or

    2. (11.?) — {i, last} for the overloads in namespace ranges.

    […]