Quelle est la différence entre std::multimap<key, value> et std::map<key, std::set<value> >.

Question

J'ai découvert qu'ils ont une clé et plusieurs valeurs, ce qui est unique.

Answer 1

A std::map est un conteneur associatif, qui vous permet d'avoir une clé unique associée à votre valeur de type. Par exemple,

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;
}

A std::multimap est égal à un std::map mais vos clés ne sont plus uniques. Vous pouvez donc trouver une série d'éléments au lieu de trouver un seul élément unique. Par exemple,

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 est comme un std::map mais il ne stocke pas une clé associée à une valeur. Il ne stocke que le type de clé, et vous assure qu'il est unique au sein de l'ensemble.

Vous disposez également de la std::multiset qui suit le même schéma.

Tous ces conteneurs fournissent un accès O(log(n)) avec leur find / equal_range.

Answer 2

La multimap stocke des paires de (clé, valeur) où la clé et la valeur peuvent apparaître plusieurs fois.

El map<key, set<value>> ne stockera chaque valeur qu'une seule fois pour une clé spécifique. Pour ce faire, il devra être capable de comparer les valeurs, et pas seulement les clés.

Cela dépend de votre application si les valeurs qui se comparent sont équivalentes, ou si vous souhaitez de toute façon les stocker séparément. Peut-être contiennent-elles des champs qui sont différents mais qui ne participent pas à la comparaison pour l'ensemble.

Answer 3

map::insert

Parce que map Les conteneurs ne permettent pas de dupliquer les valeurs de clé, l'opération d'insertion vérifie pour chaque élément inséré si un autre élément existe déjà dans le conteneur avec la même valeur de clé ; si c'est le cas, l'élément n'est pas inséré et sa valeur mappée n'est en aucun cas modifiée.

d'autre part

multimap::insert 

peut insérer un nombre quelconque d'éléments ayant la même clé.

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

Answer 4

Cette dernière nécessite que les valeurs puissent être ordonnées (soit via operator< ou une fonction de comparaison), le premier ne le fait pas.