 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Joe Gottman
Guest
|
 Posted: Wed Mar 02, 2005 4:18 pm Post subject: Defect Report: Requirements of std::partition are too strict |
 |
|
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 ]
|
|
| Back to top |
|
 |
Pete Becker
Guest
|
| Posted: Thu Mar 03, 2005 6:26 am Post subject: Re: Defect Report: Requirements of std::partition are too st |
|
|
Joe Gottman wrote:
| Quote: | 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 ]
|
|
| Back to top |
|
|
dietmar_kuehl@yahoo.com
Guest
|
| Posted: Thu Mar 03, 2005 6:48 am Post subject: Re: Defect Report: Requirements of std::partition are too st |
|
|
Joe Gottman wrote:
| Quote: | 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 (AT) yahoo (DOT) 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 ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
