11.9 Algorithmen in Collections
 
Um Probleme in der Informatik zu lösen, ist die Wahl einer geeigneten Datenstruktur nur der erste Schritt. Im zweiten Schritt müssen Algorithmen implementiert werden. Da viele Algorithmen immer wiederkehrende (Teil-)Probleme lösen, hilft uns auch hier die Java-Bibliothek mit einigen Standardalgorithmen weiter. Dazu zählen etwa Funktionen zum Sortieren und Suchen in Containern und das Füllen von Containern. Um die Methoden möglichst flexibel einzusetzen, definierten die Bibliotheksentwickler die Klasse Collections – die wir nicht mit dem Interface Collection verwechseln dürfen. Collections bietet die notwendigen Algorithmen als statische Funktionen an. Allerdings sind viele Algorithmen nur auf List-Objekten definiert; die Implementierung von Collection reicht oft nicht aus. Das ist nicht erstaunlich, denn wenn ein Container keine Ordnung definiert, kann er nicht sortiert werden. Auch die binäre Suche erfordert Container mit einer impliziten Reihenfolge der Elemente. Nur Min- und Max-Methoden arbeiten auf allgemeinen Collection-Objekten. Nutzt die Collections-Klasse keine List-Objekte, arbeitet sie doch nur mit Collection-Objekten und nicht mit Iteratoren.
Alle Funktionen sind statisch, sodass Collections als Utility-Klasse wie Math gewertet werden kann. Ein Exemplar von Collections lässt sich nicht anlegen – der Konstruktor ist privat.
Beispiel Elemente gehen geordnet in eine Liste hinein und kommen durchgeschüttelt wieder heraus. Das wahllose Vertauschen der Elemente übernimmt Collections.shuffle(). Da shuffle() allgemein auf List-Objekten arbeitet, können wir hier LinkedList-, Vector- und ArrayList-Objekte einsetzen.
Listing 11.11
Shuffle.java, main()
List<String> v = new ArrayList<String>();
Collections.addAll( v, "Bube", "Dame", "König", "Ass" );
Collections.shuffle( v );
System.out.println( v ); // z. B. [König, Ass, Bube, Dame]
|
Die shuffle()-Methode gibt es in zwei Ausführungen: in der oben verwendeten und in einer erweiterten Variante, die als zweiten Parameter ein Random-Objekt erwartet.
class java.util.Collections
|
|
static void shuffle( List<?> list )
Würfelt die Elemente der Liste durcheinander. Dafür wird ein Standard-Generator für Zufallszahlen verwendet. |
|
static void shuffle( List<?> list, Random rnd )
Würfelt die Elemente der Liste durcheinander und benutzt dafür den Random-Generator rnd. |
11.9.1 Datenmanipulation: Umdrehen, Füllen, Kopieren
 
Collections.reverse() dreht die Reihenfolge der Elemente in einer Liste um. Die Laufzeit ist linear zur Anzahl der Elemente. Mit der fill()-Methode lässt sich eine Liste in linearer Zeit mit mehreren identischen Elementen belegen. Nützlich ist dies, wenn eine Liste mit lauter identischen Elementen initialisiert werden muss. Das heißt aber, dass es immer das gleiche Objekt ist, das an allen Positionen sitzt. Es ist die Frage, ob dies immer so sinnvoll und nützlich ist.
Collections.copy(List quelle, List ziel) kopiert alle Elemente von quelle in die Liste ziel und überschreibt dabei solche, die eventuell schon an den entsprechenden Positionen der Zielliste liegen. Die Zielliste muss mindestens so lang wie die Quellliste sein, andernfalls wird eine IndexOutOfBoundsException ausgeworfen. Hat das Ziel weitere Elemente, ist das egal, weil diese nicht angetastet werden.
class java.util.Collections
|
|
static void reverse( List<?> l )
Kehrt die Reihenfolge der Elemente in der Liste um. |
|
static <T> void fill( List<? super T> list, T obj )
Überschreibt jedes vorhandene Element der Liste mit dem Element o. |
|
static <T> void copy( List<? super T> dest, List<? extends T> src )
Kopiert alle Elemente von dest nach src und überschreibt dabei die ersten Elemente von src. Ist src zu klein, gibt es eine IndexOutOfBoundsException. |
11.9.2 Vergleichen von Objekten mit Comparator und Comparable
 
