Cuándo elegir std :: vector over std :: map para datos de valor-clave?

Question

Considerando el efecto positivo del almacenamiento en caché y la ubicación de datos cuando busco en la memoria primaria, tiendo a usar std::pair<>-como elementos de valor-clave y realizar búsquedas lineales para ambos, si sé que la cantidad total de elementos clave-valor nunca sea "demasiado grande" para afectar severamente el rendimiento.

Últimamente he estado en un montón de situaciones en las que saber de antemano que va a tienen enormes cantidades de artículos de valor clave y por lo tanto he optado por std::map<> desde el principio.

Me gustaría saber cómo tomar sus decisiones para el contenedor adecuado en situaciones como las descritas anteriormente.

¿Te

• utilizar siempre std::vector<> (o similar)?
• siempre use std::map<> (o similar)?
• tienen una intuición de dónde en el rango de recuento de artículos uno es preferible sobre el otro?
• algo completamente diferente?

Gracias!

Answer 1

Raramente uso std::vector con una búsqueda lineal (excepto en combinación con la búsqueda binaria como se describe a continuación). Supongo que para una cantidad de datos lo suficientemente pequeña sería mejor, pero con esa poca información es poco probable que algo brinde una gran ventaja.

Dependiendo del patrón de uso, una búsqueda binaria en un std::vector puede tener sentido. A std::map funciona bien cuando necesita actualizar los datos regularmente durante el uso.En algunos casos, sin embargo, carga algunos datos y luego usa los datos, pero después de que haya cargado los datos, en su mayoría permanece estático (es decir, cambia muy poco, si es que cambia). En este caso, puede tener mucho sentido cargar los datos en un vector, ordenarlos si es necesario y luego realizar búsquedas binarias en los datos (por ejemplo, std::lower_bound, std::equal_range). Esto da más o menos lo mejor de ambos mundos: búsquedas binarias de baja complejidad y buen uso de la memoria caché de la localidad de referencia alta (es decir, el vector es contiguo, a diferencia de la estructura vinculada de std::map). El inconveniente, por supuesto, es que las inserciones y eliminaciones son lentas, pero esta es una vez que he usado tu idea original, almacena datos recién insertados por separado hasta que llega a un límite, y solo luego lo ordena con el resto del datos, por lo que una búsqueda única consiste en una búsqueda binaria del cuerpo principal de los datos, seguida de una búsqueda lineal de la (pequeña cantidad) de datos recién insertados.

Answer 2

Nunca tomaría la decisión únicamente sobre motivos de "eficacia" (posiblemente falsos), pero siempre sobre lo que realmente voy a hacer con el contenedor. ¿Quiero almacenar duplicados? ¿Es importante el orden de inserción? ¿A veces quiero buscar el valor, no la clave? Ese tipo de cosas.

Answer 3

Casi siempre prefiero usar map (o unordered_map, cuando un contenedor hash tiene más sentido) frente a un vector.

Habiendo dicho eso, creo que su razonamiento es al revés. Yo tendería a usar un vector solo cuando hay grandes cantidades de datos, ya que un vector tendrá una huella de memoria más pequeña.

Con los tipos correctos de conjuntos de datos, puede cargar un vector y luego ordenarlo y binary_search con una huella más pequeña y características de rendimiento similares a un mapa, especialmente si el conjunto de datos es estable después de la carga.

Answer 4

¿Ha considerado usar estructuras de datos clasificadas? Tienden a ofrecer búsquedas e inserciones logarítmicas, una compensación razonable. Personalmente, no tengo reglas duras y rápidas que no sean los mapas de me gusta para la capacidad de clave en un valor inteligible para los humanos.

Por supuesto, también hay mucha discusión sobre la eficiencia de los mapas frente a las listas/vectores (ordenados y sin clasificar): si la clave es una cadena de 10.000 caracteres, puede llevar más tiempo hacer una comparación de cadena que buscar a través de una lista de solo algunos artículos, por lo que debe asegurarse de que también pueda comparar claves de manera eficiente.

Answer 5

¿Por qué no toma unordered_map en cuenta?