C++中set_intersection的复杂度是什么？

Question

10

以下代码的时间复杂度是多少？

set<int> S1, S2, ans;
set_intersection(S1.begin(), S1.end(), S2.begin(), S2.end(), inserter(ans, ans.begin()))

其中S1和S2是一些非空集合，ans是一个空集合。

我知道将排序的范围插入到集合中是线性的；但是使用插入器进行插入也是线性的吗？

- Farzam

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Alan Stokes · Accepted Answer

插入器会记住上次插入的位置，并尝试在相同的地方插入下一个项目。如果是正确的位置，这种操作的时间复杂度为O(1)。

这意味着将排序的范围复制到插入器中总体上是线性的，因此您可以放心使用。