N3092 defines partition, stable_partition, and partition_copy.  The
algorithms differ in where they store their results and the relative
ordering thereof.

The rationale for providing a _copy version of an algorithm is based
on whether or not the complexity of the operation would dominate the
copy.  It seems like this rationale ought to be in play for
stable_partition.

Is this a hole or is this algorithm somehow redundant or otherwise
inappropriate?

--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use
mailto:std-c++@netlab.cs.rpi.edu<std-c%2B%2B@netlab.cs.rpi.edu>
]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On 9/14/2010 4:49 PM, Jared wrote:

> N3092 defines partition, stable_partition, and partition_copy.  The
> algorithms differ in where they store their results and the relative
> ordering thereof.
>
> The rationale for providing a _copy version of an algorithm is based
> on whether or not the complexity of the operation would dominate the
> copy.  It seems like this rationale ought to be in play for
> stable_partition.
>
> Is this a hole or is this algorithm somehow redundant or otherwise
> inappropriate?
>

  The effects of partition_copy are "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."  I'm pretty sure this implies that it is stable.

Joe Gottman

--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use
mailto:std-c++@netlab.cs.rpi.edu<std-c%2B%2B@netlab.cs.rpi.edu>
]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On 14 Sep., 22:49, Jared <jaredhober...@gmail.com> wrote:
> N3092 defines partition, stable_partition, and partition_copy.  The
> algorithms differ in where they store their results and the relative
> ordering thereof.
>
> The rationale for providing a _copy version of an algorithm is based
> on whether or not the complexity of the operation would dominate the
> copy.  It seems like this rationale ought to be in play for
> stable_partition.
>
> Is this a hole or is this algorithm somehow redundant or otherwise
> inappropriate?

It is redundant, because partition_copy is already stable: Both
destinations are filled by conserving the original ordering.
In fact you can implement a simple stable_partition if
you have a buffer of the same size as the to-be-partitioned
sequence by writing [untested]:

template<class ForwardIterator1, class ForwardIterator2,
 class Predicate>
ForwardIterator1
stable_partition_with_buffer(ForwardIterator1 first1,
 ForwardIterator1 last1, ForwardIterator2 first2,
 Predicate pred)
{
 std::pair<ForwardIterator1, ForwardIterator2> res =
   std::partition_copy(first1, last1, first1, first2, pred);
 return std::copy(first2, res.second, res.first);
}

It satisfies the criteria for stable partitioning, because both
the relative order of the elements satisfying the predicate
and that of those not satisfying the predicate remains
preserved.

HTH & Greetings from Bremen,

Daniel Kr=FCgler

--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use
mailto:std-c++@netlab.cs.rpi.edu<std-c%2B%2B@netlab.cs.rpi.edu>
]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On Sep 14, 3:49=A0pm, Jared <jaredhober...@gmail.com> wrote:
> N3092 defines partition, stable_partition, and partition_copy. =A0The
> algorithms differ in where they store their results and the relative
> ordering thereof.

Because partition_copy is stable. The fact that it works with
InputIterators in O(N) time and no auxiliary memory pretty much
guarantees that.

I suppose the standard should note this, but it's in the comments of
the GNU implementation at least.

--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use
mailto:std-c++@netlab.cs.rpi.edu<std-c%2B%2B@netlab.cs.rpi.edu>
]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On Sep 14, 1:49=A0pm, Jared <jaredhober...@gmail.com> wrote:
> N3092 defines partition, stable_partition, and partition_copy. =A0The
> algorithms differ in where they store their results and the relative
> ordering thereof.
>
> The rationale for providing a _copy version of an algorithm is based
> on whether or not the complexity of the operation would dominate the
> copy. =A0It seems like this rationale ought to be in play for
> stable_partition.
>
> Is this a hole or is this algorithm somehow redundant or otherwise
> inappropriate?

If we did have a stable_partition_copy it would be the same algorithm
as partition_copy.  One would have to go to extra expense to implement
partition_copy in a non-stable manner.  Perhaps a "Remarks: Stable"
clause for partition_copy is in order.

-Howard

--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use
mailto:std-c++@netlab.cs.rpi.edu<std-c%2B%2B@netlab.cs.rpi.edu>
]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On 15 Sep., 20:14, David Krauss <pot...@gmail.com> wrote:
> On Sep 14, 3:49=A0pm, Jared <jaredhober...@gmail.com> wrote:
>
> > N3092 defines partition, stable_partition, and partition_copy. =A0The
> > algorithms differ in where they store their results and the relative
> > ordering thereof.
>
> Because partition_copy is stable. The fact that it works with
> InputIterators in O(N) time and no auxiliary memory pretty much
> guarantees that.
>
> I suppose the standard should note this, but it's in the comments of
> the GNU implementation at least.

I agree that the standard could be a bit clearer in this regard. As in
"copy_if", the normative remark "Stable" should be added.

Greetings from Bremen,

Daniel Kr=FCgler

--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use
mailto:std-c++@netlab.cs.rpi.edu<std-c%2B%2B@netlab.cs.rpi.edu>
]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]