Boost.Intrusive und unordered_map

Question

Ich suche eine intrusive unordered_map zu verwenden. Aus irgendeinem Grund gibt es nur eine unordered_set in der Bibliothek. Es gibt auch eine intrusive hashtable aber ich bin nicht sicher, ob es die gleiche functunality hat, auch ist es nicht die gleiche Schnittstelle hat.
Bin ich falsch, und ich verpasste den unordered_map Link?
Wenn ich nicht, ist es ein Tutorial, das mir ein implementieren helfen?

Answer 1

Es ist eine interessante Frage. Boost.Intrusive scheint keine Karte Schnittstelle zur Verfügung zu stellen, geordnet oder ungeordnet. Es hat eine Menge Implementierung-Typen, die fein funktionieren wie Karten beide bestellt (rot-schwarze Bäume, AVL-Bäume, spreizen Bäume) und ungeordnete (Hash-Tabellen). Aber keine Karten und ich könnte nicht sagen, warum.

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

1. Just hashtable verwenden: Die ungeordneten Container werden als Hash-Tabellen implementiert (und der einzige Grund, warum sie es nicht sind genannt hash_map ist Namenskollisionen mit bereits vorhandenen Bibliotheken zu vermeiden, diesen Namen mit bereits). Das wird funktionieren, wenn Sie Ihre Arbeit erledigen wollen.
2. Wenn Sie wirklich Ihre eigene umsetzen wollen, möchten Sie in der Schnittstellenbeschreibung einen Blick nehmen für Boost.Intrusive der unordered_set . Ich habe nicht an der Umsetzung gesucht, aber es ist fast sicher ein Wrapper um einen oder mehrere der Baumart. std::set und std::map sind beide typischerweise als Wrapper um einen rot-schwarz-Baum implementiert (: GCC, MSVC ist, und Apache stdcxx in all Standard-Bibliothek Implementierungen Ich habe betrachtet). Nehmen Sie auch an, wie libstdc ++ wickelt ihre Baum-Implementierung in <map> und in <set>. Es ist eine Menge von vorformulierten, viel davon mühsam, aber beide Arten verschieben fast die ganze Arbeit auf den Baum. Etwas Analoges geschieht mit ziemlicher Sicherheit mit Boost.Intrusive des unordered_set. Sie werden auf die Unterschiede zwischen der Karte suchen müssen und Schnittstellen festgelegt, und das zum Modifizieren unordered_set in unordered_map als Basis verwenden.

Ich habe das letztere getan. Es ist ein bisschen auf der langweiligen Seite, und ich sehr empfehlen, für sie zu schreiben Unit-Tests (oder die, die stehlen, die mit libstdc kommen ++ oder Boost.Intrusive). Aber es ist machbar. Ich auch sehr empfehlen, die Anforderungen Dokumente für Sets und Karten lesen, entweder bei SGI ( Satz Karte ) oder libstdc ++

Update: wird mir klar, warum sie Karten nicht tun: die aufdringlichen Behälter erfordern, dass Sie die Knoteninformationen für die Datenstruktur in dem Werttyp einbetten Sie darin sind zu speichern. Für Karten würden Sie dies für tun haben, beide Werte und die Tasten . Es ist nicht, dass dies nicht möglich ist, aber die Standard-Implementierung für eine map verwendet den gleichen internen Typen wie die sets tun. Aber diese internen Typen haben nur ein value_type Variable: zum Speichern von Schlüsseln und Werten, die sie kopieren Sie den Schlüssel und den Wert in diese Variablen und speichern, die in den Knoten. Um das zu tun mit einer aufdringlichen Art (das heißt ohne Kopieren) Sie müssen, dass die Umsetzung Typen ändern mit Sätzen unvereinbar: es hat speichern Verweise auf die Schlüssel und Werte getrennt . Also, es zu tun Sie auch ändern haben die Implementierung Sie verwenden (wahrscheinlich hashtable). Wieder nicht unmöglich, aber die Bibliothek Designer versuchen, wahrscheinlich ernsthafte Code-Duplizierung zu vermeiden, so in Abwesenheit von einfachen Weg, dies zu implementieren, sie haben höchstwahrscheinliche Karten verlassen entschieden werden.

Ist das sinnvoll?

Answer 2

Es ist schon eine lange Zeit, da diese Frage gestellt wurde, aber ich glaube, die Leute kommen hier interessiert sein sollen, wie man ein unordered_set als eine Karte zu verwenden. Die Lösung zu verwenden ist erweiterte Einfügungen Methoden : man muss nur speichern, ein Schlüssel und dessen Wert in der gleichen value_type, und setzen sie sie mit insert_commit .