std::map - behind the scenes

Wie funktioniert eigentlich std::map und welche Garantien gibt der Standard? Der Artikel zeigt einen mögliche Implementierungsansatz (der garantiert nicht vollständig ist, da die “richtige” std::map noch viel mehr Funktionalität unterstützen muss).

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
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135


#include <iostream>
#include <memory>
#include <string>
#include <functional>
#include <stdexcept>
 
template <typename KeyT, 
          typename ValueT, 
          typename CompareT = std::less<KeyT> 
         > class map
{
    struct TreeNode
    {
        KeyT key;
        ValueT value;
        std::shared_ptr<TreeNode> left;
        std::shared_ptr<TreeNode> right;
    };
     
    std::shared_ptr<TreeNode> root;
    CompareT compare;
     
public:
     
    void insert(KeyT const &key, ValueT const value)
    {
        std::shared_ptr<TreeNode> curr_pointer(root);
 
        if (!root) {
            //Spezialfall "leerer" Baum
            root.reset(new TreeNode);
            root->key = key;
            root->value = value;
        }
        else {
            while (curr_pointer) {
                if (compare(key, curr_pointer->key)) {
                    // key < curr_pointer
                    if (!curr_pointer->left) {
                        // Element hat keinen linken Nachfolger -> einfügen
                        std::shared_ptr<TreeNode> t(new TreeNode);
                        t->key = key;
                        t->value = value;
                        curr_pointer->left = t;
                        break;
                    }
                    curr_pointer = curr_pointer->left;
                }
                else if (compare(curr_pointer->key, key)) {
                    // key > curr_pointer
                    if (!curr_pointer->right) {
                        // Element hat keinen rechten Nachfolger 
                        std::shared_ptr<TreeNode> t(new TreeNode);
                        t->key = key;
                        t->value = value;
                        curr_pointer->right = t;
                        break;
                    }
                    curr_pointer = curr_pointer->right;
                }
                else {
                    // key == curr_pointer -> Wert überschreiben
                    curr_pointer->value = value;
                    break;
                }
            }
        }
    }
     
    ValueT const &at(KeyT const &key) const
    {
        std::shared_ptr<TreeNode> curr_pointer(root);
        while (curr_pointer) {
            if (compare(key, curr_pointer->key)) {
                // key < curr_pointer
                curr_pointer = curr_pointer->left;                
            }
            else if (compare(curr_pointer->key, key)) {
                // key > curr_pointer
                curr_pointer = curr_pointer->right;
            }
            else {
                // key == curr_pointer
                return curr_pointer->value;
            }
        }
        throw std::out_of_range("Element nicht enthalten");
    }
     
    void print(std::ostream &os)
    {
        rec_printer(os, 0, root);
    }
     
private:
     
    void rec_printer(std::ostream &os, int spaces, std::shared_ptr<TreeNode> node)
    {
         
        for (int i = 0; i < spaces; ++i) {
            os << " ";
        }
        os << node->key << " => " << node->value << std::endl;
        if (node->left) {
            for (int i = 0; i < spaces+1; ++i) {
                os << " ";
            }        
            os << "left: \n";
            rec_printer(os, spaces+2, node->left);
        }
        if (node->right) {
            for (int i = 0; i < spaces+1; ++i) {
                os << " ";
            }        
            os << "right: \n";
            rec_printer(os, spaces+2, node->right);
        }
    }
};
 
int main()
{
    map<std::string, std::string> m;
    m.insert("C", "C");
    m.insert("E", "E");
    m.insert("X", "X");
    m.insert("D", "D");
    m.insert("A", "A");
         
    std::cerr << m.at("X") << std::endl;
    
    std::cerr << "----\n";
     
    m.print(std::cerr);
}

Erklärung

Der Standard ist bzgl. der Container sehr freizügig. Es werden keine Implementierungen vorgegeben, sondern nur Schnittstellen und Verhalten festgelegt. So gilt für die Operationen insert und find von std::map, dass sie logarithmisch mit der Menge der gespeicherten Elemente wachsen sollen. Wie der Implementierer das nun erreicht, ist seine Sache. Er könnte mit einem zugrunde liegenden sortierten Array arbeiten, welches mit binärer Suche beackert wird (wobei das wiederum die Implementierung des logarithmischen Inserts etwas verkompliziert) oder (was zumindest bei der Implementierung der Standardlibrary des GCC der Fall ist) auf eine irgendwie geartete Baumstruktur zurückgreifen. Für letzteres habe ich mich hier im Beispiel entschieden.

Binärbäume haben genau die verlangte Eigenschaft: sowohl das Einfügen, als auch das Auffinden von von Elementen ist im Mittel logarithmisch. Der (ausbalancierte) Baum hat eine Tiefe von log(n) (für n = Anzahl der Elemente im Baum), woraus für jedes Suche eine maximale Anzahl von log(n) Vergleichen folgt (im schlimmsten Fall muss man sich eben bis zur untersten Ebene durchhangeln). Einfügen geschieht einfach durch Anhängen an die richtige Stelle im Baum, wobei diese ebenso im schlimmsten Fall in log(n) Schritten gefunden wird. Ergo: eigentlich die perfekte Datenstruktur für die Anforderungen von std::map.

Um allerdings einen Baum so implementieren zu können, ist eine strenge schwache Ordnung der Schlüssel notwendig (hier ist mir im Video ein Fehler unterlaufen: dort habe ich von Halbordnung gesprochen, die aber nicht ausreicht). Sprich: die Schlüssel müssen “irgendwie” sortiert sein. Grundidee des Baumes lautet: soll ein Element a unter einem Element b eigehängt werden und gilt für eine Relation R (bspw < ) a R b, dann wird a als linkes Kind von b eingehängt. Gilt b R a, dann wird a als rechtes Kind von b eingehängt (wahlweise umgekehrt. Das hat aber die gleiche Wirkung, der Baum wäre dann nur spiegelverkehrt). Die für die Sortierung notwendige Relation wird als dritter Typparameter an das std::map-Template übergeben. Der zu übergebende Parametertyp muss sich mittels des Standardkonstruktors instanziieren lassen und einen operator() mit zwei Parametern anbieten. Diese beiden Parameter sind die zu vergleichenden Elemente a und b. Der Aufruf muss true liefern, wenn a R b gilt, sonst false. Als Beispiel zur Verdeutlichung kann das Template std::less<T> aus der Standardbibliothek dienen, welches der Default-Parameter für die Vergleichsoperation ist. Es vergleicht die Elemente auf “kleiner” (durch Aufruf der operator< der betreffenden Klasse). Wenn gilt a<b, dann liefert std::less(a, b) true (und a wird links von b einsortiert/gesucht. Beispiel: Zeile 74-77). Wenn gilt a>b, dann liefert std::less(b, a) true (und a wird rechts von b einsortiert/gesucht. Beispiel: Zeile 78-81). Liefern beide Aufrufe false, so nimmt std::map an, dass a==b gilt (und der Schlüssel damit gefunden wurde/überschrieben werden kann. Beispiel: Zeile 82-85). Auf dieser Basis kann std::map nun einen Baum aufbauen/durchsuchen.

Die tatsächliche Implementierung von std::map ist ein klein wenig komplexer, als hier im Beispiel, da es noch andere Anforderungen an den Container gibt, die hier nicht dargestellt sind (bspw. muss er linear durchlaufen werden können). Die Elemente werden außerdem in Objekten vom Typ std::pair<Key,Value> gespeichert (die man beim Durchlaufen raus bekommt). Die Grundidee bleibt aber in etwa die gleiche.