c++ - buscar - multimap java

¿Por qué multimap permite pares duplicados clave-valor?

Question

EDITAR: Tenga en cuenta que no estoy preguntando por qué multimap no puede contener claves duplicadas.

¿Cuál es la razón detrás del multimapa que permite pares duplicados de clave-valor? (no teclas )

#include <map>
#include <string>
#include <iostream>

int
main(int argc, char** argv)
{
    std::multimap<std::string, std::string> m;
    m.insert(std::make_pair("A", "B"));
    m.insert(std::make_pair("A", "B"));
    m.insert(std::make_pair("A", "C"));
    std::cout << m.size() << std::endl;
    return 0;
}

Este impreso 3, que me sorprendió un poco, esperaba que el multimapa se comportara como un conjunto de pares , por lo que esperaba 2.

De manera intuitiva, no es coherente con el comportamiento de C ++ std::map , donde la insert no siempre cambia el mapa (a diferencia del operator[] ).

¿Hay una razón detrás de esto, o es simplemente arbitraria?

Answer 1

Como ustedes saben, multimap permite tener múltiples claves. Dado que no impone restricciones a la comparabilidad de los valores, no se puede verificar si los valores no se han duplicado.

Si desea tener una estructura de datos de diccionario que permita claves duplicadas, pero no pares de clave-valor, debería asegurarse de que los valores sean comparables.

Digamos que tenemos un juego de algún tipo, donde hay un mundo 2D de campos cuadrados, y puedes poner elementos en los campos. Puede tener multimap<Field, Item> , que le permitirá mantener dos elementos idénticos en el campo. Los artículos no tienen que ser comparables aquí.

Answer 2

Mi razonamiento es que el multimapa se basa en la búsqueda / inserción de la clave y no en el valor. Por lo tanto, si el valor en las claves duplicadas es el mismo o no, no juega un papel cuando se insertan elementos.

23.3.2 Plantilla de clase multimap

1 Un multimapa es un tipo de contenedor asociativo que admite claves equivalentes (que posiblemente contengan varias copias del mismo valor de clave) y permite una rápida recuperación de valores de otro tipo T en función de las claves.

Answer 3

Multimap solo tiene un predicado ordenando las teclas. No tiene un método para determinar si los valores son iguales. ¿Es el valor "A" un duplicado del valor "a"? Sin un segundo predicado para los valores, no hay forma de decirlo. Por lo tanto, ni siquiera tiene sentido hablar de valores duplicados en un multimap.

Si desea un contenedor que almacene pares y aplique el carácter único de ambas partes del par, busque boost::multi_index_container . Es muy flexible, pero lleva una carga de argumentos como resultado.

Answer 4

Se permite que los valores sean duplicados porque no se requiere que sean comparables entre sí. El contenedor no puede hacer nada con los valores además de copiarlos. Esto habilita tipos como multimap< int, my_class > .

Si los pares de clave-valor duplicados no son deseables, use set< pair< T, U > > y use lower_bound para encontrar la primera coincidencia con una clave dada.

Answer 5

"multimap" está diseñado para admitir teclas ''múltiples'' a diferencia del "map" simple. Como permite varias claves, no se preocupará por sus valores, por lo que muestra 3 elementos en su ejemplo. La otra diferencia es que uno no puede tener el operator [] para multimap .

Answer 6

EDITAR: Esta respuesta ya no responde a la pregunta actual. Lo mantendré tal como está porque se ha votado mucho por lo que debe ser útil para algunos.

El multi en multimap representa el hecho de que la misma clave puede aparecer varias veces.

El estándar no pone límite al tipo utilizado como valor, por lo que no se puede suponer que el operator==() esté definido. Debido a que no queremos que el resultado de su código dependa de si el operador == () está definido o no, nunca se usa.

std::multimap no reemplaza a std::map . Como notó, se comporta de manera diferente cuando se inserta la misma clave varias veces. Si desea el comportamiento de std::map , use std::map .

También hay un std::multiset .

Lo racional: a veces uno quisiera mantener todas las entradas antiguas para la misma clave también. [TBD: Insertar un ejemplo aquí]

Personalmente, casi nunca uso std::multimap . Si quiero múltiples entradas para la misma clave, generalmente confío en std::map<std::vector<T> > .