Me pregunto cuál es más eficiente.multimap vs mapa con el conjunto
std::map< String, std::set<int> >
o
std::multimap< String, int >
EDIT: No planeo hacer nada fuera de lo común con estos mapas. Inserción estándar, eliminar, modificar, buscar. El tamaño de cada cadena con llave establecer o múltiples no debe ser más de 100.
Esto creo que depende de la implementación, pero una (des) conjetura:
En la práctica, depende del número de enteros que se va a mantener en el multimap o la std::set. A multimap lo más probable es que utilice una búsqueda lineal de los valores después de la búsqueda de registro (n) de la clave. Si tiene una gran cantidad de valores enteros, la búsqueda de log (n) de las teclas seguida de una búsqueda de log (n) de los valores puede ser un poco más rápida.
Sin embargo, en términos de eficiencia, almacenar cualquier cosa en un map o multimap con una clave string casi con seguridad superará las diferencias en ambos casos.
Como se ha dicho más adelante, un multimap es probable que sea más fácil de usar y más clara para mantener lo que supone una clara ventaja.
No puedo decir con seguridad, pero teniendo en cuenta que multimap fue diseñado para hacer lo que el otro es una expresión de, debería ser mejor estar específico y utiliza el multimapa, tiene mucho más sentido, también tiene funciones de miembro para trabajar con un multimapa como concepto, esas funciones serían un poco cobardes usando el otro enfoque.
std :: multimap < String, int> es muy probablemente más eficiente de la memoria.
¿Tiene un fundamento? –
El número de números almacenados es el mismo en ambos, pero debido a que está utilizando dos árboles negros rojos, está utilizando el doble de la cantidad de "libros" que los necesarios. Además, dado que la mayoría de las implementaciones STL de std :: string utilizan recuento de referencias y copia en semántica de escritura, los datos utilizados por las cadenas no se pueden duplicar. Espero que esto tenga sentido mientras escribo esto en mi teléfono. –
En realidad, no ha probado que un mapa y conjuntos ocupen más espacio que un multimap (¿qué pasa con la contabilidad adicional de multimap?), Pero de hecho almacenará mucho más de dos árboles. Y que estos se implementan como árboles no se especifica. Y no hay espacio de nombres 'std' en el STL. Y, en realidad, mi comentario tenía la intención de provocarlo para que agregue un fundamento a su _answer_;) –
Si no está satisfecho con las respuestas hasta ahora (no digo que no eres) y estoy absolutamente obligado a responder, voy a dar mi educada "adivinar" demasiado:
Para insertar, el multimap parece ser más "eficiente". Con el enfoque de mapa, primero tiene que recuperar, luego realizar una operación en el conjunto. Para eliminar/recuperar, el mapa parece más "eficiente".
La opción "establecer" eliminará las duplicaciones de pares clave + valor, ya sea que el multimapa no lo haga.
En realidad, no son equivalentes de todos modos. Un multimap<X,Y> permite almacenar pares clave-valor duplicados, mientras que un map<T, set<X>> no lo hace.
multimap<int, int> m;
m.insert(make_pair(2, 3));
m.insert(make_pair(2, 3)); // This changes the size of m!
Mientras
map<int, set<int>> m;
m[2].insert(3);
m[2].insert(3); // This does nothing.
Así que me gustaría utilizar el enfoque conjunto a menos que necesite duplicar los pares de valores clave. La sintaxis es también más agradable. Espero que la diferencia en el rendimiento y el uso de la memoria no sea tan buena.
Definir "eficiente". –
¿Cuáles son las operaciones que desea realizar?Eso definirá los diferentes costos, ya que el primer enfoque le permitirá realizar búsquedas rápidas tanto en cadena como en enteros, y el segundo requerirá iterar y probar la parte int contra cada valor para el que la cadena sea la misma ... Pero si no necesita esa operación, puede ser que la segunda opción sea mejor en algunos casos de uso ... –
mire mi edición –