The fastest way to find union of sets

Question

I have sets of pairs of int like set<pair<int,int> > x1, x2, ... xn ( n can be between 2 and 20). What is the fastest way to find union of those sets ?

Sorry If I wasn't make clear at the beginning, I meant fast in performance, memory allocation is not a problem.

Answer 1

Assuming that the result needs to be a set too, then you have no choice but to insert every element of each x_i into that result set. So the obvious implementation is:

set<pair<int,int>> x(x1);
x.insert(x2.begin(), x2.end());
// etc

The remaining question is whether this can be beaten for speed.

The single-element insert takes a position hint, which if correct speeds up insertion. So it might turn out that something like this is faster than x.insert(x2.begin(), x2.end());:

auto pos = x.begin()
for (auto it = x2.begin(); it != x2.end(); ++it) {
    pos = x.insert(pos, *it);
}

It depends on the data, though: that position may or may not be accurate. You can ensure that it is by putting all the elements in order before you start, for which the best tool is probably set_union. That might better be named merge_and_dedupe_sorted_ranges, because what it does has nothing particularly to do with std::set. You could either set_union into intermediate vectors, or else into sets like this:

set<pair<int,int>> x;
set_union(x1.begin(), x1.end(), x2.begin(), x2.end(), inserter(x, x.end());

My concern with using set_union is that in order to get the benefit of adding the elements to a set in increasing order, you need to create a new empty container each time you call it (because if it's not empty then the elements added need to interleave with the values already in it). The overhead of these containers might be higher than the overhead of inserting into a set in arbitrary order: you would have to test it.

Answer 2

Unfortunately, I believe that you are limited to a linear O(N) solution, as all a union would be is a combination of the elements in both sets.

template<typename S>
S union_sets(const S& s1, const S& s2)
{
     S result = s1;

     result.insert(s2.cbegin(), s2.cend());

     return result;
}