distancia entre std :: set begin() y std :: set iterator en O (logn)

Question

Necesito encontrar el índice de un elemento en std :: set. Este índice se puede visualizar como la distancia del iterador desde el principio. Una forma puede ser:

for(int i = 0, set<int>::iterator it = s.begin(); it != iteratorToBeFound; ++it, ++i); 

Esto tiene claramente el tiempo O (n). Pero sabemos que la distancia desde la raíz en un árbol de búsqueda binaria implementado por el conjunto internamente se puede encontrar en O (log n) time.

¿Hay alguna manera de implementar lo mismo para encontrar el índice en el tiempo O (log n) en C++ establecido?

Answer 1

Puede utilizar ordenados std::vector<int> . Si está ordenado, puede encontrar el elemento en O(log n). Y puede encontrar la distancia en tiempo constante O(1).

por el vector ordenado quiero decir que después de cada inserción (o después de muchas inserciones) lo hace std::sort(v.begin(), v.end());

Si su tipo en el interior std::set<T> no es tan ligero como int - se puede mantener tanto - std::set<T> y ordenados vector de iteradores std::vector<std::set<T>::iterator> . Pero no podría ser trivial mantener estas estructuras sincronizadas. ¿Tal vez pueda agregar alguna posición similar al T? O mantenga std::set<std::pair<T,int>, comp_first_of_pair<T>> donde comp_first_of_pair es solo para tener set ordenado solo por T y el segundo int es para mantener la posición en el conjunto?

sólo algunas ideas - que tienen incluso O(1) tiempo de distancia ...

Answer 2

Puede utilizar la función std::set<>::find para buscar un elemento x y calcular el distance en el primer iterador del conjunto.

std::distance(s.begin(), s.find(x)) 

Sin embargo, como los comentarios indican el tiempo de ejecución de la distancia depende del tipo de iterador utilizado. En el caso de un conjunto, este es un iterador bidireccional y la distancia es O (n).

Answer 3

No puede usar matematics con iteradores bidireccionales. Entonces, solo la forma aceptable es contar usted mismo (cuántos int menos que X ha insertado en el conjunto).

Pero, si usted se ha separado limpiamente "recolección de datos" y "etapas de uso de datos" - probablemente vale la pena para reemplazar std :: set con ordenada std :: vector. Su más difícil de mantener, pero tienen beneficios propios, incluyendo matematics iterador (para que pueda obtener la búsqueda con O (log n) con std :: binary_search y la distancia con O (1))

Answer 4

Si el cálculo del índice es muy su cuello de botella, entonces veo 2 opciones:

• almacenar el índice. Ya sea en los nodos o en un std::map por separado. Por supuesto, esto significa que debe mantener este caché actualizado.
• Utilice un std::vector. Eso no es tan malo como podría parecer al principio. Si mantiene el vector siempre ordenado, puede usarlo como set. El rendimiento será similar al set. El mayor inconveniente es que el nodo puede copiarse mucho. (esto se puede compensar mediante el uso de punteros, boost:shared_ptr o std::unique_ptr [C++ 11 solamente])
  Para buscar un elemento que utilice std::lower_bound.
  En lugar de inserción/push_back haces: insert(lower_bound(b,e,x), x)