Hello everyone,


I need to compute the intersection of two (or more) sets. I will use C or C++, but STL algorithms are not enabled to be used. I have Googled, but it seems that there are only union algorithms and no intersection algorithms.

It is not my homework, and it is my interest to improve the application I am working on now. Does anyone have any reference materials or any ideas of how to design the intersection operation of sets efficiently.


thanks in advance,
George

If your sets are sorted, then you can simply iterate through both of them at the same time. If the minimal elements are the same, put that in the intersection and advance the iterator on both sets. If they are not the same, then advance the iterator on the one with the smaller minimal element. You repeat with the rest of the set. This works since the smaller minimal element can't possibly be in the intersection.

In other words, if the sets are {x0, x1, ...} and {y0, y1, ...} in sorted order, the intersection can be defined recursively as:
if (x0 == y0)
then intersection = {x0} + intersection of {x1, x2, ...} and {y1, y2, ...}
else if (x0 < y0)
then intersection = intersection of {x1, x2, ...} and {y0, y1, ...}
else if (x0 > y0)
then intersection = intersection of {x0, x1, ...} and {y1, y2, ...}

How are you set elements stored internally?

If you have a limited number of members of the universe then the most efficient way to manage them is through bits.
If you have a reasonable number and the sets tend to be fairly full then array indices are the next best thing
If you have many member sin the universe with the sets having just a few members then you probably want something like a vector, and is possible as spooon suggested store them in some kind of order so that the set operations can be easily implemented.