Jaka jest różnica między std :: multimap <key, value> a std :: map <key, std :: set <value>>

Odkryłem, że mają jeden klucz i wiele unikalnych wartości.

Multimapa przechowuje pary (klucz, wartość), w których zarówno klucz, jak i wartość mogą pojawić się kilka razy.

map<key, set<value>>Będzie przechowywać tylko raz dla każdej wartości klucza konkretnego. Aby to zrobić, będzie musiał porównywać wartości, a nie tylko klucze.

Zależy od aplikacji, czy wartości, które porównują są równe, czy też chcesz przechowywać je osobno. Być może zawierają różne pola, ale nie biorą udziału w porównaniu dla zbioru.

A std::mapto kontener asocjacyjny, który pozwala mieć unikalny klucz powiązany z wartością typu. Na przykład,

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::multimapjest równe a std::map, ale Twoje klucze nie są już unikalne. Dlatego zamiast jednego unikalnego przedmiotu można znaleźć wiele różnych przedmiotów. Na przykład,

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

std::setJest jak std::map, ale to nie jest przechowywanie klucza związanego z wartością. Przechowuje tylko typ klucza i zapewnia, że ​​jest unikalny w zestawie.

Masz również std::multiset, który jest zgodny z tym samym wzorem.

Wszystkie te kontenery zapewniają dostęp O (log (n)) z ich zakresem find / equal_range.

map::insert

Ponieważ mapkontenery nie zezwalają na zduplikowane wartości klucza, operacja wstawiania sprawdza dla każdego wstawionego elementu, czy w kontenerze istnieje już inny element o tej samej wartości klucza, jeśli tak, element nie jest wstawiany, a jego zamapowana wartość nie jest w żaden sposób zmieniana.

z drugiej strony

multimap::insert 

może wstawić dowolną liczbę elementów tym samym kluczem.

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

Ta ostatnia wymaga, aby wartości można było uporządkować (za pośrednictwem funkcji operator<lub funkcji porównawczej), w przypadku pierwszej nie.