9

How do I check for the empty intersection of two std::sets? I can use set_intersection, but that's unnecessarily slow, I need only bool answer.

Remark: std::set means ordered sets, they are of the same type etc.

yo'
  • 811
  • 11
  • 22
  • Duplicate of http://stackoverflow.com/questions/1964150/c-test-if-2-sets-are-disjoint unless question is "do we have appropriate algorithm in STL?" – ony Mar 18 '15 at 13:11

1 Answers1

11

Anything wrong with just coding it yourself?

bool empty_intersection(const set<int>& x, const set<int>& y)
{
    set<int>::const_iterator i = x.begin();
    set<int>::const_iterator j = y.begin();
    while (i != x.end() && j != y.end())
    {
      if (*i == *j)
        return false;
      else if (*i < *j)
        ++i;
      else
        ++j;
    }
    return true;
}

Something like that anyway. Completely untested code.

plauer
  • 175
  • 1
  • 12
john
  • 85,011
  • 4
  • 57
  • 81
  • 1
    I've been working with iterators only for 2 days and I'm happy to be able to do what I'm able to do. – yo' Oct 17 '12 at 18:10
  • OK, the algorithm above is similar to that used by set_intersection except that it immediately returns false if it finds a common element. Obviously it relies on the fact that sets are sorted, so if you increment the lower valued iterator only each time round the loop you will find all the common elements. – john Oct 17 '12 at 18:13
  • Thanks a lot. I think I'm able to read this, I'm just not able to code such thing myself. – yo' Oct 17 '12 at 18:14
  • 4
    You can make one subtle change to remove the requirement for `operator==`: `if(*i<*j) ++i; else if(*j<*i) ++j; else return false;` – Mark Ransom Oct 17 '12 at 18:31