C++ 中 set_intersection 的复杂度是多少？
以下代码的复杂度是多少？
set<int> S1, S2, ans;
set_intersection(S1.begin(), S1.end(), S2.begin(), S2.end(), inserter(ans, ans.begin()))
其中 S1 和 S2 是一些非空集，ans 是一个空集。
我知道将排序范围插入到集合中是线性的；但是使用插入器插入也是线性的吗？
What is the complexity of the following code?
set<int> S1, S2, ans;
set_intersection(S1.begin(), S1.end(), S2.begin(), S2.end(), inserter(ans, ans.begin()))
where S1 and S2 are some non_empty sets and ans is an empty set.
I know that inserting a sorted range into a set is linear; but is inserting using inserter linear too?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
插入器会记住最后插入每个项目的位置，并尝试在同一位置插入下一个项目。如果位置正确的话，这是 O(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.