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一些non_empty集和ans是空集。

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

Answer 1

插入器会记住它最后插入每个项目的位置，并尝试将下一项插入到相同的位置。这是O（1）如果它是正确的地方。

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