According to paragraph 25.2.12, the std::partition algorithm requires
bidirectional iterators.  The usual partitioning algorithm, by Hoare, does
require bidirectional iterators, but there is an alternative algorithm, by
Lomuto, which only requires forward iterators.  While Lomuto's algorithm is
somewhat less efficient, it is still O(N), so the standard library should
provide it for forward iterators.

Proposed Resolution:
   Change 25.2.12 from
    template<class BidirectionalIterator, class Predicate>
    BidirectionalIterator partition(BidirectionalIterator first,
                                    BidirectionalIterator last,
                                    Predicate pred);



to

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



Change the complexity from

   At most (last - first)/2 swaps are done.  Exactly (last - first)
applications of the predicate are done.

to

   If ForwardIterator is a bidirectional_iterator, at most (last - first)/2
swaps are done; otherwise at most (last - first) swaps are done.  Exactly
(last - first) applications of the predicate are done.



Joe Gottman



[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Joe Gottman wrote:
> According to paragraph 25.2.12, the std::partition algorithm requires
> bidirectional iterators.  The usual partitioning algorithm, by Hoare, does
> require bidirectional iterators, but there is an alternative algorithm, by
> Lomuto, which only requires forward iterators.  While Lomuto's algorithm is
> somewhat less efficient, it is still O(N), so the standard library should
> provide it for forward iterators.
>

This is not a defect; it's a request for an enhancement. Which is not to
say we shouldn't do it, of course.

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]

Joe Gottman wrote:
> According to paragraph 25.2.12, the std::partition algorithm requires
> bidirectional iterators.  The usual partitioning algorithm, by Hoare,
does
> require bidirectional iterators, but there is an alternative
algorithm, by
> Lomuto, which only requires forward iterators.  While Lomuto's
algorithm is
> somewhat less efficient, it is still O(N), so the standard library
should
> provide it for forward iterators.

I would consider allowance for forward iterators to be a conforming
extension to the current definition, i.e. an implementer can choose to
also support forward iterators but is not required to do so.. However,
I would consider it strange if the library would be required to
implement both algorithms. In fact, there is precedence for not doing
such a thing: although sorting can be implemented in O(n log n) time
on bidrectional iterators (using e.g. merge sort), 'std::sort()'
requires random access iterators and is even given the leeway to use a
quadratic algorithm (quick sort)!

Of course, since you used the magic incantation "Defect Report" in
your subject line, I can make my point at the next committee meeting
when this "defect" is discussed. I consider it to be "NAD".
--
<mailto:dietmar_kuehl@yahoo.com> <http://www.dietmar-kuehl.de/>
<http://www.contendix.com> - Software Development & Consulting

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]