[Boost-commit] svn:boost r83158 - in trunk: boost/algorithm libs/algorithm/doc libs/algorithm/test

Subject: [Boost-commit] svn:boost r83158 - in trunk: boost/algorithm libs/algorithm/doc libs/algorithm/test
From: marshall_at_[hidden]
Date: 2013-02-25 17:31:53

Author: marshall
Date: 2013-02-25 17:31:52 EST (Mon, 25 Feb 2013)
New Revision: 83158
URL: http://svn.boost.org/trac/boost/changeset/83158

Log:
Gather does not (in general) work with forward iterators, even though it does on some systems
Text files modified: 
   trunk/boost/algorithm/gather.hpp           |    17 +++++++++--------                       
   trunk/libs/algorithm/doc/gather.qbk        |    18 +++++++++---------                      
   trunk/libs/algorithm/test/gather_test1.cpp |     4 +---                                    
   3 files changed, 19 insertions(+), 20 deletions(-)

Modified: trunk/boost/algorithm/gather.hpp
==============================================================================
--- trunk/boost/algorithm/gather.hpp	(original)
+++ trunk/boost/algorithm/gather.hpp	2013-02-25 17:31:52 EST (Mon, 25 Feb 2013)
@@ -80,9 +80,10 @@
 */
 
 template <
-    typename ForwardIterator,  // Iter models ForwardIterator
-    typename Pred>  // Pred models UnaryPredicate
-std::pair<ForwardIterator,ForwardIterator> gather ( ForwardIterator first, ForwardIterator last, ForwardIterator pivot, Pred pred )
+    typename BidirectionalIterator,  // Iter models BidirectionalIterator
+    typename Pred>                   // Pred models UnaryPredicate
+std::pair<BidirectionalIterator, BidirectionalIterator> gather 
+        ( BidirectionalIterator first, BidirectionalIterator last, BidirectionalIterator pivot, Pred pred )
 {
 //  The first call partitions everything up to (but not including) the pivot element,
 //  while the second call partitions the rest of the sequence.
@@ -99,14 +100,14 @@
 */
 
 template <
-    typename ForwardRange,    //
+    typename BidirectionalRange,    //
     typename Pred>                  // Pred models UnaryPredicate
 std::pair<
-    typename boost::range_iterator<ForwardRange>::type,
-    typename boost::range_iterator<ForwardRange>::type>
+    typename boost::range_iterator<const BidirectionalRange>::type,
+    typename boost::range_iterator<const BidirectionalRange>::type>
 gather (
-    ForwardRange &range,
-    typename boost::range_iterator<ForwardRange>::type pivot,
+    const BidirectionalRange &range,
+    typename boost::range_iterator<const BidirectionalRange>::type pivot,
     Pred pred )
 {
     return boost::algorithm::gather ( boost::begin ( range ), boost::end ( range ), pivot, pred );

Modified: trunk/libs/algorithm/doc/gather.qbk
==============================================================================
--- trunk/libs/algorithm/doc/gather.qbk	(original)
+++ trunk/libs/algorithm/doc/gather.qbk	2013-02-25 17:31:52 EST (Mon, 25 Feb 2013)
@@ -22,13 +22,13 @@
 ``
 namespace boost { namespace algorithm {
 
-template <typename ForwardIterator, typename Pred>
-std::pair<ForwardIterator,ForwardIterator> 
-gather ( ForwardIterator first, ForwardIterator last, ForwardIterator pivot, Pred pred );
-
-template <typename ForwardRange, typename Pred>
-std::pair<typename boost::range_iterator<ForwardRange>::type, typename boost::range_iterator<ForwardRange>::type>
-gather ( ForwardRange &range, typename boost::range_iterator<ForwardRange>::type pivot, Pred pred );
+template <typename BidirectionalIterator, typename Pred>
+std::pair<BidirectionalIterator,BidirectionalIterator> 
+gather ( BidirectionalIterator first, BidirectionalIterator last, BidirectionalIterator pivot, Pred pred );
+
+template <typename BidirectionalRange, typename Pred>
+std::pair<typename boost::range_iterator<const BidirectionalRange>::type, typename boost::range_iterator<const BidirectionalRange>::type>
+gather ( const BidirectionalRange &range, typename boost::range_iterator<const BidirectionalRange>::type pivot, Pred pred );
 
 }}
 ``
@@ -53,11 +53,11 @@
 
 [heading Iterator Requirements]
 
-`gather` work on all iterators except input or output iterators.
+`gather` work on bidirectional iterators or better. This requirement comes from the usage of `stable_partition`, which requires bidirectional iterators. Some standard libraries (libstdc++ and libc++, for example) have implementations of `stable_partition` that work with forward iterators. If that is the case, then `gather` will work with forward iterators as well.
 
 [heading Storage Requirements]
 
-`gather` uses stable_partition, which will attempt to allocate temporary memory, but will work in-situ if there is none available.
+`gather` uses `stable_partition`, which will attempt to allocate temporary memory, but will work in-situ if there is none available.
 
 [heading Complexity]
 

Modified: trunk/libs/algorithm/test/gather_test1.cpp
==============================================================================
--- trunk/libs/algorithm/test/gather_test1.cpp	(original)
+++ trunk/libs/algorithm/test/gather_test1.cpp	2013-02-25 17:31:52 EST (Mon, 25 Feb 2013)
@@ -55,14 +55,12 @@
 template <typename Container, typename Predicate>
 void test_iterator_types ( const Container &c, Predicate comp, std::size_t offset ) {
     typedef std::vector<typename Container::value_type> vec;
-    typedef forward_iterator<typename vec::iterator> FI;
+
     typedef bidirectional_iterator<typename vec::iterator> BDI;
     typedef random_access_iterator<typename vec::iterator> RAI;
     
     vec v;
     v.assign ( c.begin (), c.end ());
-    test_iterators ( FI  ( v.begin ()), FI  ( v.end ()), comp, offset );
-    v.assign ( c.begin (), c.end ());
     test_iterators ( BDI ( v.begin ()), BDI ( v.end ()), comp, offset );
     v.assign ( c.begin (), c.end ());
     test_iterators ( RAI ( v.begin ()), RAI ( v.end ()), comp, offset );