Какова сложность set_intersection в C ++?

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), если это правильное место.

Это означает, что копирование отсортированного диапазона в устройство вставки в целом линейно, так что вы хорошо здесь.