JTC1/SC22/WG21 N3795

A more common version of algorithm std::partition_copy.

Doc. No: N3795
Date: 2013-09-16
Reply-To: Vladimir Grigoriev (vlad.moscow@mail.ru)

Introduction.

The existent version of algorithm std::partition_copy has limited
capabilities. In fact this algorithm is similar to algorithm std::copy
but instead of copying all elements of the source sequence in one
destination sequence it redirects all elements of the source sequence
in either of two destination sequences depending on the given predicate.
As in the first case in the second case all elements of the source
sequence are processed.
 
However sometimes there is a need to process only that elements of the
source sequence that satisfy some criteria. To demonstrate the idea let
consider a simple task to copy all positive elements of an integral array 
in one container and all negative elements of the same array in some
other container without touching elements equal to zero.

This simple task can not be done by means of the existent version of
std::partition_copy. Also it is not effective to use for example two
times algorithm std::copy_if that at first to traverse the array that to
copy only positive elements and then to traverse the array anew that to
copy only negative elements.

The task could be simply done if there would be the more common version
of algorithm std::partition_copy shown below.

template <class InputIterator, 
	  class OutputIterator1, 
	  class OutputIterator2,
          class Predicate1,
          class Predicate2>

std::pair<OutputIterator1, OutputIterator2> 
partition_copy( InputIterator first, 
                InputIterator last,
                OutputIterator1 out1, 
                OutputIterator2 out2,
                Predicate1 pred1,
                Predicate2 pred2 )
{
	for ( ; first != last; ++first )
	{
		if ( pred1( *first ) ) *out1++ = *first;
		if ( pred2( *first ) ) *out2++ = *first;
	}

	return ( std::make_pair( out1, out2 ) );
}

This version of std::partition_copy is similar functionally to
std::copy_if but instead of selectively copying the original elements in
one sequence according to a given condition it copies the original
elements in two sequences according to each corresponding condition.

Using this algorithm the task could be done the following way

std::partition_copy( std::begin( a ), std::end( a ), 
                     std::begin( b ), std::begin( c ),
                     std::bind2nd( std::greater<int>(), 0 ), 
                     std::bind2nd( std::less<int>(), 0 ) );

where a, b, and c are some containers.

Now we have a complete relation between std::copy and std::copy_if
on the one hand and std::partition_copy with one predicate and
std::partition_copy with two predicates on the other hand. That is
functionally std::copy corresponds to std::partition_copy with one
predicate and std::copy_if corresponds to std::partition_copy with two
predicates. The difference is that std::copy and std::copy_if deal with
one output sequence while std::partition_copy with one predicate and its
more common version std::partition_copy with two predicates deal with two 
output sequences.

Proposed changes to the C++ Standard.

Section 25.1 General paragraph #2. Include the following declaration
after the existent declaration of std::partition_copy

template <class InputIterator, 
	  class OutputIterator1, 
	  class OutputIterator2,
          class Predicate1,
          class Predicate2>

pair<OutputIterator1, OutputIterator2> 
partition_copy( InputIterator first, InputIterator last,
                OutputIterator1 out1, OutputIterator2 out2,
                Predicate1 pred1, Predicate2 pred2 );


Section 25.3.13 Partitions. To include the following declaration after
the existent declaration of std::partition_copy

template <class InputIterator, 
	  class OutputIterator1, 
	  class OutputIterator2,
          class Predicate1,
          class Predicate2>

pair<OutputIterator1, OutputIterator2> 
partition_copy( InputIterator first, InputIterator last,
                OutputIterator1 out1, OutputIterator2 out2,
                Predicate1 pred1, Predicate2 pred2 );


To change paragraphs ## 12, 13, 14, 15 the following way:

12 Requires: InputIterator’s value type shall be Assignable, and shall
be writable to the out_true and out_false OutputIterators or out1 and
out2 OutputIterators correspondingly, and shall be convertible to
Predicates’ argument types. The input range shall not overlap with
either of the output ranges.

13 Effects: For the version of the algorithm with one predicate for each
iterator i in [first,last), copies *i to the output range beginning with
out_true if pred(*i) is true, or to the output range beginning with
out_false otherwise. For the version of the algorithm with two predicates 
for each iterator i in [first,last), copies *i to the output range
beginning with out1 if pred1(*i) is true and/or to the output range
beginning with out2 if pred2(*i) is true.

14 Returns: A pair p such that p.first is the end of the output range
beginning at out_true and p.second is the end of the output range
beginning at out_false for the version of the algorithm with one
predicate or p.first is the end of the output range beginning at out1
and p.second is the end of the output range beginning at out2 for the
version of the algorithm with two predicates.

15 Complexity: Exactly last - first applications of pred for the version
of the algorithm with one predicate or last - first applications
of pred1 and pred2 for the version of the algorithm with two predicates.