Re: [boost] Interest in some Algorithms

Subject: Re: [boost] Interest in some Algorithms
From: Michael Marcin (mike.marcin_at_[hidden])
Date: 2016-01-28 22:28:59

I have this algorithm in my toolkit and occasionally it is very useful 
so I wouldn't mind seeing it in boost.

FWIW here's my implementation

/// Removes elements from the first sorted range which
/// are present in the second sorted range.
/// Returns an iterator the the new end of the first range.
///
/// If there are multiple occurrences of a value the difference
/// includes as many occurrences of a given value as exist in
/// the first range, minus the amount of matching elements in the
//// second, preserving order.
template< typename I1, typename I2 >
I1 set_inplace_difference( I1 f1, I1 l1, I2 f2, I2 l2 ) {
     // skip in-place elements
     for ( ;; ) {
         if ( f1 == l1 || f2 == l2 ) {
             return l1; // no elements to remove
         } else if ( *f1 < *f2 ) {
             ++f1;
         } else if ( *f2 < *f1 ) {
             ++f2;
         } else {
             break; // found an out of order element
         }
     }

     // move elements that are not in the second range
     // i.e. remove elements that ARE in the second range
     I1 o = f1;
     for ( ++f1, ++f2; f1 != l1 && f2 != l2; ) {
         if ( *f1 < *f2 ) {
             *o = std::move( *f1 );
             ++o;
             ++f1;
         } else if ( *f2 < *f1 ) {
             ++f2;
         } else {
             ++f1;
             ++f2;
         }
     }

     // move the remaining elements
     o = std::move( f1, l1, o );
     return o;
}