vector o mapa, ¿cuál usar?

Question

He oído a muchas personas decir que si la cantidad de elementos que se esperan en el contenedor es relativamente pequeña, es mejor usar std::vector en lugar de aunque utilizo el contenedor solo para buscar y no para iterar.

¿Cuál es la verdadera razón detrás de esto?

Obviamente, el rendimiento de búsqueda del mapa no puede ser peor que el del vector (aunque puede ser en nanosegundos/microsegundos), ¿tiene algo que ver con el uso de la memoria?

¿La tarifa del vector es mejor/peor que el mapa en la fragmentación del espacio de direcciones virtuales?

Estoy usando la biblioteca STL que viene con Visual Studio (es decir, la implementación de Microsoft) ¿Eso hace alguna diferencia con otras implementaciones?

Answer 1

Supongo que está comparando map<A, B> con vector<pair<A, B> >.

En primer lugar, encontrar un elemento en un vector muy pequeño puede ser más rápido que la misma cosa en un mapa, porque toda la memoria en un vector siempre es contigua (y se juega mejor con cachés de computadoras y cosas similares) , y la cantidad de comparaciones necesarias para encontrar algo en un vector podría ser aproximadamente la misma que para un mapa. Encontrar un elemento en un mapa necesita menos operaciones en el límite de contenedores muy grandes.

El punto donde los mapas se vuelven más rápidos que los vectores depende de la implementación, en su procesador, qué datos hay en el mapa y cosas sutiles como qué memoria hay en la memoria caché del procesador. Normalmente, el punto donde el mapa se vuelve más rápido sería alrededor de 5-30 elementos.

Una alternativa es utilizar un contenedor hash. A menudo se llaman hash_map o unordered_map. Las clases denominadas hash_map no forman parte del estándar oficial (y existen algunas variantes); std::tr1::unordered_map es. Un mapa hash a menudo es más rápido que un mapa normal para búsquedas, independientemente de cuántos elementos contenga, pero si es realmente más rápido depende de qué es la clave, cómo está procesada, con qué valores debe lidiar y cómo la clave se compara en std :: map. No mantiene las cosas en un orden específico como std :: map, pero has dicho que eso no te importa. Recomiendo los mapas hash especialmente si las claves son enteros o punteros, porque estos se repiten muy rápido.

Answer 2

Los mapas generalmente se implementan como árboles de búsqueda binarios, y caminar en un árbol binario siempre viene con un poco de sobrecarga (realizar comparaciones, enlaces para caminar, etc.) Los vectores son básicamente solo matrices. Para cantidades muy pequeñas de datos, quizás 8 o 12 elementos, a veces es más rápido hacer una búsqueda lineal en una matriz que caminar un árbol de búsqueda binario.

Puede ejecutar algunos tiempos usted mismo para ver dónde está el punto de equilibrio - tiempo una búsqueda en cuatro elementos, luego ocho, luego dieciséis, y así sucesivamente para encontrar el punto óptimo para su implementación particular de la STL.

Los mapas tienden a tener un montón de asignaciones pequeñas en todo el montón, mientras que los vectores son contiguos, por lo que la velocidad de los vectores puede ser un poco mejor en los casos en que itera sobre todos los elementos del frente volver.

Answer 3

Si está haciendo todas las inserciones a la vez y luego realizando muchas búsquedas, puede usar un vector y ordenarlo cuando termine de insertar; luego use lower_bound para hacer una búsqueda rápida. Puede ser más rápido que usar un mapa, incluso para un gran número de elementos.

Answer 4

Creo que primero debe usar el contenedor que se ajusta a los datos. std :: vector se usa en situaciones en las que se usaría una matriz en C o C + pre-STL: se desea un bloque contiguo de memoria para almacenar valores con una búsqueda de tiempo constante rápida. std :: map se debe usar para asignar claves a valores. La superposición primaria aquí es un vector frente a un mapa con un size_t como clave. En ese caso, hay dos preocupaciones: ¿los índices son continuos? Si no, probablemente perderás memoria con un vector. En segundo lugar, ¿qué tiempo de búsqueda quieres? Un vector tiene búsqueda de tiempo constante, mientras que std :: map generalmente se implementa como un árbol RB, que tiene un tiempo de búsqueda O (log n), e incluso un mapa hash (como TR1 unordered_map) generalmente tiene una complejidad peor, porque el índice (o un hash del mismo) se asignará a un depósito que puede contener valores múltiples.

Si apuntamos a un vector con pares: puedes usar los elementos del vector y usar find para encontrar elementos. Pero esta es una búsqueda binaria, y prácticamente será tan rápida como un std :: map.

De todos modos, intente modelar los datos de la manera obvia. La optimización prematura a menudo no ayuda mucho.

Answer 5

"De forma predeterminada, utilice el vector cuando necesite un contenedor" - Bjarne Stroustrup.

De lo contrario, creo que este pequeño diagrama de flujo a ser de muy buena ayuda:

http://homepages.e3.net.nz/~djm/cppcontainers.html

Answer 6

Otra manera de mirar esto, es que si estamos hablando de pequeños contenedores, entonces ninguno de los dos se va tomar mucho tiempo para mirar hacia arriba. A menos que esté buscando a través de este contenedor en un circuito cerrado, la diferencia en el tiempo probablemente será insignificante.

En ese caso, buscaría qué contenedor se aproxima más a lo que desea hacer. Si está buscando un valor particular, el método find() incorporado en el mapa será mucho más fácil (y menos complejo de usar) que crear un bucle for e iterar sobre un vector.

Su tiempo probablemente valga mucho más que unos pocos nano segundos aquí y allá.

Answer 7

Básicamente, los mapas se utilizan para la búsqueda.

Pero, a veces se puede usar std::vector en lugar de std::map incluso para buscar.

Si va a haber muy pocos elementos en sus pares clave-valor, entonces puede hacer una búsqueda iterativa usando la clave incluso en std::vector<std::pair<x,y>>.

Esto se debe a que el hash lleva tiempo, especialmente para las cadenas hash y para otras operaciones en el mapa como almacenar datos en el montón.

Solo vería una mejor diferencia en std :: map, si tiene más elementos en los que debe buscar y también si desea realizar búsquedas frecuentes en la lista de elementos que tiene.