Eficiencia de iteradores en unordered_map (C++)

Question

Parece que no puedo encontrar ninguna información al respecto, así que me dirijo a stackoverflow. ¿Qué tan eficientes son los iteradores de std :: tr1 :: unordered_map en C++? Especialmente en comparación con, por ejemplo, enumerar iteradores. ¿Tendría sentido crear una clase contenedora que también contenga todas las claves en una lista para permitir una iteración eficiente (mi código usa mucha iteración sobre las claves en un mapa desordenado). Para aquellos que recomendarán impulsar, no puedo usarlo (por las razones que sean).

Answer 1

El iterador unordered_map básicamente solo tiene que caminar sobre la estructura de árbol interna de la tabla hash. Esto solo significa hacer algunos seguimientos de puntero, por lo que debería ser bastante eficiente. Por supuesto, si está caminando mucho por un mapa desordenado, puede estar utilizando la estructura de datos incorrecta en primer lugar. En cualquier caso, la respuesta a esto, como lo es para todas las preguntas de rendimiento, es que tengas el tiempo de tu código específico para ver si es lo suficientemente rápido.

Answer 2

No he comprobado TR1, pero N3035 (C++ 0x proyecto) dice lo siguiente:

Todas las categorías de iteradores requieren sólo aquellas funciones que son de realización para una categoría dada en constante tiempo (amortizado). Por lo tanto, las tablas de requisitos para los iteradores no tienen una columna de complejidad.

La norma no se va a dar una garantía de eficiencia que no sea en términos de complejidad, por lo que no tienen comparación garantizado de listunordered_map y aparte de eso los dos son amortizados constante de tiempo (es decir, el tiempo lineal para una iteración completa sobre el contenedor).

En la práctica, yo esperaría un iterador unordered_map sea por lo menos en las proximidades de list, a menos su HashMap está muy poco poblada. Podría haber un término O (número de cubos) en la complejidad de la iteración completa. Pero nunca he visto siquiera una implementación específicamente de unordered_map para C++, así que no sé qué adornos esperar en una implementación simplificada de tablas hash de "matriz de listas enlazadas". Si tiene una plataforma "típica" pruébelo, si está intentando escribir código que definitivamente será el más rápido posible en todas las implementaciones de C++, entonces, mala suerte, no puede ;-)

Answer 3

Desafortunadamente, puede hacerlo ' t decir con certeza si algo es lo suficientemente eficiente a menos que lo hayas probado y medido los resultados. Puedo decirte que la biblioteca estándar, TR1 y las clases Boost han tenido toneladas de ojos en ellos. Probablemente sean tan rápidos como lo sean para la mayoría de los casos de uso común. Caminar por un contenedor es ciertamente un caso de uso común.

Con todo lo dicho, es necesario hacerse algunas preguntas:

1. ¿Cuál es la forma más clara de lo que quiero decir? Es posible que escribir una clase contenedora agregue complejidad innecesaria a su código. Primero corrígelo, luego hazlo rápido.

2. ¿Puedo pagar la memoria extra y el tiempo para mantener un list en paralelo con el unordered_map?

3. ¿Es unordered_map realmente la estructura de datos correcta? Si su caso de uso más común es transversal desde el principio hasta el final, es posible que esté mejor con vector porque se garantiza que la memoria será contigua.

Answer 4

Respondido por los puntos de referencia aquí https://stackoverflow.com/a/25027750/1085128 unordered_map es hasta cierto punto entre el vector y mapa de iteración. Es significativamente más rápido que el mapa.