c++ - example - multimap vs mapa con set
multimap c++ example (6)
Me pregunto cuál es más eficiente.
std::map< String, std::set<int> >
o
std::multimap< String, int >
EDITAR: No planeo hacer nada fuera de lo común con estos mapas. Inserción estándar, eliminar, modificar, buscar. El tamaño de cada conjunto o String con múltiples claves no debe ser mayor a 100.
Esto creo que depende de la implementación, pero es una conjetura (no) educada:
En la práctica, depende del número de enteros que mantendrá en multimap o std::set . Es muy probable que un multimap use una búsqueda lineal de los valores después de la búsqueda de log (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 de string seguramente superará las diferencias en ambos casos.
Como se indica a continuación, es probable que un multimap sea más fácil de usar y más claro de mantener dándole una clara ventaja.
No puedo decirlo con certeza, pero dado que el multimapa fue diseñado para hacer lo que el otro es una expresión de, debería ser mejor ser específico y usar el multimap, 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.
Si no estás satisfecho con esas respuestas hasta el momento (sin decir que no) y estoy absolutamente obligado a responder, también daré mi "conjetura" educada:
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".
std :: multimap <String, int> probablemente sea más eficiente con la memoria.
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.
Entonces usaría el enfoque de conjunto a menos que necesite pares clave-valor duplicados. 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.