Gibt es ein Set zum Beibehalten der Insertionsreihenfolge, das auch List implementiert?

Lesezeit: 3 Minuten

Benutzer-Avatar
jegor256

Ich versuche, eine Implementierung von zu finden java.util.List und java.util.Set gleichzeitig in Java. Ich möchte, dass diese Klasse nur eindeutige Elemente (wie z Set) und ihre Reihenfolge beibehalten (wie List). Existiert es in JDK 6?

Es ist wichtig zu haben List<T>#add(int, T) damit ich an einer bestimmten Position einfügen kann.

  • Meinst du ihre bewahren einfügen Reihenfolge oder eine durch a definierte Reihenfolge Comparator? Wollen Sie auch die Semantik der List auch Schnittstelle?

    Benutzer177800

    18. November 2011 um 16:00 Uhr

Benutzer-Avatar
Jon Skeet

TreeSet ist nach Elementreihenfolge sortiert; LinkedHashSet behält die Insertionsreihenfolge bei. Hoffentlich ist einer davon das, wonach Sie gesucht haben.

Sie haben angegeben, dass Sie an einer einfügen können möchten willkürlich location, ich vermute, Sie müssen Ihre eigene schreiben – erstellen Sie einfach eine Klasse, die a enthält HashSet<T> und ein ArrayList<T>; Überprüfen Sie beim Hinzufügen eines Artikels, ob er im Set enthalten ist, bevor Sie ihn zur Liste hinzufügen.

Alternativ bietet Apache’s commons-collections4 an ListOrderedSet und SetUniqueListdie sich ähnlich verhalten und die gegebenen Anforderungen erfüllen sollten.

LinkedHashSet ist die Antwort.

Iterationsreihenfolge und Eindeutigkeit.

http://download.oracle.com/javase/6/docs/api/java/util/LinkedHashSet.html

  • Es wird nicht implementiert List Schnittstelle, siehe meine Änderungen an der Frage

    – jegor256

    18. November 2011 um 15:59 Uhr

Benutzer-Avatar
Peter Lawrey

Meinst du wie LinkedHashSet? Dadurch wird die Reihenfolge der Eingaben beibehalten, aber keine Duplikate zugelassen.

IMHO, es ist eine ungewöhnliche Anforderung, aber Sie können eine Liste ohne Duplikate schreiben.

class SetList<T> extends ArrayList<T> {
    @Override
    public boolean add(T t) {
        return !super.contains
    }

    @Override
    public void add(int index, T element) {
        if (!super.contains(element)) super.add(index, element);
    }

    @Override
    public boolean addAll(Collection<? extends T> c) {
        boolean added = false;
        for (T t : c)
            added |= add
        return added;
    }

    @Override
    public boolean addAll(int index, Collection<? extends T> c) {
        boolean added = false;
        for (T t : c)
            if (!super.contains
                super.add(index++, t);
                added = true;
            }
        return added;
    }
}

  • Es wird nicht implementiert List Schnittstelle, siehe meine Änderungen an der Frage

    – jegor256

    18. November 2011 um 15:59 Uhr

  • stackoverflow.com/a/8185105/253468 sieht besser aus, weil es keine hat O(n) Einfügungskomplexität, es gibt einen Kompromiss, den man zwischen doppelter Speicherung und berücksichtigen muss O(log(n)) Vorgang einfügen.

    – TWiStErRob

    4. Oktober 2013 um 18:45 Uhr

Sie können nicht implementieren List und Set sofort ohne Vertragsverletzung. Siehe zum Beispiel die Set.hashCode Vertrag:

Der Hash-Code einer Menge ist als die Summe der Hash-Codes der Elemente in der Menge definiert, wobei der Hash-Code eines Null-Elements als Null definiert ist.

Andererseits ist hier der Vertrag von List.hashCode:

Der Hash-Code einer Liste ist als Ergebnis der folgenden Berechnung definiert:

int hashCode = 1;
for (E e : list)
    hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());

Daher ist es unmöglich, eine einzelne Klasse zu implementieren, die die Erfüllung beider Verträge garantiert. Das gleiche Problem für equals Implementierung.

Benutzer-Avatar
Ondrej Bozek

Wenn Sie sich nicht auf JDK 6 beschränken, können Sie es verwenden Allgemeine Apache-Sammlungen Bibliothek, die genau Ihren Anforderungen entspricht – ListOrderedSet. Es ist wie List und Set miteinander kombiniert 🙂

  • abzüglich der List Schnittstelle

    – LateralFractal

    8. Dezember 2015 um 2:31 Uhr

Benutzer-Avatar
kuporisch

Eine weitere Option (abzüglich der List Schnittstellenanforderung) ist Guava’s ImmutableSet, wodurch die Reihenfolge der Einfügungen beibehalten wird. Aus ihre Wiki-Seite:

Außer bei sortierten Sammlungen, Ordnung bleibt aus der Bauzeit erhalten. Zum Beispiel,

ImmutableSet.of("a", "b", "c", "a", "d", "b")

iteriert über seine Elemente in der Reihenfolge “a”, “b”, “c”, “d”.

  • abzüglich der List Schnittstelle

    – LateralFractal

    8. Dezember 2015 um 2:31 Uhr

Benutzer-Avatar
Gemeinschaft

Ich hatte ein ähnliches Problem, also habe ich mein eigenes geschrieben. Siehe hier. Das IndexedArraySet erweitert ArrayList und implementiert Set, daher sollte es alle Vorgänge unterstützen, die Sie benötigen. Beachten Sie, dass das Einfügen von Elementen an Stellen in der Mitte eines ArrayList kann bei großen Listen langsam sein, da alle folgenden Elemente verschoben werden müssen. Mein IndexedArraySet ändert das nicht.

1246790cookie-checkGibt es ein Set zum Beibehalten der Insertionsreihenfolge, das auch List implementiert?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy