I agree with Arthur that std::set_intersection is equivalent to this specific algorithm implementation:
while (first1 != last1 && first2 != last2) {
if (*first1 < *first2) {
} else if (*first2 < *first1) {
*out++ = *first1; ++first1; ++first2;
}
}
return out;
It is not easy to analyse this algorithm with weak ordering and arbitrarily overlapping input and possible output ranges. To just standardise the algorithm is a smart move.
Add some remarks to when it works. E.g. nonoverlapping ranges and strong ordering. Or First range overlap with output range, etc.
I don't feel up to the task of writing a proposal, but I am willing to help and give my opinion.
...Although, I see that libc++'s `std::set_intersection` is actually cleverer than that, for forward iterators specifically. This was done by Iúri Chaer in July 2024:
At a glance, I think this clever algorithm still preserves all the aliasing behavior of the algorithm above. That is, it doesn't make anything undefined that would have been well-defined with the simpler algorithm. That is, it doesn't introduce a dependency on any of the preconditions Peter's objecting to. But maybe Iúri (cc'ed) can confirm?
It also occurs to me that Nikolas Klauser has been working on a compiler-assisted approach to replacing paired `<`s with `<=>` when that is equivalent.
This is very cool, recently there
was question on S0 why set calls <=> twice on target element.
This means that for a type like `std::string`, we would do the-moral-equivalent-of-memcmp only once per step, rather than twice; which is a huge speedup.
So any specification effort would need to avoid implying that we actually call `<` a certain number of times, or actually call `++` a certain number of times. That makes the specification effort a fair bit harder, I think.
I still do not follow why would we want to make specification of algorithm so much harder to read for beginners for some very rare usecase(although to be fair std::set_intersection is rare anyway so it is not a such rare case when we focus on std::set_intersection use cases), not to mention that violation of requirement can no longer be easily checked(i.e. just check out is not in range 1 or range 2 when all 5 iterators are pointers)...
Why just not make stateful search work fine by specifying exactly number of comparisons erase_if does to be size of input range of erase_if?
e.g.
(code is not generic and uses ==, but I hope idea is clear)
This may have bad performance since it keeps restoring/checking iterator state, but I did not have time to benchmark.