Set_union/Set_intersect for C++中的两个以上的集合

Question

我知道这些命令是针对两个集合的。

请问有没有简单，快捷的方式了两个多套这样做。

我想我可以用某种循环的这个，但也许有更好的办法。

谢谢

Answer 1

对于并集，如果你会看到其中的M组有将M-1的比较中的最小值。所以，现在我们流行过这个值如果N是所有集合中的项目总数，我们的算法就是O（NM）（忽略它是Big-O表示法的M-1）

我们可以优化的地方是如下所示：如果我们排序最低的元素每个集合的t：现在我们从前面弹出一个，但是从这个集合中，我们只需要在我们新分类的前端插入O（logM）。我们为每个项目做这个，所以我们的算法是O（N logM）。

请注意，如果你有3个你可能一无所获。如果你有8个这样的套装，它当然可以显示出收益。

对于集合交叉，我们正在寻找只为出现在我们所有的值集。如果最小值与最大值相同，我们知道它们都是相同的。我们可以弹出并丢弃较小的值，如果它们不再次插入下一个。如果是这样，我们添加到我们的结果然后从每个列表中弹出无论哪种方式，我们仍然会有O（N logM）

Answer 2

关于set_union：
如果你的容器是真正的std ::集，你可以通过所有组进行循环，但不使用set_union，你可以选择集和使用插入（使用其他集合的begin（）和end（）迭代器）。这样，你将不是创建许多副本，因为set_union返回（迭代器）到新创建的集合的副本。如果你不想修改任何集合，你可以创建一个新的集合，并且开始插入所有集合中的所有元素。
如果你不使用集合，你可以临时创建一个std :: set，使用insert，然后将所有元素插入到你的类型的新容器中。
关于set_intersect：你可以使用擦除，但不使用迭代器，只是通过所有集合，并通过所有元素去，它们包含。但我不太确定使用set_intersect会更快。取决于你有多少套。
希望这有助于（：

Answer 3

如果您正在使用的有序集合（如STL套），你可以一次做工会/交集上所有的人立刻如果他们是普通的台，我不知道。觉得你可以做的比他们一次一个结合较好。