Sollen beliebige Objekte verglichen werden, muss es eine Ordnung dieser Objekte geben. Wie sollte das System sonst selbstständig entscheiden können, ob ein Personen-Objekt kleiner als ein anderes Personen-Objekt ist. Weil die eine Person 1,50 Meter groß ist, die andere aber 1,80 Meter, oder weil die eine Person eine Million Euro auf dem Konto hat und die andere nur fünf?
Es mag überraschen, dass es in Java 2 zwei unterschiedliche Schnittstellen (in zwei unterschiedlichen Paketen) zur Sortierunterstützung gibt:
|
java.util.Comparator definiert die Methode int compare(Object o1, Object o2). Eine Klasse, die sich Comparator nennt, implementiert die Schnittstelle und legt auf diese Weise die Ordnung fest. |
|
Die Schnittstelle java.lang.Comparable schreibt die Methode int compareTo(Object o) vor. Die Klasse implementiert die Schnittstelle, und ein Objekt kann sich mit einem anderen Objekt vergleichen. Da im Allgemeinen nur ein Sortierkriterium implementiert wird, heißt dieses natürliche Ordnung (engl. natural ordering). |
Während Comparable im Allgemeinen nur ein Sortierkriterium umsetzt, kann es viele Extraklassen vom Typ Comparator geben, die jeweils unterschiedliche Ordnungen definieren. Ein Comparator für Diskotheken könnte zum Beispiel nach der Anzahl der Personen oder auch nach der Größe in Quadratmetern sortieren; die Implementierung von Comparable wäre nicht sinnvoll, weil hier nur ein Kriterium natürlich umgesetzt werden kann, eine Disko aber nicht die Ordnung hat.
Die Schnittstelle Comparable
Comparable definiert nur eine Methode:
interface java.lang.Comparable<T>
|
|
int compareTo( T o )
Vergleicht sich mit einem Anderen. |
Ganz wichtig ist neben einer Implementierung von compareTo() auch die passende Realisierung in equals(). Sie ist erst dann konsistent, wenn e1.compareTo(e2) == 0 das gleiche Ergebnis wie e1.equals(e2) liefert, wobei e1 und e2 Objekte der gleichen Klasse sind. Ein Verstoß dieser Regel kann bei sortierten Mengen schnell Probleme bereiten; ein Beispiel nennt die API-Dokumentation.
e.compareTo(null) sollte eine NullPointerException auslösen, auch wenn e.equals(null) die Rückgabe false liefert.
Die Schnittstelle Comparator
Die Schnittstelle Comparator definiert zwei Methoden:
interface java.util.Comparator<T>
|
|
int compare( T o1, T o2 )
Vergleicht zwei Argumente auf ihre Ordnung. |
|
boolean equals( Object obj )
Testet, ob Comparator-Objekte gleich sind. Das testet keine Gleichheit von Objekten! |
Die Methode equals() muss nicht implementiert werden, da ja schon aus Object eine Implementierung bereitgestellt wird.
 Hier klicken, um das Bild zu Vergrößern
Comparable und Comparator in der Java-API
Eine Implementierung von Comparable findet sich genau dort, wo eine natürliche Ordnung nahe liegt, etwa bei:
|
String |
|
BigDecimal, BigInteger, Byte, Character, Double, Float, Integer, Long, Short |
|
Date |
|
File, URI |
|
Enum |
|
TimeUnit |
Von Comparator finden wir in der API-Dokumentation nur java.text.Collator vermerkt.
Um Such- oder Sortier-Operationen möglichst unabhängig von Klassen zu machen, die eine natürliche Ordnung besitzen oder die eine Ordnung über einen externen Comparator definiert bekommen, haben Utility-Klassen wie java.util.Arrays oder java.util. Collections oft zwei Arten von Methoden: Einmal Funktionen mit einem zusätzlichen Comparator und einmal ohne. Wird kein Comparator angegeben, so müssen die Objekte vom Typ Comparable sein.
|
static void sort( Object[] a )
Sortiert die Elemente. Zum Vergleichen wird vorausgesetzt, dass sie die Klasse Comparable implementieren. Falls sie dies nicht tun, wird eine Ausnahme ausgelöst. |
|
static <T> void sort( T[] a, Comparator<? super T> c )
Vergleicht die Objekte mit einem externen Comparator. Falls die Objekte auch noch Comparable implementieren, wird diese Sortierordnung nicht genutzt. |
|
static int binarySearch( Object[] a, Object key )
Sucht binär nach key. Die Objekte im Feld müssen Comparable implementieren. |
|
static <T> int binarySearch( T[] a, T key, Comparator<? super T> c )
Sucht im sortierten Feld. Der Comparator bestimmt das Sortierkriterium. |
class java.util. Collections
|
|
static <T extends Comparable<? super T>> void sort( List<T> list ) |
|
static <T> void sort( List<T> list, Comparator<? super T> c ) |
|
static <T> int binarySearch( List<? extends Comparable<? super T>> list, T key ) |
|
static <T> int binarySearch( List<? extends T> list, T key, Comparator<? super T> c ) |
Die Datenstrukturen, die eine Sortierung verlangen, wie TreeSet oder TreeMap, nehmen entweder einen Comparator entgegen oder erwarten eine Implementierung von Comparable.
11.9.3 Größten und kleinsten Wert einer Collection finden
 
