[ Vorwort: Die assoziativen C ++ - Container wie std::map sind ein bisschen wie Mikro-Datenbanken mit nur einer Schlüsselspalte. Boost bimap hebt dies zu einer zweispaltigen Tabelle mit Nachschlagen in beiden Spalten, aber das ist, soweit es die Analogie betrifft - es gibt keine "Polymap", die die Idee verallgemeinert.]
Auf jeden Fall möchte ich Karten als Datenbanken betrachten und frage mich nun, ob es einen Iterator (oder eine andere Lösung) gibt, der es mir erlaubt, eine UNION aus mehreren Karten zu erstellen. Das heißt, alle Maps haben den gleichen Typ (oder Werttyp und mindestens Comparator), und ich möchte einen einzelnen Iterator, der die gesamte Sammlung als eine große Multimap behandelt (wiederholte Schlüssel sind OK) und lässt mich im richtigen unioned durchlaufen bestellen.
Gibt es so etwas, vielleicht in Boost? Oder ist es einfach, einen aufzubauen? Im Pseudocode:
%Vor%Zum Beispiel, wenn wir hatten:
%Vor%Dann möchte ich, dass der Iterator Folgendes erzeugt:
%Vor%Wie ich angekündigt habe , habe ich etwas ziemlich cooles.
Ich poste es jetzt, weil ich nicht sicher bin, ob ich heute Abend zurück bin, um es zu posten. Ich werde ein paar Worte zur Erklärung geben. (in diesem Post)
PS. Die Includes werden reduziert (auf etwa 20%); Ich werde wahrscheinlich auch etwas mehr allgemeine Arbeit an dem Code machen.
Über diesen Code kann viel gesagt werden: Er ist nicht sehr effizient und (noch) nicht sehr sauber. Es ist jedoch fast unendlich generisch und sollte wie alles andere skalieren. Der gesamte Code kann in einem GitHub gefunden werden:
Hier ist die Ausgabe der test.cpp, wie Sie sie finden können:
%Vor%So würde ich Thitons Antwort implementieren:
%Vor% Es hat eine etwas andere Verwendung als union_iterator<K, V> , aber es implementiert die Grundidee. Sie können den Konstruktor beliebig erweitern, um mehrere Maps zu akzeptieren, und sie in einer while (iterator.next()) -Schleife anstelle einer for (...) -Schleife verwenden.
BEARBEITEN: Ich habe next() vereinfacht, indem ich das ganze Poppen und Drücken gleichzeitig mache. So, jetzt ist es noch einfacher! (Man könnte auch etwas Mühe darauf verwenden, es zu einem STL-Iterator zu machen, aber das wird mühsam.)
Sehr einfache Lösung mit Boost function_output_iterator:
%Vor%Wir können diese Lösung schöner machen, indem wir boost :: set_union (range version) anstelle von std :: set_union verwenden.
UPD Die aktualisierte Version verwendet verschiedene Schlüssel- / Werttypen:
%Vor%UPD2 std :: set_union wird durch std :: merge
ersetztOder ist es einfach, einen auszurichten?
Das Rigging sollte ziemlich einfach sein: Für N Basiskarten enthält Ihr Iterator eine Prioritätswarteschlange, die durch die N Schlüssel der Elemente, auf die die Basisiteratoren zeigen, priorisiert ist. Zur Dereferenzierung dereferenzieren Sie den Iterator an der Warteschlangenfront. Erhöhen Sie für Iterator den Iterator an der Queue-Front und fügen Sie ihn, falls das Inkrement nicht am Ende ist, erneut ein.
So kann es ganz einfach gemacht werden:
%Vor%Aber das eigentliche Problem ist die Implementierung aller verbleibenden Member-Funktionen, die von normalen Iteratoren benötigt werden :-). Boost hat einige Lib, die dir dabei helfen, aber es könnte immer noch ziemlich schwierig sein.
Dies ist kein Iterator, wie Sie ihn verlangten, aber ich habe diese Funktion in der Standardbibliothek gefunden:
§ 25.4.5.2 set_union [set.union]
%Vor%
Es gibt auch std::set_intersection , std::set_difference und std::set_symmetric_difference