I have been working with the algorithms in the Standard Library.

I have noticed that the standard (IOS/IEC 14882:1998(E)) states that
stable_partiton requires Bidirectional Iterators (see section 25.2.12
paragraph 3).

Is it not the case that it should actually require Forward Iterators?
I have seen stable_partition being instansiated with a Forward
Iterator (see the stable_partition section at
http://www.boost.org/libs/concept_check/stl_concept_covering.cpp),
although I have not actually compiled any code that tries a forward
iterator.

After seeing this, I checked the standard (as noted above).  Thinking
the standard was in error, I checked the C++ Standard - unofficial
list of revisions.  I see no mention of it there.

I also checked out the C++ Standard Library Active Issues List
(Revision 23) ( http://std.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html)
and saw no mention of it there either.

Any thoughts?  Should stable_partition in fact require a Forward
Iterator instead of a Bidirectional Iterator?

Dale

---
[ 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                       ]

"Dale Muchow" <dale_muchow@hotmail.com> wrote in message
news:97833335.0209250944.1b868492@posting.google.com...

> I have noticed that the standard (IOS/IEC 14882:1998(E)) states that
> stable_partiton requires Bidirectional Iterators (see section 25.2.12
> paragraph 3).
>
> Is it not the case that it should actually require Forward Iterators?
> I have seen stable_partition being instansiated with a Forward
> Iterator (see the stable_partition section at
> http://www.boost.org/libs/concept_check/stl_concept_covering.cpp),
> although I have not actually compiled any code that tries a forward
> iterator.
>
> After seeing this, I checked the standard (as noted above).  Thinking
> the standard was in error, I checked the C++ Standard - unofficial
> list of revisions.  I see no mention of it there.

Why do you assume that the C++ Standard is in error when you see a
piece of code that violates the C++ Standard? Nonconforming code can
compile and execute, even for years, and still trip across undefined
behavior eventually.

> I also checked out the C++ Standard Library Active Issues List
> (Revision 23) ( http://std.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html)
> and saw no mention of it there either.
>
> Any thoughts?  Should stable_partition in fact require a Forward
> Iterator instead of a Bidirectional Iterator?

Our implementation happens to work nicely with forward iterators so
long as the sequence doesn't get too large. If the algorithm can
purchase a temporary buffer large enough to hold the sequence, all
is well. Otherwise, it falls back on a divide-and-conquer technique
that uses buffered rotations to rearrange the pieces. It is the
buffered rotations that require bidirectional iterators.

We could change the spec for stable_sort to say that it mostly needs
just forward iterators, and only sometimes needs bidirectional
iterators...

P.J. Plauger
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                       ]