Die Methoden min() und max() suchen das kleinste und größte Element einer Collection. Die Laufzeit ist linear zur Größe der Collection. Die Methoden unterscheiden nicht, ob die Elemente der Datenstruktur schon sortiert sind oder nicht.
class java.util.Collections
|
|
static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll) |
|
static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp) |
|
static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll) |
|
static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp) |
Wir sehen, dass es eine überladene Version der jeweiligen Methode gibt, da für beliebige Objekte eventuell ein Comparator-Objekt erforderlich ist, das den Vergleich vornimmt. Es sei auch bemerkt, dass dies mit die komplexesten Beispiele für Generics sind.
Bedeutung von Comparable bei min()
Bisher kennen wir nur min() und max() der Utility-Klasse Math auf den numerischen Datentypen. Wenn wir also ein String-Objekt in eine Liste packen oder ein Double-Objekt in eine Menge, werden sie korrekt gesucht, da insbesondere die Wrapper-Klassen die Schnittstelle Comparable implementieren. In der Implementierung min() ohne extra Comparator lässt sich gut der Aufruf von compareTo() sehen.
public static <T extends Object & Comparable<? super T>>
T min( Collection<? extends T> coll )
{
Iterator<? extends T> i = coll.iterator();
T candidate = i.next();
while( i.hasNext() )
{
T next = i.next();
if ( next.compareTo(candidate) < 0 )
candidate = next;
}
return candidate;
}
Die generische Schreibweise verlangt, dass die Elemente in der Collection vom Typ Comparable sein müssen. Genauer steht dort, dass die Collection typisiert werden muss mit etwas, das mindestens T ist, wobei T extends Object & Comparable<? super T>. (Damit später die Methode compareTo() aufgerufen werden kann, wird das im Bytecode verankerte allgemeine java.lang.Object auf ein Comparable gecastet.)
11.9.4 Sortieren
 
