c++ test if 2 sets are disjoint

Question

I know the STL has set_difference, but I need to just know if 2 sets are disjoint. I've profiled my code and this is slowing my app down quite a bit. Is there an easy way to see if 2 sets are disjoint, or do I need to just roll my own code?

EDIT: I also tried set_intersection but it took the same time...

Answer 1

You could use set_intersection and test if the resulting set is empty, but I don't know if that's much faster.

The optimal implementation would stop the testing and return false as soon as the first equal element is found. I don't know of any ready-made solution for that, though

template<class Set1, class Set2> 
bool is_disjoint(const Set1 &set1, const Set2 &set2)
{
    Set1::const_iterator it, itEnd = set1.end();
    for (it = set1.begin(); it != itEnd; ++it)
        if (set2.count(*it))
            return false;

    return true;
}

isn't too complex and should do the job nicely.

EDIT: If you want O(n) performance, use the slightly less compact

template<class Set1, class Set2> 
bool is_disjoint(const Set1 &set1, const Set2 &set2)
{
    Set1::const_iterator it1 = set1.begin(), it1End = set1.end();
    if (it1 == it1End)
        return true; // first set empty => sets are disjoint

    Set2::const_iterator it2 = set2.begin(), it2End = set2.end();
    if (it2 == it2End)
        return true; // second set empty => sets are disjoint

    // first optimization: check if sets overlap (with O(1) complexity)
    Set1::const_iterator it1Last = it1End;
    if (*--it1Last < *it2)
        return true; // all elements in set1 < all elements in set2
    Set2::const_iterator it2Last = it2End;
    if (*--it2Last < *it1)
        return true; // all elements in set2 < all elements in set1

    // second optimization: begin scanning at the intersection point of the sets    
    it1 = set1.lower_bound(*it2);
    if (it1 == it1End)
        return true;
    it2 = set2.lower_bound(*it1);
    if (it2 == it2End)
        return true;

    // scan the (remaining part of the) sets (with O(n) complexity) 
    for(;;)
    {
        if (*it1 < *it2)
        {
            if (++it1 == it1End)
                return true;
        } 
        else if (*it2 < *it1)
        {
            if (++it2 == it2End)
                return true;
        }
        else
            return false;
    }
}

(modified Graphics Noob's modification further, using only operator <)

Answer 2

Use std::set_intersection, and see if the output is empty. You could check to see if the range of the two sets (area covered by the begin and end iterators) overlap first, but I suspect that set_intersection might already do this.

These are all O(n) operations, as is is_disjoint. If O(n) is unacceptable, you'll have to build some side storage to "keep track" of the disjoint-ness of the sets as you add/remove elements. Here, you would pay the overhead at insertion time (by updating your "isdisjoint" structure for each set modification), but is_disjoint could be implemented cheaply. This may or may not be a good tradeoff to make.

Answer 3

Modified hjhill's code to reduce complexity by a factor of O(log n) by getting rid of the count() call.

template<class Set1, class Set2> 
bool is_disjoint(const Set1 &set1, const Set2 &set2)
{
    if(set1.empty() || set2.empty()) return true;

    typename Set1::const_iterator 
        it1 = set1.begin(), 
        it1End = set1.end();
    typename Set2::const_iterator 
        it2 = set2.begin(), 
        it2End = set2.end();

    if(*it1 > *set2.rbegin() || *it2 > *set1.rbegin()) return true;

    while(it1 != it1End && it2 != it2End)
    {
        if(*it1 == *it2) return false;
        if(*it1 < *it2) { it1++; }
        else { it2++; }
    }

    return true;
}

I've complied and tested this code now so it should be good.