Sorry for the late reply, I missed this message! But I can confirm that the
changes I made to libc++'s `std::set_intersection` don't alter the aliasing
behavior in ways relevant to this discussion.

My (decidedly late) 2c is that, regardless of the sharp edges or additional
complexity in the specification of the function, I have a hard time seeing
the positive side of the change offsetting the additional constraints
imposed on library implementers. My impression is that everyone would lose
a little to unlock a rare use case, and one which wouldn't be hard to
implement outside of the standard library.

On Mon, 15 Sept 2025 at 21:10, Arthur O'Dwyer <arthur.j.odwyer_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. So for example we could write something like this:
>
> while (first1 != last1 && first2 != last2) {
> if constexpr
> (__builtin_lt_synthesizes_from_spaceship(decltype(*first1),
> decltype(*first2))) { // Nikolas's new compiler builtin, more or less
> auto rc = (*first1 <=> *first2);
> if (rc < 0) {
> ++first1;
> } else if (rc > 0) {
> ++first2;
> } else {
> *out++ = *first1; ++first1; ++first2;
> }
> } else {
> if (*first1 < *first2) {
> ++first1;
> } else if (*first2 < *first1) {
> ++first2;
> } else {
> *out++ = *first1; ++first1; ++first2;
> }
> }
> }
> return out;
>
> 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.
>
> –Arthur
>
>
> Am Mo., 15. Sept. 2025 um 00:26 Uhr schrieb Arthur O'Dwyer <
>> arthur.j.odwyer_at_[hidden]>:
>>
>>> On Sun, Sep 14, 2025 at 1:38 PM Arthur O'Dwyer <
>>> arthur.j.odwyer_at_[hidden]> wrote:
>>>
>>>> On Sun, Sep 14, 2025 at 1:08 PM Peter Neiss via Std-Proposals <
>>>> std-proposals_at_[hidden]> wrote:
>>>>
>>>>> Ok. I have not thought about overlapping input ranges. Classical
>>>>> aliasing problem. Modifying the first range at a later position, through
>>>>> the second maybe makes the range unsorted. But when I try to construct an
>>>>> example, the sorting seems to make this impossible and it still works out
>>>>> correctly.
>>>>> I am not familiar with weak comparators and when they are allowed in
>>>>> the stl. Is sorting by a weak comparator enough for a range to be sorted ?
>>>>> Please give an example that breaks with overlapping input ranges. If
>>>>> this is a problem inplace_set_intersection is a good idea, otherwise i
>>>>> would prefer changing the precondition on std::set_intersection.
>>>>>
>>>> [...]
>>>>
>>>>> If the input ranges overlap, the output can generally only coincide
>>>>>> with
>>>>>> the first range (the source for the copy). Otherwise you can get wrong
>>>>>> results with a weak comparator.
>>>>>
>>>>>
>>>> I don't think this is true. The output range could be the same as the
>>>> first input range, or it could be the same as the second input range, or it
>>>> could be unrelated, or it could start before either input range.
>>>> The output range obviously can't point into the *middle* of either
>>>> input range, but nobody was claiming that.
>>>>
>>>> I wonder if the term "overlap with" is ever actually defined in the
>>>> spec, or if there's an LWG issue about that. I think as the iterator type
>>>> becomes more complicated than just a simple pointer, and the element types
>>>> become more resource-managey and/or view-ish, "overlap" gets harder to
>>>> define. What we mean, of course(tm), is that while the algorithm is running
>>>> the values of all elements in the two input ranges must be stable and not
>>>> change for any reason. And how we want to loosen that restriction is to say
>>>> something like, the values of all *not-yet-read* elements in the two
>>>> input ranges must be stable and not change (along with some explanation of
>>>> when *does* the algorithm read each element).
>>>>
>>>
>>> ...Oh, I see — the problem is actually pre-existing, and happens when
>>> (A) the two *input* ranges overlap* each other* and (B) the type's
>>> "copying from input to output" operation is destructive/modifying.
>>> So we have something like this:
>>>
>>> // https://godbolt.org/z/TTn3f5E8P
>>>
>>> struct S {
>>> explicit S() = default;
>>> explicit S(int i) : p_(std::make_unique<int>(i)) {}
>>> friend bool operator<(const S& a, const S& b) {
>>> assert(a.p_ != nullptr);
>>> assert(b.p_ != nullptr); // this assertion will fail
>>> return *a.p_ < *b.p_;
>>> }
>>> std::unique_ptr<int> p_;
>>> };
>>>
>>> #define M(it) std::make_move_iterator(it)
>>>
>>> int main() {
>>> fprintf(stderr, "First input range starts in the middle of second:");
>>> {
>>> S a[4] = { S(2), S(2), S(4), S(5) };
>>> S out[4];
>>> auto dlast = std::set_intersection(M(a+1), M(a+4), M(a), M(a+3), out); //
>>> boom goes the dynamite
>>> assert(dlast == out + 2); // we never get here
>>> assert(*out[0].p_ == 2);
>>> assert(*out[1].p_ == 4);
>>> }
>>> }
>>>
>>> Here `out` does not "overlap" either the first input range or the second
>>> input range; but because the two input ranges overlap *each other*, and
>>> we're using a move_iterator, bad things happen.
>>>
>>> It might be very appreciated if someone were able to bring a paper
>>> codifying, in proper standardese, that set_intersection should do precisely
>>> what Vendors All Understand set_intersection actually, physically, does.
>>> Such a paper would incidentally both implement your feature request (that
>>> set_intersection should be specified to work when Vendors All Understand
>>> that it physically will) and also fix this defect (that set_intersection
>>> should be permitted to fail when Vendors All Understand it cannot possibly
>>> work, physically). However, I can't think of a sensible way to word that
>>> paper except to write something like
>>>
>>> Effects: Equivalent to:
>>> while (first1 != last1 && first2 != last2) {
>>> if (*first1 < *first2) {
>>> ++first1;
>>> } else if (*first2 < *first1) {
>>> ++first2;
>>> } else {
>>> *out++ = *first1; ++first1; ++first2;
>>> }
>>> }
>>> return out;
>>>
>>> We've had good success with that kind of specification in places like
>>> [specialized.algorithms]
>>> <https://eel.is/c++draft/uninitialized.construct.default>. I imagine
>>> such a paper wouldn't *sail* through, but it might work.
>>>
>>> my $.02,
>>> –Arthur
>>>
>>>>