Is it possible to use `std::set_intersection` to check if two sets have any element in common?

Question

std::set_intersection allows me to retrieve all elements in common between two std::set instances by outputting elements to an output iterator. In my particular situation, I am only interested in checking whether or not two sets have any element in common.

My current solution is using boost::function_output_iterator to set a bool variable as follows:

bool b{false};
set_intersection(begin(s0), end(s0),
                 begin(s1), end(s1),
                 make_function_output_iterator([&](const auto&){ b = true; }));
return b;

Unfortunately, this solution does not return early if a match is found: the sets have to be traversed entirely (i.e. no early return / short-circuiting).

Is it possible to use set_intersection with early return? The only solution I can think of is throwing an exception from the function_output_iterator function object, which is a terrible idea.

If not, is there anything else in the Standard Library that can help me, or am I forced to reimplement set_intersection? Bonus question: how would set_intersection's interface look like if it allowed early termination (i.e. what is the "most general" interface a Standard Library algorithm could have)?

Answer 1

Well, being “forced” to reimplement std::set_intersection isn’t such a bad thing. <g> It’s only about five lines of code:

template <class I1, class I2>
bool have_common_element(I1 first1, I1 last1, I2 first2, I2 last2) {
    while (first1 != last1 && first2 != last2) {
        if (*first1 < *first2)
            ++first1;
        else if (*first2 < *first1)
            ++first2;
        else
            return true;
    }
    return false;
}

Okay, a bit more than 5 lines. But painless.

Answer 2

This simple algorithm should do it:

Features:

• complexity: At most K=max(N, M) iterations where N is distance(first1, last1), and M is distance(first2, last2)
• short circuits
• works with any sorted range
• predicate can be replaced

 

#include <set>
#include <ciso646>
#include <iostream>
#include <cassert>
#include <functional>

template<class I1, class I2, class Comp = std::less<> >
bool has_element_in_common(I1 first1, I1 last1, I2 first2, I2 last2, Comp&& comp = Comp())
{
    while (first1 != last1 and first2 != last2)
    {
        if (comp(*first1, *first2))
        {
            ++first1;
        }
        else if (comp(*first2, *first1))
        {
            ++first2;
        }
        else
        {
            return true;
        }
    }

    return false;
}


int main()
{
    auto s1 = std::set<int> { 1, 3, 5, 7, 9 };
    auto s2 = std::set<int> { 2, 3, 4, 6, 8 };

    assert(has_element_in_common(begin(s1), end(s1), begin(s2), end(s2)));

    auto s3 = std::set<int> { 2, 4, 6, 8 };

    assert(!has_element_in_common(begin(s1), end(s1), 
                                  begin(s3), end(s3)));

}

It'll need a little work if you want to optimise it to skip duplicates in multisets.