Just a thought; can't we utilise concepts in some nice way here so that if
we use a custom comparator for these algorithms, we are allowed to return a
"three-way-compare"-object instead of a bool to further be able to get the
aforementioned speedup related to comparison?

// Robin

On Tue, Sep 16, 2025, 09:26 Ivan Matek via Std-Proposals <
std-proposals_at_[hidden]> wrote:

>
>
> On Mon, Sep 15, 2025 at 10:10 PM Arthur O'Dwyer via Std-Proposals <
> std-proposals_at_[hidden]> wrote:
>
>> On Mon, Sep 15, 2025 at 3:06 PM Peter Neiss <peter.stefan.neiss_at_[hidden]>
>> wrote:
>>
>>> I agree with Arthur that std::set_intersection is equivalent to this
>>> specific algorithm implementation:
>>> while (first1 != last1 && first2 != last2) {
>>> if (*first1 < *first2) {
>>> ++first1;
>>> } else if (*first2 < *first1) {
>>> ++first2;
>>> } else {
>>> *out++ = *first1; ++first1; ++first2;
>>> }
>>> }
>>> return out;
>>>
>>> Back in the day a defect report on set algorithm
>>> https://cplusplus.github.io/LWG/issue291 was solved it seems to retain
>>> this algorithm.
>>> 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:
>> https://github.com/llvm/llvm-project/pull/75230
>> 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
> <https://stackoverflow.com/questions/79760145> 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.
> https://godbolt.org/z/KcedMvKaj
> (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.
>
>
>
>
> --
> Std-Proposals mailing list
> Std-Proposals_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals
>