Mit zwei sort()-Methoden bietet die Utility-Klasse Collections die Möglichkeit, die Elemente einer Liste stabil zu sortieren.
|
sort(List): Die Variante nutzt die natürliche Ordnung, also Zahlen nach der Größe (19<34) und Zeichenketten alphanumerisch (Hansi<Raphael<Ulli). |
|
sort(List,Comparator): Die zweite Form arbeitet mit einem speziellen Comparator-Objekt, welches jeweils zwei Objekte mit seiner compare(Object, Object)-Methode vergleicht. Die natürliche Ordnung spielt keine Rolle. |
Die Sortierfunktion arbeitet nur mit List-Objekten. Bei den anderen Datenstrukturen würde das ohnehin kaum sinnvoll sein, weil diese entweder unsortiert sind oder extern eine bestimmte Ordnung aufweisen, wie oben schon angemerkt. Eine analoge Sortierfunktion für die Elemente von Arrays, nämlich sort(), gibt es aber noch in der Klasse Array.
class java.util.Collections
|
|
static <T extends Comparable<? super T>> void sort( List<T> list )
Sortiert die Elemente der Liste gemäß ihrer natürlichen Ordnung, die ihnen die Implementierung über Comparable gibt. |
|
static <T> void sort( List<T> list, Comparator<? super T> c )
Sortiert die Elemente der Liste gemäß der Ordnung, die durch den Comparator c festgelegt wird. |
Beispielprogramm zum Sortieren
Das folgende Programm sortiert eine Reihe von Zeichenketten aufsteigend. Zunächst nutzt es die Methode Arrays.asList(), um aus einem String-Feld eine Liste zu konstruieren und daraus eine veränderbare Liste aufzubauen. (Leider gibt es keinen Konstruktor für ArrayList, der ein Array von Strings direkt verarbeitet, daher dieser Umweg.) Anschließend setzten wir mit der unter Java 5 eingeführten neuen Funktion Collections.addAll() eine Reihe von weiteren Strings in die Liste. Praktisch an der Funktion addAll() ist, dass sie beliebig viele Argumente über ein Vargs annimmt.
Listing 11.12
CollectionsSortDemo.java
import java.util.*;
public class CollectionsSortDemo
{
public static void main( String[] args )
{
List<String> list = new ArrayList<String>(
Arrays.asList( new String[]{
"Noah", "Abraham", "Isaak", "Ismael", "Moses", "Jesus", "Muhammed" }
) );
Collections.addAll( list,
"Saskia", "Regina", "Angela", "Astrid", "Manuela", "Silke",
"Linda", "Daniela", "Silvia", "Samah", "Radhia", "Mejda"
);
Collections.sort ( list );
System.out.println( list );
}
}
Merge-Sort steht dahinter
Der Methode sort() in der Klasse Collections liegt als Algorithmus ein optimierter Merge-Sort zugrunde. Er arbeitet in der Regel sehr schnell; die Laufzeit beträgt n*log(n), wenn n Elemente zu sortieren sind. Obwohl Quick-Sort bei einigen Sortierfolgen schneller ist, hat dieser den großen Nachteil, dass er nicht stabil arbeitet und keine garantierte Laufzeit von n*log(n) besitzt.1
Auf fast sortierten Datenfolgen arbeitet jedoch Merge-Sort wesentlich schneller.
Implementierung von sort() über Arrays.sort()
Die sort()-Methode arbeitet intern mit der toArray()-Funktion der Klasse List. Die Elemente der Liste werden immer erst in ein temporäres Array kopiert und anschließend wird die sort()-Methode der Arrays-Klasse zum Sortieren genutzt. Am Ende überträgt ein ListIterator den sortierten Array-Inhalt zurück in die Liste.
public static <T extends Comparable<? super T>> void sort( List<T> list )
{
Object[] a = list.toArray();
Arrays.sort( a );
ListIterator<T> i = list.listIterator();
for ( int j = 0; j < a.length; j++ ) {
i.next();
i.set( (T)a[j] );
}
}
Stabiles Sortieren
Stabile Sortieralgorithmen lassen die Reihenfolge von gleichen Elementen unverändert. Dies spielt dann eine Rolle, wenn nicht alle Attribute der Elemente in den Vergleich eingehen. Wenn wir etwa die Folge (27,1), (3,2), (56,1), (4,2) (3,1) nach der zweiten Komponente der Zahlenpaare sortieren und anschließend nach der ersten Komponente, dann erwarten wir, dass (3,1) vor (3,2) liegt und der Algorithmus die Reihenfolge der beiden Zahlenpaare nicht wieder ändert. Diese Eigenschaft ist nur dann garantiert, wenn die zweite Sortierung mit einem stabilen Sortieralgorithmus erfolgt. Etwas praktischer lässt sich diese Eigenschaft an einem E-Mail-Programm demonstrieren. Sortieren wir unsere Nachrichten zuerst nach dem Datum und anschließend nach dem Absender, so sollen die Nachrichten von demselben Absender immer noch nach dem Datum sortiert bleiben.
Strings sortieren, auch unabhängig von der Groß- und Kleinschreibung
Die Klasse String realisiert über die Implementierung von Comparable eine natürliche Sortierung. Alle String-Objekte, die in einem Feld sind, können problemlos über Array.sort() und alle Strings in Collection-Objekten über Collections.sort() sortiert werden.
Kommen weitere Sortierkriterien hinzu – und die gibt es in den unterschiedlichen Ländern allemal –, so helfen die Collator-Objekte, da sie spezielle Comparator-Objekte sind.
Comparator deutschCollator = Collator.getInstance( Locale.GERMAN );
Zum Sortieren unabhängig von der Groß- und Kleinschreibung bietet die Klasse String eine praktische Konstante: String.CASE_INSENSITIVE_ORDER. Das ist ein Comparator<String>, der gut als Argument für sort() passt. (Im Übrigen ist es die einzige statische Variable der Klasse.)
Daten in umgekehrter Reihenfolge sortieren
Da es keine spezielle Methode reverseSort() gibt, ist hier ein spezielles Comparator-Objekt im Einsatz, um Daten entgegensetzt zu ihrer natürlichen Reihenfolge zu sortieren. Mit der statischen Funktion reverseOrder() der Klasse Collections können wir ein geeignetes Comparator-Exemplar anfordern. Im folgenden Programm fügen wir einige Zeichenketten in eine Liste ein, die wir anschließend absteigend sortieren lassen:
Listing 11.13
CollectionsReverseSortDemo.java
import java.util.*;
public class CollectionsReverseSortDemo
{
public static void main( String[] args )
{
List<String> list = new ArrayList<String>();
Collections.addAll( list, "Adam", "Eva", "Set", "Enosch", "Kenan", "Mahalalel");
Comparator<String> comparator = Collections.<String>reverseOrder();
Collections.sort( list, comparator );
System.out.println( list ); // [Set, Mahalalel, Kenan, Eva, Enosch, Adam]
}
}
Eine andere Möglichkeit für umgekehrt sortierte Listen besteht darin, erst die Liste mit sort() zu sortieren und anschließend mit Collections.reverse(List<?> list) umzudrehen. Die Lösung mit einem Comparator über reverseOrder() ist jedoch stabil. Für einen existierenden Comparator liefert Collections.reverseOrder(Comparator<T> cmp) einen Comparator<T>, der genau umgekehrt arbeitet.
11.9.5 Elemente in der Collection suchen
 
