If the sets are unsorted, then you can use find_first_of
for an O(N*M) algorithm.
If they are sorted (which would be required for set_intersection
anyway), then you can iterate over one set calling equal_range
in the other for every element. If every returned range is empty, there is no intersection. Performance is O(N log M).
However, there is no excuse not to have O(N+M) performance, right? Nothing is copied by set_intersection
if it's passed a dummy iterator.
struct found {};
template< class T > // satisfy language requirement
struct throwing_iterator : std::iterator< std::output_iterator_tag, T > {
T &operator*() { throw found(); }
throwing_iterator &operator++() { return *this; }
throwing_iterator operator++(int) { return *this; }
};
template< class I, class J >
bool any_intersection( I first1, I last1, J first2, J last2 ) {
try {
throwing_iterator< typename std::iterator_traits<I>::value_type > ti;
set_intersection( first1, last1, first2, last2, ti );
return false;
} catch ( found const& ) {
return true;
}
}
This provides for early exit. You could alternately avoid the exception and just have the iterator remember how many times it was incremented, and no-op the assignment.