On Tue, Sep 16, 2025 at 8:58 PM Peter Neiss via Std-Proposals <
std-proposals_at_[hidden]> wrote:

>
> A better implementation is
> auto remove_missing = [](auto first1, auto last1, auto first2, auto
> last2, auto comp)
> {
> auto out = first1;
> while (first1 != last1 && first2 != last2)
> {
> if (comp(*first1, *first2))
> ++first1;
> else
> {
> if (!comp(*first2, *first1))
> *out++ = *first1++; // *first1 and *first2 are equivalent.
> else // THE else IS NEW
> ++first2;
> }
> }
> return out;
> };
>
> which has Complexity O(N+M).
>

Well what implementation is better depends on sizes of s1 and s2. If s1 is
1'000'000 elements and s2 is 50 elements binary_search(or even better
lower_bound if you remember last result) will be faster.
As for the remove_missing algorithm: as I said previously I believe what
you want is basically a stateful find in s1, and then you can use
std::erase_if/remove_if. One issue with erase_if is that it says on
cppreference that complexity is linear,
so there are no guarantees predicate will not be called 5 times for every
element, but reading the standard draft for vector it defers to remove_if
that has this more tightly specified so it should be fine.
Bigger issue is that left to right traversal is not guaranteed, although I
think all implementations do it like that, and left to right implementation
is required if you want to remember last lookup in s1.
So maybe it would be better to just require left to right traversal for
erase_if/remove_if.