Issue 3186: ranges removal, partition, and partial_sort_copy algorithms discard useful information

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

Section: 26.7.8 [alg.remove], 26.7.9 [alg.unique], 26.8.2.4 [partial.sort.copy], 26.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:

We don't need to repeat the definition of partial_sort_copy_result in 26.8.2.4 [partial.sort.copy]; the single definition in the synopsis is sufficient.
e is a potentially confusing choice of placeholder name for the end of the output range, given that we use a placeholder E for predicates in the algorithm specifications.

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.

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

[…]
//26.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 = {});
}
[…]
// 26.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 = {});
}
[…]
// 26.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 = {});
}
[…]
// 26.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 = {});
}
[…]

Change 26.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:

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

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

[…]

Change 26.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:

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

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

[…]

Change 26.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:

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

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

[…]

Change 26.8.5 [alg.partitions] as indicated:

[…]
namespace ranges {
 template<Permutable I, Sentinel S, class Proj = identity,
 IndirectUnaryPredicate<projected<I, Proj>> Pred>
 constexpr subrange
 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:

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

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

[…]
[…]
namespace ranges {
 template<BidirectionalIterator I, Sentinel S, class Proj = identity,
 IndirectUnaryPredicate<projected<I, Proj>> Pred>
 requires Permutable
 subrange 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:

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

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

[…]

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

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