¿Cuál es la complejidad de set_intersection en C++?

Question

¿Cuál es la complejidad del siguiente código?

set<int> S1, S2, ans; 
set_intersection(S1.begin(), S1.end(), S2.begin(), S2.end(), inserter(ans, ans.begin())) 

donde S1 y S2 son algunos conjuntos NON_EMPTY y ans es un conjunto vacío.

Sé que la inserción de un rango ordenado en un conjunto es lineal; ¿pero está insertando también con el insertador lineal?

Answer 1

El insertador recuerda dónde insertó por última vez cada elemento e intenta insertar el siguiente en el mismo lugar. Este es O (1) si es el lugar correcto.

Lo que significa que copiar un rango ordenado al insertador es lineal en general, por lo que está bien aquí.