Boost.Intrusive und unordered_map

Question

Ich suche eine aufdringliche unordered_map zu verwenden. Aus irgendeinem Grund gibt es nur ein ungeordnetes_set in der Bibliothek. Es gibt auch eine aufdringliche Hashtabelle, aber ich bin mir nicht sicher, ob es die gleiche Funktionalität hat, auch hat es nicht die gleiche Schnittstelle.
Bin ich falsch und habe den unordered_map Link verpasst?
Wenn ich nicht bin, gibt es ein Tutorial, das mir helfen wird, eines zu implementieren?

Answer 1

Es ist eine interessante Frage. Boost.Intrusive scheint keine geordnete oder ungeordnete Kartenschnittstelle zu bieten. Es hat viele Implementierungstypen, die gut funktionieren, da die Karten sowohl geordnet (rot-schwarze Bäume, AVL-Bäume, Splay-Bäume) als auch ungeordnet (Hashtabellen) sind. Aber keine Karten und ich konnte dir nicht sagen warum.

Sie haben zwei Möglichkeiten, wie ich es sehe:

1. Nur hashtable verwenden: Die ungeordneten Container werden als Hash-Tabellen implementiert (und der einzige Grund, warum sie nicht genannthash_map ist Namenskollisionen mit bereits zu vermeiden -existierende Bibliotheken, die diesen Namen bereits verwenden). Das wird funktionieren, wenn Sie Ihre Arbeit erledigen wollen.
2. Wenn Sie wirklich Ihre eigenen implementieren möchten, sollten Sie sich die Schnittstellenbeschreibung für Boost.Intrusive's unordered_set ansehen. Ich habe die Implementierung nicht betrachtet, aber es ist fast sicher ein Wrapper um einen oder mehrere der Baumtypen. std::set und std::map werden beide normalerweise als Wrapper um einen rot-schwarzen Baum implementiert (in allen Standard-Bibliotheksimplementierungen, die ich mir angeschaut habe: GCCs, MSVCs und Apache's stdcxx). Nehmen Sie auch an, wie libstdC++ ihre Baumimplementierung in <map> und in <set> umschließt. Es ist eine Menge Boilerplate, viel davon langweilig, aber beide Arten verschieben fast alle Arbeiten auf den Baum. Etwas analoges passiert mit Sicherheit mit Boost.Intrusive unordered_set. Sie müssen sich die Unterschiede zwischen den Schnittstellen map und set ansehen und diese als Grundlage für das Ändern von unordered_set in unordered_map verwenden.

Ich habe das letztere getan. Es ist ein bisschen auf der langweiligen Seite, und ich empfehle sehr, Komponententests dafür zu schreiben (oder diejenigen zu stehlen, die mit libstdC++ oder Boost.Intrusive kommen). Aber es ist machbar. Ich auch sehr empfehlen, die Anforderungen Dokumente für Sets und Karten lesen, entweder bei SGI (set, map) oder für libstdc++

Update: wurde mir klar, warum sie nicht tun Karten sind: die aufdringlichen Behälter erfordern, dass Sie das einbetten Knoteninformationen für die Datenstruktur in der Wertart, in der Sie sie speichern. Für Karten müssten Sie dies sowohl für die Werte als auch für die Tasten tun. Es ist nicht, dass dies nicht möglich ist, aber die Standard-Implementierung für eine map verwendet die gleiche internen Typ wie die set s tun. Aber diese internen Typen haben nur einevalue_type Variable: um Schlüssel und Werte zu speichern, kopieren sie den Schlüssel und den Wert in diese Variable und speichern diese in den Knoten. Um dies mit einem intrusiven Typ (d. H. Ohne zu kopieren) zu tun, müssten Sie diesen Implementierungstyp so ändern, dass er nicht mit Sätzen kompatibel ist: er muss Referenzen auf die Schlüssel und Werte separat speichern. Um dies zu tun, müssen Sie auch die von Ihnen verwendete Implementierung ändern (wahrscheinlich hashtable). Auch das ist nicht unmöglich, aber die Bibliotheksdesigner versuchen wahrscheinlich, ernsthafte Code-Duplikationen zu vermeiden, so dass sie in Ermangelung einer einfachen Möglichkeit, dies zu implementieren, höchstwahrscheinlich beschlossen haben, Karten wegzulassen.

Macht das Sinn?

Answer 2

Es ist schon lange her, dass diese Frage gestellt wurde, aber ich denke, dass Leute, die hierher kommen, daran interessiert sein sollten, eine unordered_set als Karte zu verwenden. Die Lösung ist advanced insertions methods zu verwenden: man muss nur einen Schlüssel und seinen Wert in demselben speichern und es unter Verwendung insert_check und insert_commit einfügen.