Ich weiß nicht, wie ein rot-schwarzer Baum mit String-Schlüsseln funktioniert. Ich habe es bereits mit Zahlen auf Youtube gesehen und es hat mich sehr verblüfft. Ich weiß jedoch sehr gut, wie unoredred_map funktioniert (das Interne von Hash-Maps). std :: map bleibt für mich esoterisch, aber ich habe gelesen und getestet, dass wenn wir nicht viele Änderungen an der std :: map haben, es Hash-Maps schlagen könnte.

Mein Fall ist einfach, ich habe eine std :: map von <std::string,bool>. Schlüssel enthält Pfade zu XML-Elementen (Beispiel eines Schlüssels: "Instrument_Roots / Instrument_Root / Rating_Type"), und ich verwende den booleschen Wert in meinem SAX-Parser, um festzustellen, ob wir ein bestimmtes Element erreicht haben.

Ich baue diese Karte "nur einmal"; und dann suche ich nur mit std :: find, ob ein bestimmter "Schlüssel" ("Pfad") vorhanden ist, um seinen Booleschen Wert auf "true" zu setzen, oder suche das erste Element, dem "true" als zugeordneter Wert und Verwendung zugeordnet ist Es entspricht dem "Schlüssel", und schließlich habe ich alle booleschen Werte auf false gesetzt, um sicherzustellen, dass nur ein einziger "Schlüssel" einen "wahren" booleschen Wert hat.

-1
Aminos 30 Dez. 2015 im 22:22

2 Antworten

Beste Antwort

Sie sollten nicht verstehen müssen, wie rot-schwarze Bäume funktionieren, um zu verstehen, wie ein std::map verwendet wird. Es ist einfach ein assoziatives Array, in dem die Schlüssel in der richtigen Reihenfolge sind (lexikografische Reihenfolge, im Fall von Zeichenfolgenschlüsseln, zumindest mit der Standardvergleichsfunktion). Das bedeutet, dass Sie nicht nur Schlüssel in einem std::map nachschlagen können, sondern auch Abfragen durchführen können, die von der Reihenfolge abhängen. Beispielsweise können Sie den größten Schlüssel in der Karte finden, der nicht größer als der Schlüssel ist, den Sie haben. Sie finden den nächstgrößeren Schlüssel. Oder (auch bei Zeichenfolgen) Sie finden alle Schlüssel, die mit demselben Präfix beginnen.

Wenn Sie alle Schlüssel-Wert-Paare in einem std::map durchlaufen, werden sie nach Schlüssel sortiert angezeigt. Das kann manchmal sehr nützlich sein.

Die zusätzliche Funktionalität hat ihren Preis. std::map ist normalerweise langsamer als std::unordered_map (wenn auch nicht immer; bei großen Zeichenfolgenschlüsseln ist der Aufwand für die Berechnung der Hash-Funktion möglicherweise spürbar), und die zugrunde liegende Datenstruktur hat einen gewissen Aufwand kann mehr Platz einnehmen. Der übliche Rat ist, ein std::map zu verwenden, wenn Sie feststellen, dass die Reihenfolge der Schlüssel wesentlich oder sogar nützlich ist.

Wenn Sie jedoch ein Benchmarking durchgeführt haben und zu dem Schluss gekommen sind, dass ein std::map für Ihre Anwendung auch schneller ist, verwenden Sie es :)


Es ist gelegentlich nützlich, eine Karte mit dem zugeordneten Typ bool zu haben, aber nur, wenn Sie zwischen Schlüsseln mit dem entsprechenden Wert false und Schlüsseln unterscheiden müssen, die überhaupt nicht in der Karte vorhanden sind. Tatsächlich bietet ein std::map<T, bool> (oder std::unordered_map<T, bool>) eine ternäre Auswahl für jeden möglichen Schlüssel.

Wenn Sie nicht zwischen den beiden false Fällen unterscheiden müssen und den Wert eines Schlüssels nicht häufig ändern, ist es möglicherweise besser, wenn Sie einen std::set (oder std::unordered_set) verwenden. ), die genau dieselbe Datenstruktur ist, jedoch ohne den Overhead von bool in jedem Element. (Obwohl nur ein Bit von bool nützlich ist, werden bei Überlegungen zur Ausrichtung möglicherweise 8 zusätzliche Bytes für jeden Eintrag verwendet.) Abgesehen vom Speicherplatz gibt es jedoch keinen großen (wenn überhaupt) Leistungsunterschied.

Wenn Sie wirklich einen ternären Fall benötigen, sollten Sie den Wert als enum und nicht als bool festlegen. Was bedeuten true und false im Zusammenhang mit Ihrer Nutzung? Ich vermute, dass sie nicht "wahr" und "falsch" bedeuten. Stattdessen bedeuten sie so etwas wie "ist ein Attributpfad" und "ist ein Elementpfad". Diese Unterscheidung könnte durch die Verwendung von enum PathType {ATTRIBUTE_PATH, ELEMENT_PATH}; viel deutlicher (und daher weniger unfallanfällig) gemacht werden. Dies erfordert keine zusätzlichen Ressourcen, da bool in jedem Fall acht Byte Speicher belegt (aufgrund der Ausrichtung).


Übrigens gibt es keine Garantie dafür, dass die zugrunde liegende Datenstruktur genau ein rot-schwarzer Baum ist, obwohl die Leistungsgarantien ohne eine Art selbstausgleichenden Baum nur schwer zu erreichen wären. Ich kenne eine solche Implementierung nicht, aber es wäre möglich, k-ary-Bäume (für einige kleine k) zu verwenden, um beispielsweise SIMD-Vektorvergleichsoperationen zu nutzen. Das müsste natürlich für geeignete Schlüsseltypen angepasst werden.

Wenn Sie rot-schwarze Bäume verstehen wollen, könnten Sie schlechter abschneiden als Robert Sedgewicks Standardlehrbuch über Algorithmen. Auf der Website des Buches finden Sie eine kurze illustrierte Erklärung im Kapitel über ausgeglichene Bäume.

3
rici 30 Dez. 2015 im 20:38

Ich würde Ihnen empfehlen, std :: unordered_set zu verwenden, da Sie dieses boolesche Flag wirklich nicht speichern müssen und diese XML-Tags auch nicht in sortierter Reihenfolge halten müssen, sodass std :: unordered_set mir als logisch und am meisten erscheint effiziente Wahl.

1
Pustovalov Dmitry 30 Dez. 2015 im 20:14