Movatterモバイル変換

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

3186.ranges removal, partition, andpartial_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++20Submitter: Tomasz KamińskiOpened: 2019-02-05Last modified: 2021-02-25

Priority:1

View all otherissues in [alg.remove].

View all issues withC++20 status.

Discussion:

This is direct follow-up on the LWG issue3169⁽ⁱ⁾, 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, andunique), partition (partition,stable_partition), andpartial_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 returnsubrange.

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 returnsubrange.

Forpartial_sort_copy we propose to returnpartial_sort_copy_result as an alias tocopy_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 ofpartial_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 placeholderE for predicates in the algorithm specifications.

The placeholdere is replaced withj 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 toN4800.

1. 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*>  constexprsubrange<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>  constexprsubrange<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<>>    constexprsubrange<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>>    constexprpartial_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>>    constexprpartial_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>    constexprsubrange<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 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*>  constexprsubrange<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>  constexprsubrange<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:Letj be tThe end of the resulting range.Returns:

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

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

   […]

3. 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<>>    constexprsubrange<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:Letj be tThe end of the resulting range.Returns:

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

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

   […]

4. 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>>    constexprpartial_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>>    constexprpartial_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 +Nfor the overloads in namespacestd, or

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

   […]

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

   […]namespace ranges {  template<Permutable I, Sentinel<I> S, class Proj = identity,           IndirectUnaryPredicate<projected<I, Proj>> Pred>    constexprsubrange<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:Leti be aAn iteratori such thatE(*j) istrue for every iteratorj in[first, i) andfalse for every iteratorj in[i, last).Returns:

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

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

   […]

   […]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:Leti be aAn iteratori such that for every iteratorj in[first, i),E(*j) istrue, and for every iteratorj in the range[i, last),E(*j) isfalse,. Returns:

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

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

   […]