C++中set_intersection的复杂性是什么？
C++中set_intersection的复杂性是什么？
提问于 2012-02-10 15:29:28
下面代码的复杂度是多少？
set<int> S1, S2, ans;
set_intersection(S1.begin(), S1.end(), S2.begin(), S2.end(), inserter(ans, ans.begin()))其中S1和S2是一些non_empty集合，而ans是空集。
我知道将已排序的范围插入到集合中是线性的；但是使用插入器插入也是线性的吗？
回答 1
Stack Overflow用户
回答已采纳
发布于 2012-02-10 15:45:50
插入器记住它最后一次插入每一项的位置，并尝试在同一位置插入下一项。如果它是正确的位置，这是O(1)。
这意味着将排序的范围复制到插入器总体上是线性的，所以在这里很好用。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/9224253
复制相关文章
相似问题
腾讯云开发者
