What is the complexity of set_intersection in C ++?

Question

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 nonempty sets, and ans is an empty set.

I know that inserting a sorted range into a set is linear; but also inserts using linear insertion?

Answer 1

The paster remembers where he last inserted each element and tries to insert the next element in the same place. This is O (1) if it is in the right place.

This means that copying a sorted range into an insert is linear in general, so you're good here.