From the title you'd almost assuredly think use set_union
to create a list
and then check if it's empty. However, the objects I'm comparing are "expensive" to copy. I've loo开发者_开发技巧ked at includes
but that only works if all the items of one list are found in another. I've also looked at mismatch
but rejected it for obvious reasons.
I can and have written my own function which assumes both lists are sorted but I'm wondering if an efficient function already exists in the STL. (Project is forbidden to use third-party libraries including Boost and TR1, don't ask.)
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.
Is find_first_of()
what you're after?
精彩评论