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

Question

std::set_intersection allows me to retrieve all the elements common between two instances of std::set , outputting the elements to the output iterator. In my specific situation, I'm only interested in checking for the presence or absence of two elements in common .

My current solution uses boost::function_output_iterator to set the 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 will not return earlier if a match is found: the sets must be completed in their entirety (i.e. early return / short circuit).

Is it possible to use set_intersection with early return? The only solution I can think of is to exclude the function_output_iterator function_output_iterator from the 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 override set_intersection ? Bonus question: what would the set_intersection interface look like if it allowed early termination (ie What is the “most common” interface that the standard library algorithm can have)?

Answer 1

Well, being “forced” to override std::set_intersection not so bad. <g> Its 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; } 

Ok, a little more than 5 lines. But painlessly.

Answer 2

This simple algorithm should do this:

Features:

• complexity: no more than K = max (N, M) iterations, where N is the distance (first1, last1), and M is the distance (first2, last2)
• short circuits
• works with any sorted range
• can replace the predicate

 #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))); } 

This will require a little work if you want to optimize it to skip duplicates in multisets.

Answer 3

you can throw an exception, although the overhead of the exception is big ... and according to the programming style you shouldn't use it like this:

 bool find=false; try{ set_intersection(begin(s0), end(s0), begin(s1), end(s1), make_function_output_iterator([&](const auto&){throw true;})); }catch{ find= true; }