c++ - 找到集合并集的最快方法

Question

我有成对的 int 像 set<pair<int,int> > x1, x2, ... xn (n 可以在 2 到 20 之间)。找到这些集合并集的最快方法是什么？

对不起，如果我一开始没有说清楚，我的意思是性能快，内存分配不是问题。

Answer 1

假设结果也需要是一个集合，那么您别无选择，只能将每个 x_i 的每个元素插入该结果集中。所以显而易见的实现是:

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

剩下的问题是这是否可以在速度上被击败。

单元素insert 采用position 提示，如果正确 会加快插入速度。所以它可能证明这样的事情比 x.insert(x2.begin(), x2.end());:

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

不过，这取决于数据:该位置可能准确，也可能不准确。您可以通过在开始之前将所有元素按顺序排列来确保它是，最好的工具可能是 set_union。最好将其命名为 merge_and_dedupe_sorted_ranges，因为它所做的与 std::set 没有特别的关系。您可以将 set_union 放入中间 vector ，或者放入这样的集合:

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

我对使用 set_union 的担忧是，为了获得将元素按递增顺序添加到集合中的好处，每次调用它时都需要创建一个新的空容器(因为如果它不是空的，那么添加的元素需要与其中已有的值交错)。这些容器的开销可能高于以任意顺序插入集合的开销:您必须对其进行测试。