Selbstgebaute Schlüssel

std::map ist an sich ja schön und gut, aber man will ja oft nicht nur Strings und Integer als Schlüssel verwenden. Eigene Typen müssen allerdings bestimmte Anforderungen erfüllen, um hier Verwendung zu finden. Zum Glück bietet C++ mehrere Möglichkeiten, um diese Anforderungen in den unterschiedlichsten Situationen zu erfüllen.

Video

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include <iostream>
#include <map>
#include <string>
 
struct City
{
    std::string name;
    std::string country;
     
    City(std::string const &n, std::string const &c)
        : name { n }, country { c }
    {
    }
     
//     bool operator<(City const &other) const
//     {
//         return name < other.name || (name == other.name && country < other.country);
//     }
};
 
namespace std
{
    template <> struct less<City> {
        bool operator()(City const &c1, City const c2) 
        {
            return c1.name < c2.name || (c1.name == c2.name && c1.country < c2.country);
        }
    };
}
 
struct Compare
{
    bool operator()(City const &c1, City const &c2)
    {
        return c1.name > c2.name || (c1.name == c2.name && c1.country > c2.country);
    }
};
 
int main()
{
    std::map<City, unsigned int, Compare> inhabitants;
     
    inhabitants[City("London", "United Kingdom")] = 8308369;
    inhabitants[City("Berlin", "Deutschland")] = 3375222;
    inhabitants[City("Frankfurt/Main", "Deutschland")] = 687775;
    inhabitants[City("Berlin", "Conneticut, USA")] = 19590;
     
    for (auto c : inhabitants) {
        std::cerr << c.first.name << " (" << c.first.country << "): " << c.second << std::endl;
    }
}

Erklärung

Städte weltweit haben ja bekanntermaßen öfters mal gleiche Namen. Will man die also eindeutig kennzeichnen, dann braucht man noch weitere Informationen (bspw. das Land). Diese Informationen werden hier in der Klasse City gespeichert. Soll diese nun als Schlüssel für std::map verwendet werden, dann geht das erstmal daneben. Je nach Compiler (der GCC sticht hier leider sehr negativ hervor) wird man von einer ganzen Menge Fehlermeldungen erschlagen, die letztlich nur auf eins hinweisen: standardmäßig vergleicht std::map zwei Schlüssel mit dem Ausdruck k1 < k2. Wenn nun der eigene Typ keinen operator< unterstützt, dann ist erstmal Essig.

Damit ist auch schon die erste (und einfachste) Variante der Anpassung genannt: die Implementierung von operator< für den betreffenden Typ. Der auskommentierte Block in den Zeilen 15-18 enthält eine mögliche Variante. Was hier auffällt ist der zweite Teil des Ausdrucks in Zeile 17. Die naive Implementierung würde hier möglicherweise nur so aussehen: return name < other.name || country < other.country. Allerdings würde diese Variante die Anforderungen von std::map nicht erfüllen. Für das Beispiel “Frankfurt, Deutschland” und “Berlin, USA” liefert diese Implementierung nämlich für beide Richtungen true: “Frankfurt, Deutschland” < “Berlin, USA” (aufgrund der Teilergebnisse false || true), umgekehrt allerdings auch (aufgrund von true || false, wobei der zweite Teil nach dem || nicht mehr ausgewertet wird, wenn vorher schon ein true auftaucht). Das ist nicht nur unlogisch, sondern auch verboten. Das Verhalten von std::map ist damit nicht mehr vorhersehbar. Das hier gewählte Muster ist für die Implementierung von mehrteiligen Schlüsseln immer wieder hilfreich: wenn ein Schlüssel aus den Teilen k1, k2 und k3 besteht, dann ist eine richtige Implementierung k1 < other.k1 || k1 == other.k1 && (k2 < other.k2 || k2 == other.k2 && k3 < other.k3). Natürlich ist das auf beliebig viele Teilschlüssel erweiterbar. Wichtig ist nur, dass bei Vergleich den n. Teilschlüssel sichergestellt ist, dass alle n-1 Teilschlüssel vorher gleich sind.

In Situationen, wo eine Anpassung des betreffenden Typs mit einer Implementierung von operator< nicht möglich ist (bspw. bei Typen aus Libraries), bietet std::map über die Verwendung des Templates std::less zum Vergleich eine bequeme Möglichkeit, die Sortierung extern anzupassen. Dazu muss das betreffende Template für den entsprechenden Typ spezialisiert werden (Zeile 21-29). std::less ist ein Funktionstyp, dessen operator() zwei Parameter nimmt und true zurückliefert, wenn der erste kleiner, als der zweite ist. Für die Implementierung des operator() gelten natürlich die gleichen Regeln, wie für operator<.

Die beiden Varianten mit operator< und std::less wirken global: jede std::map (und einige weitere Datenstrukturen) wird ihre Sortierung entsprechend vornehmen. Will man hingegen nur die Sortierung einer einzelnen Map ändern, so kann man den dritten Templateparameter in der Variablendeklaration anpassen (wie in Zeile 41 zu sehen). Der zu übergebende Typ muss wie std::less ein Funktionstyp sein, der einen passenden operator() mit zwei Parametern implementiert. Im Beispiel ist das die Struktur Compare (Zeile 31-37). Der Typ muss mit einem Standardkonstruktur initialisierbar sein (Ausnahme: man übergibt das betreffende Vergleichsobjekt als Konstruktorparameter an die std::map. Braucht man aber eher selten.) Im Beispiel hier wird die Sortierung der std::map umgedreht.