Esiste un ordine di inserimento che preserva Set che implementa anche l'Elenco?

Question

Sto cercando di trovare un'implementazione di java.util.List e java.util.Set allo stesso tempo in Java. Voglio che questa classe permetta solo elementi unici (come Set) e conservi il loro ordine (come List). Esiste in JDK 6?

È importante avere List<T>#add(int, T) così posso inserirlo in una posizione specifica.

Answer 1

TreeSet è ordinato per ordine di elementi; LinkedHashSet conserva l'ordine di inserimento. Speriamo che uno di questi sia quello che cercavi.

Hai specificato che si desidera essere in grado di inserire in una arbitraria posizione , ho il sospetto che si dovrà scrivere il proprio - basta creare una classe che contiene un HashSet<T> ed un ArrayList<T>; quando aggiungi un oggetto, controlla se è presente nel set prima di aggiungerlo alla lista.

Answer 2

Vuoi dire come LinkedHashSet? Ciò mantiene l'ordine di entrata, ma non consente duplicati.

IMHO, è un requisito insolito ma è possibile scrivere una lista senza duplicati.

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

    @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(t); 
     return added; 
    } 

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

Answer 3

LinkedHashSet è la risposta.

Ordinamento di iterazione e unicità.

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

Answer 4

Se non vuoi limitarti a JDK 6 è possibile utilizzare Apache common collections biblioteca che offre corrispondenza esatta per il vostro bisogno - ListOrderedSet. E 'come List e Set combinati insieme :)

Answer 5

Non si può implementare List e Set contemporaneamente senza la violazione del contratto. Vedere, per esempio, il Set.hashCode contratto:

Il codice hash di un insieme è definito come la somma dei codici hash degli elementi dell'insieme, in cui il codice hash di un elemento nullo è definita come zero.

D'altra parte qui è il contratto di List.hashCode:

Il codice hash di una lista è definita come il risultato del calcolo seguente:

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

Quindi è impossibile implementare una singola classe che garantisca che entrambi i contratti siano soddisfatti. Lo stesso problema per l'implementazione di equals.

Answer 6

Ho avuto un problema simile, quindi ho scritto il mio. Vedi here. Lo IndexedArraySet estende ArrayList e implementa Set, quindi dovrebbe supportare tutte le operazioni necessarie. Tieni presente che l'inserimento di elementi in posizioni nel mezzo di un ArrayList può essere lento per i grandi elenchi poiché è necessario spostare tutti i seguenti elementi. Il mio IndexedArraySet non lo cambia.

Answer 7

Un'altra opzione (meno il requisito List interfaccia) è ImmutableSet di Guava, che conserva ordine di inserimento. Da their wiki page:

Fatta eccezione per raccolta differenziata, ordine preservata da tempi di costruzione. Ad esempio,

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

sarà iterare suoi elementi nell'ordine "a", "b", "c", "d".