¿Cuál es la complejidad del tiempo de iteración a través de std::set/std::map? Creo que es lineal en el tamaño del conjunto/mapa, pero no tan seguro. ¿Está especificado en el estándar de idioma?¿Cuál es la complejidad del tiempo de iteración a través de un estándar :: set/std :: map?
En el draft C++11 standard N3337 la respuesta se puede encontrar en el § 24.2.1 párrafo 8:
Todas las categorías de iteradores requieren sólo aquellas funciones que son de realización para una categoría dada en tiempo constante (amortizado).
Desde cada operación en un iterador debe ser constante de tiempo, la iteración a través n elementos deben ser O(n).
Si el mapa/conjunto se implementa como un árbol binario con punteros padres, la iteración a través de todos los elementos visitará cada nodo de árbol como máximo 3 veces. Si la implementación es un árbol b con punteros padres, cada nodo se visitará como máximo 2 * n + 1 veces, n la cantidad de elementos en el nodo. En ambos casos, esto implica una complejidad de tiempo promedio constante para cada paso de iteración. No conozco ninguna otra forma compatible de implementar map/set. – WaltK
Creo que es lineal en el tamaño del conjunto/mapa, pero no tan seguro.
Eso es correcto. Iteración a través de un sistema entero o mapa es O(N)
La iteración de un contenedor completo siempre será 'O (n)' _al least_ (supongo que implementaciones realmente tontas podrían hacer que _worse_) – Chad
Cuando dice "iterando a través de", ¿exactamente qué quiere decir? ¿Estás escribiendo un ciclo while/for utilizando un iterador estándar? ¿Estás usando uno de los algoritmos estándar? –