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

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;
}