 # Boost :

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;
}