Cuál es la diferencia entre std :: multimap <key, value> y std :: map <key, std :: set <value>>

Question

Encontré que tienen una clave y múltiples valores que son únicos.

Answer 1

El multimapa almacena pares de (clave, valor) donde tanto la clave como el valor pueden aparecer varias veces.

El map<key, set<value>> solo almacenará cada valor una vez para una clave específica. Para hacer eso, tendrá que ser capaz de comparar los valores, no solo las claves.

Depende de su aplicación si los valores que comparan iguales son equivalentes, o si desea guardarlos por separado de todos modos. Quizás contienen campos que son diferentes pero no participan en la comparación del conjunto.

Answer 2

Este último requiere que los valores se puedan pedir (ya sea a través de operator< o una función de comparación), el primero no.

Answer 3

map::insert 

Debido map recipientes no permiten valores de clave duplicados, los controles de operación de inserción para cada elemento insertado si otro elemento que ya existe en el recipiente con el mismo valor de clave si es así, el elemento no está insertada y de sus mapeados el valor no se cambia de ninguna manera.

por el contrario

multimap::insert 

puede insertar cualquier número de elementos con la misma clave.

http://www.cplusplus.com/reference/stl/map/
http://www.cplusplus.com/reference/stl/multimap/

Answer 4

Un std::map es un contenedor asociativo, que le permite tener una clave única asociada con su valor de tipo. Por ejemplo,

void someFunction() 
{ 
    typedef std::map<std::string, int> MapType; 
    MapType myMap; 

    // insertion 
    myMap.insert(MapType::value_type("test", 42)); 
    myMap.insert(MapType::value_type("other-test", 0)); 

    // search 
    auto it = myMap.find("test"); 
    if (it != myMap.end()) 
     std::cout << "value for " << it->first << " is " << it->second << std::endl; 
    else 
     std::cout << "value not found" << std::endl; 
} 

Un std::multimap es igual a un std::map, pero las llaves no son exclusivos más. Por lo tanto, puede encontrar una variedad de artículos en lugar de solo encontrar un artículo único. Por ejemplo,

void someFunction() 
{ 
    typedef std::multimap<std::string, int> MapType; 
    MapType myMap; 

    // insertion 
    myMap.insert(MapType::value_type("test", 42)); 
    myMap.insert(MapType::value_type("test", 45)); 
    myMap.insert(MapType::value_type("other-test", 0)); 

    // search 
    std::pair<auto first, auto second> range = myMap.equal_range("test"); 
    for (auto it = range.first; it != range.second; ++it) 
     std::cout << "value for " << it->first << " can be " << it->second << std::endl; 
} 

El std::set es como un std::map, pero no es el almacenamiento de una clave asociada a un valor. Almacena solo el tipo de clave, y le asegura que es único dentro del conjunto.

También tiene el std::multiset, que sigue el mismo patrón.

Todos estos contenedores proporcionan un acceso O (log (n)) con su rango de búsqueda/igualdad.