[boost] Interest in some Algorithms

Subject: [boost] Interest in some Algorithms
From: Dean Michael Berris (mikhailberis_at_[hidden])
Date: 2016-01-18 07:13:12

Hi Boost!

It’s been a while, I hope you all have been doing well.

I wanted to ask whether anybody’s interested in a couple of algorithms, to be made part of the Boost.Algorithm library.

One is tentatively named ‘set_inplace_difference' which has the following synopsis:

template <class I1, class I2>
I1 set_inplace_difference(I1 f1, I1 f2, I2 f2, I2 l2);

template <class I1, class I2, class C>
I1 set_inplace_difference(I1 f1, I1 f2, I2 f2, I2 l2, C comp);

It’s essentially a set_difference which re-uses the storage of the range [f1, l1). It takes elements from [f1, l1) that are in [f2, l2) and moves them to [p, l1) where p is the partition point (or the new “end”). This is best used in conjunction with “erase” on vectors and/or std::deque. These algorithms return p.

Another is tentatively named ‘set_inplace_intersection’ which instead of the above which does the difference, does an intersection instead.

Requirements on I1 and I2 are that they are RandomAccess iterators, and that they are sorted. I haven’t figured out whether partially-sorted is a sufficient condition. I also haven’t figured out whether it would work for weaker iterator classes, but so far my implementation relies on std::lower_bound and std::upper_bound.

If there’s enough interest, I can prepare a pull request after going through my employer’s open-source patching process.

Looking forward to hearing your thoughts!

Cheers