vector o mapa, ¿cuál usar?

He escuchado 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 lugar de std::map 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?

¿El precio 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?

Supongo que está comparando el map con el vector > .

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, ya que toda la memoria de un vector siempre es contigua (y así se juega mejor con los cachés de las computadoras y cosas así), y el número de las 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, de su procesador, de qué datos se encuentran en el mapa, y de 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 usar un contenedor hash. A menudo se denominan hash_map o hash_map . Las clases denominadas hash_map no son 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.

Los mapas generalmente se implementan como árboles de búsqueda binarios, y caminar en un árbol binario siempre viene con un poco de sobrecarga (realizando 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: programe una búsqueda en cuatro elementos, luego ocho, luego dieciséis, y así sucesivamente para encontrar el punto óptimo para su implementación particular del STL.

Los mapas tienden a tener un montón de pequeñas asignaciones en todo el montón, mientras que los vectores son contiguos, por lo que la tasa de vectores de caché puede ser un poco mejor en los casos en que itera sobre todos los elementos de adelante hacia atrás.

“De forma predeterminada, utilice el vector cuando necesite un contenedor” – Bjarne Stroustrup.

De lo contrario, me parece que este pequeño diagtwig de flujo es de gran ayuda:

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

Si está haciendo todas sus 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.

Creo que primero debes 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 apuntara a un vector con pares: podría 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.

Otra forma de ver esto es que si hablamos de contenedores pequeños, ninguno tardará mucho en 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 quiere 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.

Tu tiempo es probable que valga mucho más que unos pocos nano segundos aquí y allá.

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

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

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

Esto se debe al hecho de 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 cuando desea realizar búsquedas frecuentes en la lista de elementos que tiene.