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

The inserter remembers where it last inserted each item and tries to insert the next item at the same place. This is O(1) if it's the right place.

Which means copying a sorted range to the inserter is linear overall, so you're good here.