[Boost-bugs] [Boost C++ Libraries] #2578: Add double-bounded version of outputting algorithms

Subject: [Boost-bugs] [Boost C++ Libraries] #2578: Add double-bounded version of outputting algorithms
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2008-12-09 08:21:35

#2578: Add double-bounded version of outputting algorithms
--------------------------------------+-------------------------------------
 Reporter:  dlwalker                  |       Owner:                
     Type:  Feature Requests          |      Status:  new           
Milestone:  Boost 1.38.0              |   Component:  None          
  Version:  Boost 1.37.0              |    Severity:  Not Applicable
 Keywords:  algorithm iterator bound  |  
--------------------------------------+-------------------------------------
 (I thought there was an algorithms component.  But I don't see it, so I
 left the "Component" field as "None.")

 Many of the standard algorithms transfer data from one sequence to
 another, using iterators to define the bounds of said sequences.
 Parameters for such sequences always include the beginning iterator.  But,
 frequently, only the first sequence has its ending iterator also passed;
 all the other sequences are assumed to be at least as long as the first
 one.  Confirming this is essential for robustness, and sometimes
 determining the length of a sequence relative to another in advance is
 non-trivial.  (It may involve manual counting through iterating over the
 whole sequence, which could be slow.  And it could be devastating if one
 of  the measured sequences is single-pass.)

 The alternative is to make algorithms that take both the beginning and
 ending iterators for every sequence and automatically stop as soon as any
 of them end.  Obviously, this cannot work with output iterators, and such
 sequences need to work with forward (or above) iteration instead.  For
 instance, `std::copy` can go from:

 {{{
 template < typename InIter, typename OutIter >
 OutIter  copy( InIter b, InIter e, OutIter o )
 { while ( b != e )  *o++ = *b++; return o; }
 }}}

 to:

 {{{
 template < typename InIter, typename ForIter >
 pair<bool, ForIter>  copy_db( InIter sb, InIter se, ForIter db, ForIter de
 )  {
     while ( sb != se && db != de )
         *db++ = *sb++;
     return make_pair( sb == se, db );
 }
 }}}

 The first sequence may be a single-pass input-iterator, so it can only
 return a Boolean flag if it reached its end.  The second sequence must be
 (at least) a forward-iterator, so a copy of the updated iterator can be
 returned.

 Examples from the (C++ 2003) standard that could use such adaptations are:
 `equal`, `mismatch`, `copy`, `copy_backward`, `transform`, `swap_ranges`,
 `replace_copy`, `replace_copy_if`, `remove_copy`, `remove_copy_if`,
 `unique_copy`, `reverse_copy`, `rotate_copy`, `merge`, `set_union`,
 `set_intersection`, `set_difference`, `set_symmetric_difference`,
 `inner_product`, `partial_sum`, and `adjacent_difference`.  (Some return
 types may vary.)

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/2578>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.