On 9/15/25 23:10, Arthur O'Dwyer via Std-Proposals wrote:
>
> ...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 <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?
>

Another possible optimization for bidirectional iterators is to "test
for equality backward":

    template <
        std::bidirectional_iterator I1, std::sentinel_for<I1> S1,
        std::bidirectional_iterator I2, std::sentinel_for<I2> S2,
        std::weakly_incrementable O,
        class Comp = std::ranges::less
>
    O set_intersection (
        I1 first1, S1 last1,
        I2 first2, S2 last2,
        O out,
        Comp comp = {}
    ) {
        while (first1 != last1 && first2 != last2) {
            if (comp (*first1, *first2)) {
                ++first1;
            } else {
                I2 i = first2;
                I2 j = first2;

                for (++i; i != last2 && ! comp (*first1, *i); ++i)
                    j = i;

                for (; ! comp (*j, *first1); --j) {
                    *out++ = *first1++;

                    if (first1 == last1 || j == first2)
                        break;
                }

                first2 = i;
            }
        }

        return out;
    }

Compared to the simple approach, this has the advantage of not requiring
two comparisons each time `*first2 < *first1`, while only requiring
double-traversal for the copied elements. How this compares to binary
search depends on the input, but it can be significantly better for
random input: https://godbolt.org/z/MaTE3rTGc