2741. is_partitioned requirements need updating

Section: 26.8.5 [alg.partitions] Status: Resolved Submitter: Jonathan Wakely Opened: 2016-07-06 Last modified: 2020-05-12

Priority: 3

View all other issues in [alg.partitions].

View all issues with Resolved status.

Discussion:

Requires: InputIterator's value type shall be convertible to Predicate's argument type.

This seems to date from the days of adaptable function objects with an argument_type typedef, but in modern C++ the predicate might not have an argument type. It could have a function template that accepts various arguments, so it doesn't make sense to state requirements in terms of a type that isn't well defined.

[2016-07, Toronto Saturday afternoon issues processing]

The proposed resolution needs to be updated because the underlying wording has changed. Also, since the sequence is homogeneous, we shouldn't have to say that the expression is well-formed for all elements in the range; that implies that it need not be well-formed if the range is empty.

Marshall and JW to reword. Status to Open

Previous resolution [SUPERSEDED]:

This wording is relative to N4594.

1. Edit 26.8.5 [alg.partitions] as indicated:

   template <class InputIterator, class Predicate>
   bool is_partitioned(InputIterator first, InputIterator last, Predicate pred);
   

   -1- Requires: InputIterator's value type shall be convertible to Predicate's argument typeThe expression pred(*i) shall be well-formed for all i in [first, last).

   […]

   template <class InputIterator, class OutputIterator1,
             class OutputIterator2, class Predicate>
     pair<OutputIterator1, OutputIterator2>
     partition_copy(InputIterator first, InputIterator last,
                    OutputIterator1 out_true, OutputIterator2 out_false,
                    Predicate pred);
   

   -12- Requires: InputIterator's value type shall be CopyAssignable, and shall be writable (24.3.1 [iterator.requirements.general]) to the out_true and out_false OutputIterators, and shall be convertible to Predicate's argument typethe expression pred(*i) shall be well-formed for all i in [first, last). The input range shall not overlap with either of the output ranges.

   […]

   template<class ForwardIterator, class Predicate>
     ForwardIterator partition_point(ForwardIterator first,
                                     ForwardIterator last,
                                     Predicate pred);
   

   -16- Requires: ForwardIterator's value type shall be convertible to Predicate's argument typeThe expression pred(*i) shall be well-formed for all i in [first, last). [first, last) shall be partitioned by pred, i.e. all elements that satisfy pred shall appear before those that do not.

   […]

[2019-03-17; Daniel comments and removes previous wording]

In the recent working draft N4810 all the "shall be convertible to Predicate's argument type" are gone - they were cleaned up when "The One Range" proposal P0896R4 had been accepted in San Diego 2018.

I also believe that we don't need the extra wording that was suggested in the previous P/R (effectively the need to say that the expression pred(*i) is well-formed), because this follows (in a more general way) by the expression invoke(pred, invoke(proj, e)) that is applied to the elements e of [first, last).

Therefore I'm suggesting that the resolution for this issue should be: Resolved by P0896R4.

[2020-05-12; Reflector discussions]

Resolved by P0896R4.

Rationale:

Proposed resolution: