Utility function: set_intersects

From: Joe Gottman (joegottman_at_[hidden])
Date: 2000-11-29 21:16:02

Often when I am working with sorted sets I need to know whether two sets
intersect but I don't need to know exactly what the intersection is.  I
could use std::set_intersection, but this is wasteful of both time and
space.  Here is what I think is a better function.  It doesn't require space
to save the intersection, and it returns as soon as a common element is
found.

namespace Boost {

   template <class Iterator1, class Iterator 2>
   bool set_intersects(Iterator1 begin1, Iterator1 end1,  Iterator2 begin2,
Iterator2 end2)
   {
        while ((begin1 != end1) && (begin2 != end2) ) {
             if (*begin1 < *begin2) {
                   ++begin1;
             } else if (*begin2 < *begin1) {
                   ++begin2;
             } else { //Equality
                    return true;
             }
       }
       return false;
}

   template <class Iterator1, class Iterator 2, class Compare>
   bool set_intersects(Iterator1 begin1, Iterator1 end1,  Iterator2 begin2,
Iterator2 end2, Compare comp)
   {
        while ((begin1 != end1) && (begin2 != end2) ) {
             if (comp(*begin1, *begin2)) {
                   ++begin1;
             } else if (comp(*begin2,*begin1)) {
                   ++begin2;
             } else { //Equality
                    return true;
             }
       }
       return false;
}