wake-up-neo.com

Was ist der Unterschied zwischen std :: multimap <Schlüssel, Wert> und std :: map <Schlüssel, std :: set <Wert>>?

Ich habe festgestellt, dass sie einen Schlüssel und mehrere Werte haben, was eindeutig ist.

75
大宝剑

Die Multikarte speichert Paare von (Schlüssel, Wert), wobei sowohl Schlüssel als auch Wert mehrmals vorkommen können.

Das map<key, set<value>> speichert jeden Wert nur einmal für einen bestimmten Schlüssel. Dazu muss es möglich sein, die Werte und nicht nur die Schlüssel zu vergleichen.

Es hängt von Ihrer Anwendung ab, ob die Werte, die gleich sind, gleich sind oder ob Sie sie trotzdem separat speichern möchten. Vielleicht enthalten sie Felder, die unterschiedlich sind, aber nicht am Vergleich für die Menge teilnehmen.

47
Bo Persson

EIN std::map ist ein assoziativer Container, mit dem Sie Ihrem Typwert einen eindeutigen Schlüssel zuordnen können. Beispielsweise,

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

EIN std::multimap ist gleich a std::map, aber Ihre Schlüssel sind nicht mehr eindeutig. Daher können Sie eine Reihe von Artikeln finden, anstatt nur einen einzigen Artikel zu finden. Beispielsweise,

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

Das std::set ist wie ein std::map, aber es wird kein einem Wert zugeordneter Schlüssel gespeichert. Es speichert nur den Schlüsseltyp und stellt sicher, dass er innerhalb des Satzes eindeutig ist.

Sie haben auch die std::multiset, das folgt dem gleichen Muster.

Alle diese Container bieten einen O(log(n)) Zugriff mit ihrem find/equal_range.

69
typedef
map::insert

Da in map -Containern keine doppelten Schlüsselwerte zulässig sind, überprüft der Einfügevorgang für jedes eingefügte Element, ob bereits ein anderes Element mit demselben Schlüsselwert im Container vorhanden ist. Ist dies der Fall, wird das Element nicht eingefügt und der zugeordnete Wert lautet in keiner Weise verändert.

auf der anderen Seite

multimap::insert 

kann eine beliebige Anzahl von Elementen mit demselben Schlüssel einfügen.

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

13
Luka Rahne

Letzteres setzt voraus, dass die Werte bestellt werden können (entweder über operator< oder eine Vergleichsfunktion), erstere nicht.

10
Björn Pollex