Da ich hauptsächlich aus C ++ stammt, schreibe ich jetzt etwas Wut in Java. Etwas, das ich in C ++ unter Verwendung der STL grundlegend finde, scheint in Java umständlicher zu sein, als ich denke, dass es sein sollte. Meine Schlussfolgerung ist, dass es wahrscheinlich eine bessere Java-Sprache gibt, die ich noch nicht kenne. Hier ist ein Beispiel mit Pseudocode.
Ich habe eine Sammlung von Dingen, die eine natürliche Ordnungsrelation basierend auf einigen Elementvariablen haben, die Strings sind.
%Vor%In C ++ könnte ich einen Ordnungsoperator & lt; (Thing, Thing) definieren und diese in ein std :: set setzen. ZB
%Vor%Ich kann dann Elemente in O (log N) Zeit finden, indem ich set :: find für den Fall verwende, dass es eine Sache gibt. Verwenden zusätzlicher Überladungen des Operators & lt; (). Ich kann mit key1 oder key1 und key2 mit std :: lower_bound oder std :: equal_range suchen. Zum Beispiel:
%Vor%Um dies weniger abstrakt zu machen, ist key1 der Name und key2 die Version. Ich kann fragen, haben wir irgendeine Software namens Foobar oder genauer gesagt haben wir Foobar v1.0.
Auf den ersten Blick scheint das direkteste Äquivalent von std :: in Tree das TreeSet zu sein Die Reihenfolge kann implementiert werden, indem die Komparatorschnittstelle unterklassifiziert wird. Für das, worüber ich spreche, sieht es jedoch so aus, als wären mehrere Maps in Java erforderlich. In C ++ würde ich nur einen assoziativen Container wie std :: map verwenden, wenn ich den Wert ändern wollte. In einem C ++ std :: set wie in einem Java TreeSet ist der Wert ein eigener Schlüssel. In C ++ kann ich jedoch Komparatoren schreiben, um "Thing" mit "std :: string" zu vergleichen, indem man key1 oder key2 benutzt und eine bestimmte Sache in einer std :: Menge findet. Es sieht für mich so aus, als müsste Map in Java verwendet werden. Sonst (weil Comparator nur einen Typparameter hat) Sie enden mit einem Durcheinander wie:
%Vor%Wenn Sie das tun, können Sie (in Klasse Thing) schreiben:
%Vor%Mit einem Java-Set können Sie nur die Existenz testen, aber nicht das Objekt, nach dem Sie suchen. z.B. Du kannst nicht
%Vor%weil Methoden wie floor () nur Objekte vom Werttyp (d. h. Thing) akzeptieren
Die offensichtliche Lösung besteht darin, für jeden Schlüssel eine Karte zu verwenden.
%Vor%Aus einem C ++ - Hintergrund scheint dies unnötig aufgebläht zu sein. Warum sollte ich den Schlüssel noch einmal speichern, wenn das Ding ihn schon enthält? Wenn ich zwei Schlüssel habe, ist es noch schlimmer. Ich brauche zwei Karten.
%Vor%Ich kopiere jetzt nicht nur den Schlüssel, sondern erstelle auch zusätzliche unnötige Baumdatenstrukturen (oder HashMaps mit besserer Laufzeitleistung). Für die oben beschriebene Bestellimplementierung könnte dies auch "einfach falsch" sein, da jeder Schlüssel für sich genommen nur eine Teilreihenfolge und nicht eine Gesamtordnung für eine Menge von Dingen bildet.
Ich habe Fragen über die Suche hier unter Verwendung der linearen Suche, die fast immer die schlechteste Wahl ist, beantwortet. ZB
Suche nach allen Objekten mit einer bestimmten Eigenschaft in einer Sammlung
Ich stelle fest, dass es eine Version von BinarySearch gibt, die ein Comparator-Objekt als Argument akzeptiert, es aber den Index des Elements und nicht das Element selbst zurückgibt. Dies bedeutet, dass nach der Verwendung von get () ein unnötiger Aufruf von get () erfolgt, sofern die Sammlung dies unterstützt.
Was ist also der Java-Weg, um dies effizient in Zeit und Raum zu tun?
Der Java Weg dies zu tun ist ja, Map zu benutzen.
Aus einem C ++ - Hintergrund scheint dies unnötig aufgebläht zu sein. Warum sollte ich den Schlüssel noch einmal speichern, wenn es bereits darin enthalten ist?
Das ist nicht so viel Aufwand, wie Sie denken. Sie speichern einen zusätzlichen Verweis auf String mit einem Gesamtkostenwert von ... 4 Byte. (Tatsächlich sind die Kosten gleich Null: Die Implementierung TreeSet benötigt genau so viel Speicher wie TreeMap .)
Wenn Sie mit beiden Schlüsseln suchen möchten, können Sie eine Comparator<Thing> verwenden, die beide Schlüssel vergleicht, oder make Thing implementieren Comparable<Thing> und dann TreeSet<Thing> beibehalten. Das ist viel kompakter als das ... unangenehme Comparator , das du oben geschrieben hast. Wenn Sie mit einem Schlüssel suchen möchten, verwenden Sie einfach Map<String, Thing> . Wenn Sie wirklich mit beiden suchen wollen, dann pflegen Sie beide. (In der Praxis musste ich das fast nie tun ... und die Autoren des JDK Collections-Frameworks dachten nicht, dass Sie das auch sehr oft tun müssten.)
Tags und Links java c++ map set collections