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

Question

以下代码的复杂性是什么？

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

where S1和S2是一些non_empty集,ans是一个空集.

我知道将一个排序范围插入一个集合是线性的; 但是也使用插入线性插入？

Answer 1

插入器会记住它最后插入每个项目的位置,并尝试将下一个项目插入到同一位置.这是O(1),如果它是正确的地方.

这意味着将排序范围复制到插入器是整体线性的,所以你在这里很好.