On Sep 14, 2012, at 2:36 AM, Jens Müller <blog@tessarakt.de> wrote:
Hi everyone,
I'm trying to test whether two std::vector's intersect.
When you say, "intersect", I interpret that to mean "Have any elements in common"
A straightforward way is to sort them, apply std::set_intersection and test whether the result set is non-empty.
However, I don't need the result. Is there some algorithm in boost that just _tests_ for intersection, i.e., stops when it has found one common element?
I don't know of one, but it should be simple to write: Here's a brute force implementation (uncompiled code): bool any_elements_in_common ( first1, last1, first2, last2 ) { for ( auto f = first1; f != last1; ++f ) if ( find ( first2, last2, *f ) != last2 )) return true; return false; // no elements in common } You can cut down the search time if you can sort the first vector (or whatever it is), and then use std::binary_search bool any_elements_in_common ( first1, last1, first2, last2 ) { std::sort ( first2, last2 ); for ( auto f = first1; f != last1; ++f ) if ( std::binary_search ( first2, last2, *f ) != last2 )) return true; return false; // no elements in common } Alternately, if you can afford the space to make a copy of the first set, then you could use std::set: bool any_elements_in_common ( first1, last1, first2, last2 ) { std::set<int> s (first2, last2); for ( auto f = first1; f != last1; ++f ) if ( s.find ( f ) != s.end ()) return true; return false; // no elements in common } Note that neither of these actually requires that the data be stored in a vector. -- Marshall Marshall Clow Idio Software <mailto:mclow.lists@gmail.com> A.D. 1517: Martin Luther nails his 95 Theses to the church door and is promptly moderated down to (-1, Flamebait). -- Yu Suzuki