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:
> Its been a while, I hope you all have been doing well.
> I wanted to ask whether anybodys 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);
> Its 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 havent figured out whether partially-sorted is a sufficient condition. I also havent 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk