Boost logo

Boost :

Subject: Re: [boost] Interest in some Algorithms
From: Steven Watanabe (watanabesj_at_[hidden])
Date: 2016-01-18 15:32:23


On 01/18/2016 05:13 AM, Dean Michael Berris wrote:
> 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.

  Why do you need lower/upper_bound? set_difference
can be implemented easily with a straight linear
scan through the two sequences. In addition, it's
quite easy to implement set_difference in such a
way that result == first1 works, which effectively makes
it operate in place, although the standard forbids
such usage.

In Christ,
Steven Watanabe

Boost list run by bdawes at, gregod at, cpdaniel at, john at