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

I assume with fast you mean fast to implement.

Then: std::set_union (*)

Example for two sets:

#include <set>
#include <algorithm>
#include <iterator>
using namespace std;

int main () {
    set<pair<int,int> > a, b, uni;
    set_union (a.begin(), a.end(),
               b.begin(), b.end(),
               inserter(uni, uni.begin()));

}

for n sets, hand writing it might be the most maintainable solution:

#include <set>
#include <vector>
using namespace std;

int main () {
    vector<set<pair<int,int>>> sets;
    set<pair<int,int>> uni;

    for (const auto &s : sets)
        for (const auto &elem : s)
            uni.insert (elem);
}

though in general, one should prefer standard algorithms and profit from their quality implementation.

If by fast you mean performance, we can't help as we don't have the requirements. Different approaches might give different results for different circumstances.

---

(*) note: the site is frowned upon sometimes for not being 100% accurate vs. the standard