Die Collection-Klassen enthalten mit contains(Object) eine Methode, die entweder true oder false zurückgibt, wenn ein Element gefunden wurde oder nicht. Wenn allerdings eine Liste sortiert ist, lässt sich eine Suche schneller durchführen. Diesem Verfahren, der Halbierungssuche (auch binäre Suche, engl. binary search), liegt eine einfache Idee zugrunde. Wir beginnen die Suche nach einem Objekt in der Mitte der Liste. Ist das gesuchte Objekt kleiner als das mittlere Listen-Element, dann muss es sich links von der Mitte befinden, andernfalls rechts. Die Liste wird also in zwei gleich große Abschnitte unterteilt, von denen nur einer weiter durchsucht werden muss. Diesen Vorgang wiederholen wir so oft, bis das Element gefunden wurde. Auf diese Weise ist die Suche sehr schnell und benötigt höchstens log(n) Listenhalbierungen, bei einer Liste mit n Elementen. Es ist jedoch gut möglich, dass das gesuchte Element in der Liste nicht vorkommt. Dieser Fall wird erkannt, wenn durch das wiederholte Halbieren der Liste ein Listenabschnitt mit nur einem Element entstanden ist. Stimmt dieses eine Element nicht mit dem gesuchten Objekt überein, ist das Ergebnis der Suche ein »Nicht gefunden«. Die Suche nach einem nicht vorhandenen Element ist geringfügig aufwändiger als eine erfolgreiche Suche, benötigt aber ebenfalls nur logarithmisch viele Halbierungsschritte. Enthält die Liste mehrere gleiche Elemente, dann ist nicht gesichert, welches davon bei der Suche gefunden wird. Besteht die Liste etwa aus zehn Zahlen mit dem Wert 22, dann liefert der Algorithmus das fünfte Element.
Von binarySearch() gibt es zwei Varianten. Die erste Methode nimmt an, dass die Werte in ihrer natürlichen Form sortiert sind. Die zweite arbeitet wieder mit einem Comparator-Objekt zusammen. Beide Methoden liefern die Position des gefundenen Objekts innerhalb der Liste als Ergebnis. Wurde kein passendes Element gefunden, ist das Ergebnis eine negative Zahl und beschreibt recht trickreich die Stelle, an der der Algorithmus den letzten Vergleich durchgeführt hat. Der Rückgabewert ist dann »– Einfügepunkt – 1« und der Einfügepunkt die Position in der Liste, an die der Wert gemäß Sortierung eingesetzt werden kann. Wir können folgende Programmzeilen verwenden, um einen nicht gefundenen Wert gleich passend einzufügen:
int pos = Collections.binarySearch( l, key );
if ( pos < 0 )
l.add( -pos – 1, key);
Ist die Liste nicht sortiert, kann die Halbierungssuche nicht richtig funktionieren, da sie möglicherweise in die falsche Richtung läuft und das Element sich in der anderen Hälfte der unterteilten Liste befindet. Eine nicht sortierte Liste lässt sich jedoch mit sort() sortieren. Es ist aber immer noch schneller, in einer unsortierten Liste zu suchen, – Laufzeit O(n) –, als erst die Liste zu sortieren – Laufzeit O(n log(n)) – und darin mit Halbierungssuche zu suchen, – Laufzeit O(log(n)). Wenn ausreichend viele Suchvorgänge nacheinander durchzuführen sind, lohnt sich das vorherige Sortieren der Liste natürlich.
class java.util.Collections
|
|
static <T extends Object & Comparable<? super T>>
int binarySearch(List<? extends T> list, T key)
Sucht ein Element in der Liste. Gibt die Position zurück oder einen Wert kleiner 0, falls kein passendes Element in der Liste ist. |
|
static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)
Sucht ein Element mit Hilfe des Comparator-Objekts in der Liste. Gibt die Position oder einen Wert kleiner 0 zurück, falls kein passendes Element in der Liste ist. |
Häufigkeit eines Elements
Collections.frequency(Collection, Object) gibt seit Java 5 die Anzahl der Elemente zurück, die zu einem Such-Objekt equals()-gleich sind.
Beispiel Ermittle die Anzahl :-) Smilies.
String s = "Hallo :-) Suppi :-)";
int i = Collections.frequency ( Arrays.asList(s.split("\\s")), ":-)" );
System.out.println( i ); // 2
|
class java.util.Collections
|
|
static int frequency( Collection<?> c, Object o )
Liefert die Anzahl der Elemente, die mit o gleich sind, genauer gesagt, für die gilt: o == null ? e == null : o.equals(e). |
11.9.6 Nicht-änderbare Datenstrukturen
 
