Mehrere gleiche Schlüssel

Für manchen Anwendungsfall ist std::map mit den eindeutigen Schlüsseln etwas wenig. Manchmal möchte man unter einem Schlüssel mehrere Werte speichern können. Genau dafür ist std::multimap gedacht. Die hat allerdings eine kleine Stolperfalle.

Video

Quellcode

#include <map>
#include <string>
#include <iostream>

int main()
{
  std::multimap<std::string, std::string> names
  {
    { "Meier", "Heinz" },
    { "Schmidt", "Anne" },
    { "Mustermann", "Max" },
    { "Meier", "Hildegard" }
  };

  names.insert(std::make_pair("Mustermann", "Theo"));

  for (auto p : names)
  {
    std::cout << p.first << ", " << p.second << std::endl;
  }
  
  auto m = names.find("Mustermann");
  if (m != names.end()) {
    std::cout << "Gefunden: "<< m->first << ", " << m->second << std::endl;
  }
  
  for (auto i = names.find("Mustermann"); 
       i != names.end() && i->first == "Mustermann"; 
       ++i) {
    std::cout << "find: " << i->first << ", " << i->second << std::endl;
  }

  for (auto i = names.lower_bound("Mustermann"); 
       i != names.end() && i->first == "Mustermann"; 
       ++i) {
    std::cout << "lower_bound: " << i->first << ", " << i->second << std::endl;
  }
  
  auto res = names.equal_range("Mustermann");
  for (auto i = res.first; i != res.second; ++i) {
    std::cout << "equal_range: " << i->first << ", " << i->second << std::endl;
  }

}

Erklärung

Grundsätzlich sieht die Deklaration von std::multimap aus, wie std::map: zwei Templateparameter jeweils für den Schlüssel- und den Werttyp und zur Initialisierung ggf. eine Initialisierungsliste mit entsprechenden Paaren. Der Unterschied wird zum ersten Mal in Zeile 12 sichtbar: der doppelte Schlüssel "Meier" ist kein Problem. Dafür ist die std::multimap ja da.

Zeile 15 zeigt einen Teil der Schnittstelle von std::multimap: im Gegensatz zur einfachen std::map gibt es aus semantischen Gründen keinen operator[]. Gäbe es den, dann wäre unklar, wie der sich verhalten soll: soll m["key"] = "value" den Wert des gegebenen Schlüssels überschreiben oder hinzufügen? Die Standardisierer haben deswegen hier auf den Operator verzichtet und bieten nur die insert-Methode an. Diese nimmt allerdings keine zwei Parameter, sondern ein std::pair mit den entsprechenden Werten. Der Bequemlichkeit halber – std::pair ist ein Template, dessen Parameter man normalerweise ausschreiben müsste – verwenden wir hier die Funktion std::make_pair (auch ein Template, aber Funktionen können ihre Templateparameter ja automatisch ableiten).

Zum Auslesen/Auffinden eines Schlüssels dient std::multimap::find. Wie bei allen Containern liefert diese Methode entweder einen Iterator auf einen passenden Wert oder m.end() zurück. Hier lauert allerdings die Stolperfalle bei der Verwendung von m.find(): die Methode liefert laut Standard einen Treffer: nicht den ersten, nicht den letzten, sondern irgendeinen. Deswegen sind die Zeilen 27-31 auch nicht portabel: trifft dieser Code auf eine multimap, die mit find nicht den ersten Treffer landet, dann werden hier schlicht nicht alle Elemente ausgegeben. Die bessere Variante hierfür ist die Funktion lower_bound. Die liefert den ersten Schlüssel, der nicht mehr kleiner ist, als der übergebene. Hier haben wir nun zwei Möglichkeiten: entweder es wird ein passender Schlüssel gefunden, dann ist es der erste Treffer. Oder es wird kein passender Schlüssel gefunden. Dann ist es entweder der nächstgrößere, der vorhanden ist oder m.end(). Beide Fälle sind in der Schleifenbedingung in Zeile 34 abgehandelt: erst wird geprüft, ob der Iterator überhaupt gültig ist und dann, ob der Schlüssel des Iterators (i->first) gleich dem gesuchten Schlüssel ist.

Wem dieser Code nicht schön genug ist, weil man zweimal auf den Schlüssel prüfen muss, dem sei m.equal_range ans Herz gelegt. Ergebnis ist hier ein std::pair aus zwei Iteratoren für den Bereich [erster Treffer, erstes Element hinter dem Schlüssel). Die kann man dann ganz bequem durchlaufen. Wird kein Treffer gefunden, dann kommt hier zweimal m.end() zurück.