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

Odpowiedzi:

52

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.

Bo Persson
źródło
5
Tak więc std :: multimap <key, value> jest jak std :: map <key, std :: multiset <value>>, różnica między nimi polega na tym, że późniejsze wartości są sortowane. Czy to prawda?
大 宝剑
2
Nie, std::multimap<key, value>umożliwia wielokrotne pojawienie się tego samego klucza, ale std::map<key, whatever>wymaga wyjątkowości key.
Yixing Liu
75

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.

typedef
źródło
6
W funkcji multimap ta linia std::pair<auto first, auto second> range = myMap.equal_range("test");nie działa, ponieważ error: 'auto' not allowed in template argument. Użyj const auto range = myMap.equal_range("test")zamiast tego.
vancexu
2
typ mapy? Czy nie powinno to być MapType w linii 4?
lolololol ol
Nie wiem, kto był pierwszy, ale to oczywiście kopia wklej z drugiej: cppbuzz.com/What-is-difference-between-map-and-multimap
largest_prime_is_463035818
1
ahah, cppbuzz zeskrobuje StackOverflow czy co ?, napisałem tę odpowiedź lata temu, kiedy wciąż codziennie kodowałem w c ++. I rzeczywiście istnieje linia typo 4, dzięki @lololololol
typedef
1
(i ich kopiowanie / wklejanie nie powiodło się, nawet nie wyświetlają typów w szablonie std :: maplaration: std :: map <std :: string, int>)
typedef
13
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/

Luka Rahne
źródło
Dobry link do różnicy i tego, jak to działa wewnętrznie. link
Rndp13
10

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.

Björn Pollex
źródło
Wydawałoby się, że operator <działa tak samo na mapie, czy na multimapie? en.cppreference.com/w/cpp/container/map/operator_cmp
johnbakers
Tak, ale moja odpowiedź dotyczyła uporządkowania wartości. Załóżmy, że masz typ, Tktóry nie ma zamówienia. Możesz go użyć do utworzenia pliku std::multimap<U, T>, ale nie możesz go użyć do utworzenia pliku std::map<U, std::set<T> >.
Björn Pollex