Set_union/Set_intersect for more than two sets in c++

Question

I know those commands are for two sets.

Does there any simple and fast way to do this for more then two sets.

I think I can use some kind of loop for this but maybe there are better way.

Thank you

Answer 1

About the set_union:
If your containers are really std::set, you could make a loop through all sets, but not using set_union, you could select one of the sets and use insert (using begin() and end() iterators of the other sets). This way, you will not create many copies, because set_union return (iterator to ) a copy of the newly created set. If you don't want to modify any of the sets, you could create new one, an empty one, and start inserting all elements from all sets.
If you're not using sets, you could temporary create a std::set, use insert and then insert all elements into a new container from your type.
About set_intersect: you could use erase, but not using iterators, just going through all sets and through all elements, that they contain. But I'm not very sure if this will be faster that using set_intersect. Depends on how many sets do you have.
Hope that helped (:

Answer 2

If you are using sorted sets (like STL sets) you can do the union/intersection on all of them at once in one pass. If they're plain sets, I don't think you can do better than combining them one at a time.

Answer 3

For set union, if you are going to see which of M sets has the smallest value that will take M-1 comparisons. So now we pop off this value and go again. If N is the total number items in all the sets our algorithm this way is O(NM) (ignore that it's M-1 for Big-O notation).

Where we might be able to optimise is as follows: If we sort the lowest element of each set: Now we pop one off the front, but from that set we just need an O(logM) insertion into our new sorted fronts. We do this for each item so our algorithm is O(N logM).

Note that if you have 3 you probably gain nothing. If you have 8 such sets it certainly could show a gain.

For set-intersection we are looking only for values that appear in all our sets. We know they are all the same if the minimum is the same as the maximum. We can pop off and discard the smaller values if they are not then once again insert each time the one that is next. If so we add to our result then pop from each list. Either way we still will have O(N logM)