CODEWITHSUNDEEP
c++algorithm
Mikhail
Mikhail

Reputation: 21749

Compute two set differences A\B and B\A in one pass

If I have a set represented as a sorted range, I can use std::set_difference to compute A\B and std::set_symmetric_difference to compute A\B U B\A. What if I want to compute both distinct sets A\B and B\A?

Of course, I can run std::set_difference twice, but this does not seem very elegant (and not even possible if we have e.g. input iterators). It is also pretty easy to write my own implementation, but I wonder whether there is a ready solution for this task?

Upvotes: 2

Views: 83

Answers (1)

amit
amit

Reputation: 178441

If your sets are both sorted it can be done in one pass using two iterators:

  • If the pointed element is in both sets, increase both
  • else if the element pointed by A's iterator is smaller, produce it to A\B, and increase A's iterator.
  • else, increase produce B's element to B\A and increase B's iterator.

C++ like Pseudo code:

iter1 = A.begin();
iter2 = B.begin();
while (iter1 != A.end() && iter2 != B.end()) { 
  if (*iter1 == *iter2) { 
    // don't produce anything
    ++iter1; ++iter2;
  } else if (*iter1 < *iter2) { 
    // produce *iter1 to A\B
    ++iter1;
  } else { 
    //produce *iter2 to B\A
    ++iter2;
  }
}

while (iter1 != A.end()) {
  //produce element to A\B
  ++iter1;
}
while (iter2 != B.end()) {
  //produce element to B\A
  ++iter2;
}

Upvotes: 2

Related Questions