So wie synchronizedXXX() einen Wrapper um existierende Datenstrukturen legt, verfahren auch diverse unmodifiableXXX()-Methoden der Utility-Klasse Collections. Sie lassen die Lese-Methoden zu dem Container durch, blocken Modifizierungsmethoden wie add() aber durch eine UnsupportedOperationException ab.
11.9.7 nCopies()
 
Die statische Funktion nCopies(int number, Object element) erzeugt eine Liste mit der gewünschten Anzahl von Elementen aus einem Objekt. Die Liste besteht aber nicht aus einer Anzahl Kopien des Elements (mit clone()), sondern aus einer Liste, die ein Element immer wiederholt. Daher sind auch nur Leseoperationen wie get() oder contains() erlaubt, doch keine Veränderungen. Infolgedessen ist der Einsatzbereich der Liste beschränkt, jener der Funktion aber nicht. Denn die Elemente der Liste können als Ausgang für eine modifizierbare Datenstruktur gelten, der sich eine Liste übergeben lässt. Das gilt zum Beispiel für eine ArrayList, die im Konstruktor eine andere Liste akzeptiert, der sie die Werte entnimmt.
Beispiel Initialisiere eine Liste mit 10 Leer-Strings und hänge an eine Liste 2 Zeichenketten mit ».« an.
List<String> list = new ArrayList<String>( Collections.nCopies (10, "") );
list.addAll( Collections.nCopies (2, ".") );
System.out.println( list ); // [, , , , , , , , , , ., .]
|
11.9.8 Singletons
 
Singletons sind Objekte, die genau ein Exemplar realisieren. singleton(T o) liefert ein Set<T> mit genau einem Element. Auf den ersten Blick erscheint die Funktion ziemlich unnütz, doch sie löst sehr elegant ein Problem, für das die Collection-Klassen keine Lösung zeigen: Löschen aller Vorkommen eines Elements. Zwar gibt es die Collection-Funktion remove(Object), doch das löscht nur das erste Vorkommen. Um alle Vorkommen zu löschen, ist entweder eine Schleife zu schreiben oder singleton() zu nutzen. Uns hilft beim Löschen aller Elemente die Funktion removeAll(Collection), doch erwartet sie als Argument eine Collection, die wir ja gerade durch singleton() bekommen, da ein Set eine Erweiterung von Collection ist!
Beispiel Eine Funktion removeAll(Collection c, Object o), die jedes Vorkommen eines Objektes aus der Datenstruktur entfernt.
void removeAll( Collection<?> c, Object o )
{
c.removeAll( Collections.singleton(o) );
}
|
Neben der einfachen Methode singleton(T o) gibt es noch singletonList(T o), die eine List<T> liefert, und singletonMap(K key, V value) für eine Map<K,V>.
1 Die STL-Bibliothek bei C(++) unterstützt stabile und nicht stabile Sortieralgorithmen. Davon können wir in Java nur träumen.
|