Qual é a diferença entre std :: multimap <key, value> e std :: map <key, std :: set <value>>

Descobri que eles têm uma chave e vários valores que são únicos.

O multimapa armazena pares de (chave, valor) onde a chave e o valor podem aparecer várias vezes.

O map<key, set<value>>irá armazenar cada valor apenas uma vez para uma chave específica. Para fazer isso, ele deverá ser capaz de comparar os valores, não apenas as chaves.

Depende do seu aplicativo se os valores que comparam iguais são equivalentes ou se você deseja armazená-los separadamente. Talvez eles contenham campos diferentes, mas não participem da comparação do conjunto.

A std::mapé um contêiner associativo, que permite que você tenha uma chave exclusiva associada ao valor do tipo. Por exemplo,

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é igual a a std::map, mas suas chaves não são mais exclusivas. Portanto, você pode encontrar uma variedade de itens em vez de apenas encontrar um item exclusivo. Por exemplo,

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

O std::seté como um std::map, mas não está armazenando uma chave associada a um valor. Ele armazena apenas o tipo de chave e garante que ele é único dentro do conjunto.

Você também tem o std::multiset, que segue o mesmo padrão.

Todos esses contêineres fornecem um acesso O (log (n)) com seu find / equal_range.

map::insert

Como os mapcontêineres não permitem valores de chave duplicados, a operação de inserção verifica para cada elemento inserido se outro elemento já existe no contêiner com o mesmo valor de chave. Nesse caso, o elemento não é inserido e seu valor mapeado não é alterado de nenhuma maneira.

por outro lado

multimap::insert 

pode inserir qualquer número de itens com a mesma chave.

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

O último requer que os valores possam ser ordenados (por meio de operator<ou por uma função de comparação), o primeiro não.