C++ 11 unordered_map Zeit Komplexität

Question

Ich versuche herauszufinden, die beste Möglichkeit, einen Cache für Ressourcen zu tun. Ich suche hauptsächlich nach nativen C/C++/C++ 11 Lösungen (d. H. Ich habe keinen Boost und die Likes als Option).

Was ich tue, wenn sie aus dem Cache Abrufen von so etwas wie diese:

Object *ResourceManager::object_named(const char *name) { 
    if (_object_cache.find(name) == _object_cache.end()) { 
     _object_cache[name] = new Object(); 
    } 
    return _object_cache[name]; 
} 

Wo _object_cache definiert ist, so etwas wie: std::unordered_map <std::string, Object *> _object_cache;

Was ich frage mich, ist über die Zeit, Komplexität, dies zu tun, findet es eine lineare Zeitsuche oder ist es eine Art Nachschlageoperation?

Ich meine, wenn ich _object_cache["something"]; auf das angegebene Beispiel tun wird es entweder das Objekt zurückgeben oder wenn es nicht existiert, wird es den Standardkonstruktor aufrufen, ein Objekt einzufügen, was nicht das ist, was ich will. Ich finde das ein wenig kontraintuitiv, ich hätte erwartet, dass es auf irgendeine Art und Weise berichtet (nullptr zum Beispiel), dass ein value für den key nicht abgerufen werden konnte, nicht zweiterraten, was ich wollte.

Aber noch einmal, wenn ich eine find auf den Schlüssel, löst es eine große Suche, die tatsächlich in linearer Zeit (da der Schlüssel nicht gefunden wird, wird es auf jeden Schlüssel zu sehen) laufen?

Ist dies ein guter Weg, um es zu tun, oder hat jemand einige Vorschläge, vielleicht ist es möglich, einen Blick nach oben oder etwas zu wissen, ob der Schlüssel verfügbar ist oder nicht, kann ich oft zugreifen, und wenn es der Fall ist dass etwas Zeit mit Suchen verbracht wird, möchte ich es beseitigen oder es zumindest so schnell wie möglich machen.

Dankbar für jede Eingabe zu diesem Thema.

Answer 1

Der Standardkonstruktor (ausgelöst durch _object_cache["something"]) ist, was Sie wollen; der Standardkonstruktor für einen Zeigertyp (z. B. Object *) ergibt nullptr (8.5p6b1, Fußnote 103). So

:

auto &ptr = _object_cache[name]; 
if (!ptr) ptr = new Object; 
return ptr; 

Sie verwenden einen Verweis in die ungeordnete Karte (auto &ptr) als lokalen Variable, so dass Sie in die Karte zuordnen und Ihren Rückgabewert im gleichen Betrieb gesetzt. In C++ 03 oder wenn Sie explizit sein möchten, schreiben Sie Object *&ptr (eine Referenz auf einen Zeiger).

Beachten Sie, dass Sie wahrscheinlich lieber unique_ptr als einen RAW-Zeiger verwenden sollten, um sicherzustellen, dass Ihr Cache die Eigentumsrechte verwaltet.

Übrigens, find hat die gleiche Leistung wie operator[]; durchschnittliche Konstante, worst-case linear (nur wenn jeder Schlüssel in der ungeordneten Karte den gleichen Hash hat).

Answer 2

Hier ist, wie ich dies schreibe würde:

auto it = _object_cache.find(name); 
return it != _object_cache.end() 
     ? it->second 
     : _object_cache.emplace(name, new Object).first->second; 

Answer 3

Die Komplexität der find auf einer std :: unordered_map ist O (1) (konstant), speziell mit std :: string Tasten, die gut Hashing führende haben zu sehr geringen Kollisionsraten. Auch wenn der Name der Methode find lautet, wird kein linearer Scan ausgeführt, wie Sie angegeben haben.

Wenn Sie eine Art Caching durchführen möchten, ist dieser Container definitiv ein guter Anfang.

Answer 4

