c++ - C++ 中 set_intersection 的复杂度是多少？

Question

下面代码的复杂度是多少？

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

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

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

Answer 1

插入器会记住上次插入每个项目的位置，并尝试在同一位置插入下一个项目。如果位置正确，则为 O(1)。

这意味着将排序的范围复制到插入器总体上是线性的，所以你在这里很好。