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.