c++ - 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セットでansあり、空のセットです。

ソートされた範囲をセットに挿入することは線形であることを私は知っています。しかし、インサーターリニアを使用して挿入することもできますか？

Answer 1

インサーターは、各アイテムを最後に挿入した場所を記憶し、同じ場所に次のアイテムを挿入しようとします。適切な場所であれば、これはO（1）です。

つまり、ソートされた範囲をインサーターにコピーすることは全体的に線形であるため、ここで問題ありません。