¿Cuál es la diferencia de rendimiento entre el uso de un iterador para recorrer un mapa STL, frente a un vector? Me gustaría utilizar la clave del mapa para la inserción, eliminación y algunos accesos, pero también necesito hacer accesos regulares al cada elemento en el mapa.¿Rendimiento de acceso del iterador para el mapa STL frente al vector?
Con mapa y vector, iterar a través de toda la colección es O (N). sin embargo (como el vector de la lista contra el vector) almacena elementos contiguamente, por lo que acceder al siguiente elemento es mucho más económico porque usará el caché de manera óptima, mientras que el mapa no lo hará.
Pero dado que necesita para buscar basado en las claves, no hay realmente una alternativa. Podría usar un vector de pares ordenados en el primer elemento, pero si la colección debe ser mutable, esto será muy lento. Solo usa un mapa.
Utilice el mapa si necesita acceso rápido mediante la tecla. De lo contrario, use vector todo el tiempo a menos que se descubran algunos problemas de rendimiento con Profiler.
Iterar a través de cada elemento de un mapa toma O (n) tiempo. wikipedia
No sé por qué alguien votó negativamente. Es verdaderamente O (N) para atravesar todo el árbol. –
Sería bueno si mostrara quién votó. –
Para hacer una sangrienta venganza? :) –
Navegar por el árbol no es costoso (grosso modo como seguir una lista vinculada), no se beneficiará tanto del caché con un vector, pero generalmente es lo que hace cuando itera que es caro, no el iteración en sí.
¿Podría decirnos más sobre lo que espera hacer cuando recorre todo el mapa?
tiene una buena tabla de rendimiento para varias operaciones en todos los contenedores STL.
En general, si necesita realizar muchas operaciones de inserción, eliminación o búsqueda basadas en una clave, entonces el mapa es el camino a seguir.
Si solo necesita configurar el contenedor una vez y luego acceder a él como una matriz, utilice un vector.
EDIT: Tabla de rendimiento de las operaciones de contenedores STL:
Hay una sutileza en la pregunta. El usuario no desea acceder a un elemento, sino a _todos elementos en el mapa. El análisis del costo amortizado arroja O (N) para todo el mapa transversal (cada borde del árbol se cruza solo dos veces, una vez hacia abajo, una vez hacia arriba). –
El enlace está roto. Supongo que debería ser: http://devmentor.org/references/stl/stl.php –
¿Por qué insertar cabeza para vector es n/a y eliminar cabeza para vector es O (1)? Ambos deberían ser O (n). Y el vector de búsqueda es O (log n)? Hay algo mal allí. – Slava
iteración a través de un mapa puede ser lineal pero en la práctica, no es tan eficiente de las implementaciones en C++. Entonces mi consejo es usar un vector y usar otro mapa para ubicar los elementos en el vector en tiempo lineal.
El acceso de cada elemento en el mapa es algo más importante, ya que se va a disparar frecuentemente, pero aún necesito una búsqueda razonablemente rápida basada en claves (puedo cumplir ese requisito, pero las cosas se pondrán irracionales). El mapa parece ser el más adecuado, según la respuesta anterior de Greg Rogers. –