Beachten Sie, dass ein cache ist in der Regel nicht nur ein schneller O(1) Zugang, sondern auch ein begrenzt Datenstruktur. Die std::unordered_map wird ihre Größe dynamisch erhöhen, wenn mehr und mehr Elemente hinzugefügt werden. Wenn Ressourcen begrenzt sind (z. B. das Lesen riesiger Dateien von der Festplatte in den Speicher), möchten Sie eine beschränkte und schnelle Datenstruktur, um die Reaktionsfähigkeit Ihres Systems zu verbessern.

Im Gegensatz dazu ein cache wird eine Räumung Strategie ausgetüftelt size()capacity() erreicht, indem die am wenigsten wertvolle Element ersetzt werden.

Sie können eine cache über eine std::unordered_map implementieren. Die Räumungsstrategie kann dann implementiert werden, indem das Element insert() neu definiert wird. Wenn Sie einen N (für kleine und feste N) assoziativen Cache verwenden möchten (d. H. Ein Element kann höchstens N andere Elemente ersetzen), können Sie die -Schnittstelle verwenden, um einen der Bucket-Einträge zu ersetzen.

Für eine vollständig assoziative Cache (dh jedes Element ein anderes Element ersetzt werden kann), können Sie eine Least Recently Used Bereinigungsstrategie durch Hinzufügen eines std::list als sekundäre Datenstruktur verwenden:

using key_tracker_type = std::list<K>; 
using key_to_value_type = std::unordered_map< 
    K,std::pair<V,typename key_tracker_type::iterator> 
>; 

Durch Einwickeln diese beiden Strukturen innerhalb Ihrer cache Klasse, können Sie die insert() definieren, um einen Austausch auszulösen, wenn Ihre Kapazität voll ist. Wenn das passiert, geben Sie pop_front() den zuletzt verwendeten Artikel und push_back() den aktuellen Artikel in die Liste ein.

Auf Tim Day's blog there is an extensive example mit vollständigen Quellcode, der die obige Cache-Datenstruktur implementiert. Die Implementierung kann auch mit Boost.Bimap oder Boost.MultiIndex effizient durchgeführt werden.

Answer 5

Die insert/emplace-Schnittstellen zu map/unordered_map reichen aus, um das zu tun, was Sie wollen: Suchen Sie die Position und fügen Sie sie bei Bedarf ein. Da die abgebildeten Werte hier Zeiger sind, ist die Antwort von ekatmur ideal. Wenn Ihre Werte vollwertiges Objekte in der Karte sind eher als Zeiger, könnten Sie so etwas wie folgt verwenden:

Object& ResourceManager::object_named(const char *name, const Object& initialValue) { 
    return _object_cache.emplace(name, initialValue).first->second; 
} 

Die Werte name und initialValue Argumente machen bis zu dem Schlüssel-Wert-Paar, das eingeführt werden muss, wenn Es gibt keinen Schlüssel mit dem gleichen Wert wie name. Die emplace gibt ein Paar zurück, wobei second anzeigt, ob etwas eingefügt wurde (der Schlüssel in name ist ein neuer) - das ist uns hier egal; und first ist der Iterator, der auf den (möglicherweise neu erzeugten) Schlüssel-Wert-Paar-Eintrag mit einem Schlüssel zeigt, der dem Wert name entspricht. Wenn also der Schlüssel bereits vorhanden war, gibt die Dereferenzierung first das ursprüngliche Ojbect für den Schlüssel, der nicht mit initialValue überschrieben wurde; Andernfalls wurde der Schlüssel unter Verwendung des Werts name neu eingefügt, und der Wertebereich des Eintrags wurde von initialValue kopiert, und first weist darauf hin.

ekatmur Antwort ist dies gleichbedeutend mit:

Object& ResourceManager::object_named(const char *name) { 
    bool res; 
    auto iter = _object_cache.end(); 
    std::tie(iter, res) = _object_cache.emplace(name, nullptr); 
    if (res) { 
     iter->second = new Object(); // we inserted a null pointer - now replace it 
    } 
    return iter->second; 
} 

aber profitiert von der Tatsache, dass der Standard-konstruierte Zeigerwert erstellt von operator[] null ist, zu entscheiden, ob ein neuer Object Bedarf zugewiesen werden.Es ist prägnanter und einfacher zu lesen.