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: 25.7.8 [alg.remove], 25.7.9 [alg.unique], 25.8.2.4 [partial.sort.copy], 25.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 25.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.

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

   >     […]
   >     //25.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 = {});
   >     }
   >     […]
   >     // 25.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 = {});
   >     }
   >     […]
   >     // 25.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 = {});
   >     }
   >     […]
   >     // 25.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 25.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 t The 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 25.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 t The 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 25.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 25.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 a An 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 a An 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`.

   > > […]