Esiste un'implementazione dell'elenco non duplicata là fuori?

Question

Conosco SortedSet , ma nel mio caso ho bisogno di qualcosa che implementa List e non Set. Quindi esiste un'implementazione là fuori, nell'API o altrove?

Non dovrebbe essere difficile implementarmi, ma ho pensato perché non chiedere prima alle persone qui?

Answer 1

Non ci sono raccolte Java nella libreria standard per farlo. LinkedHashSet<E> conserva l'ordinamento in modo simile a un < =>, tuttavia, quindi se avvolgi il tuo set in List quando vuoi usarlo come commons-collections4 otterrai la semantica che desideri.

In alternativa, le Collezioni comuni (o SetUniqueList, per la versione generica ) ha un SetUniqueList<E> che fa già quello che vuoi: <=> / <=> .

Answer 2

Ecco cosa ho fatto e funziona.

Supponendo che ho un ArrayList per lavorare con la prima cosa che ho fatto è stato creato un nuovo LinkedHashMap.

LinkedHashSet<E> hashSet = new LinkedHashSet<E>()

Quindi provo ad aggiungere il mio nuovo elemento a LinkedHashSet. Il metodo add non modifica LinkedHasSet e restituisce false se il nuovo elemento è un duplicato. Quindi questa diventa una condizione che posso verificare prima di aggiungere a addAll.

if (hashSet.add(E)) arrayList.add(E);

Questo è un modo semplice ed elegante per impedire che i duplicati vengano aggiunti a un elenco di array. Se lo desideri, puoi incapsularlo e sovrascrivere il metodo add in una classe che estende <=>. Ricorda solo di gestire <=> eseguendo il ciclo tra gli elementi e chiamando il metodo add.

Answer 3

Quindi ecco cosa ho fatto alla fine. Spero che questo aiuti qualcun altro.

class NoDuplicatesList<E> extends LinkedList<E> {
    @Override
    public boolean add(E e) {
        if (this.contains(e)) {
            return false;
        }
        else {
            return super.add(e);
        }
    }

    @Override
    public boolean addAll(Collection<? extends E> collection) {
        Collection<E> copy = new LinkedList<E>(collection);
        copy.removeAll(this);
        return super.addAll(copy);
    }

    @Override
    public boolean addAll(int index, Collection<? extends E> collection) {
        Collection<E> copy = new LinkedList<E>(collection);
        copy.removeAll(this);
        return super.addAll(index, copy);
    }

    @Override
    public void add(int index, E element) {
        if (this.contains(element)) {
            return;
        }
        else {
            super.add(index, element);
        }
    }
}   

Answer 4

Dovresti considerare seriamente la risposta di Dhiller:

1. Invece di preoccuparti di aggiungere i tuoi oggetti a un elenco senza duplicati, aggiungili a un set (qualsiasi implementazione), che filtrerà per natura i duplicati.
2. Quando è necessario chiamare il metodo che richiede un Elenco, racchiuderlo in un new ArrayList(set) (o un new LinkedList(set), qualunque cosa).

Penso che la soluzione che hai pubblicato con NoDuplicatesList abbia alcuni problemi, principalmente con il metodo contains(), inoltre la tua classe non gestisce il controllo dei duplicati nella Raccolta passati al tuo metodo addAll().

Answer 5

Perché non incapsulare un set con un elenco, ordinare come:

new ArrayList( new LinkedHashSet() )

Questo lascia l'altra implementazione per qualcuno che è un vero maestro delle Collezioni ;-)

Answer 6

Avevo bisogno di qualcosa del genere, quindi sono andato alle raccolte comuni e ho usato SetUniqueList, ma quando ho eseguito alcuni test delle prestazioni, ho scoperto che non sembra ottimizzato rispetto al caso se voglio usare un set e ottenere un Array usando il metodo Set.toArray (), SetUniqueTest ha impiegato 20: 1 tempo per riempire e poi attraversare 100.000 stringhe rispetto alle altre implementaion, il che è una grande differenza, quindi se ti preoccupi delle prestazioni, ti consiglio di usare Set e ottieni un array invece di usare SetUniqueList, a meno che tu non abbia davvero bisogno della logica di SetUniqueList, quindi devi controllare altre soluzioni ...

Metodo principale del codice di test:

public static void main (String [] args) {

SetUniqueList pq = SetUniqueList.decorate(new ArrayList());
Set s = new TreeSet();

long t1 = 0L;
long t2 = 0L;
String t;


t1 = System.nanoTime();
for (int i = 0; i < 200000; i++) {
    pq.add("a" + Math.random());
}
while (!pq.isEmpty()) {
    t = (String) pq.remove(0);
}
t1 = System.nanoTime() - t1;

t2 = System.nanoTime();
for (int i = 0; i < 200000; i++) {
    s.add("a" + Math.random());
}

s.clear();
String[] d = (String[]) s.toArray(new String[0]);
s.clear();
for (int i = 0; i < d.length; i++) {
    t = d[i];

}
t2 = System.nanoTime() - t2;

System.out.println((double)t1/1000/1000/1000); //seconds
System.out.println((double)t2/1000/1000/1000); //seconds
System.out.println(((double) t1) / t2);        //comparing results

}

Saluti Mohammed Sleem http://abusleem.net/blog

Answer 7

NOTA: non tiene conto dell'implementazione subList .

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Set;

public class UniqueList<T> extends ArrayList<T> {

    private static final long serialVersionUID = 1L;

    /** Unique elements SET */
    private final Set<T> set=new HashSet();

    /** Used by addAll methods */
    private Collection<T> addUnique(Collection<? extends T> col) {
        Collection<T> unique=new ArrayList();
        for(T e: col){
            if (set.add(e)) unique.add(e);
        }
        return unique;
    }

    @Override
    public boolean add(T e) {
        return set.add(e) ? super.add(e) : false;
    }

    @Override
    public boolean addAll(Collection<? extends T> col) {
        return super.addAll(addUnique(col));
    }

    @Override
    public void add(int index, T e) {
        if (set.add(e)) super.add(index, e);
    }

    @Override
    public boolean addAll(int index, Collection<? extends T> col) {
        return super.addAll(index, addUnique(col));
    }

}

Answer 8

La documentazione per le interfacce di raccolta dice:

  

Imposta & # 8212; una raccolta che non può contenere elementi duplicati.
  Elenco & # 8212; una raccolta ordinata (a volte chiamata sequenza). Gli elenchi possono contenere elementi duplicati.

Quindi, se non vuoi duplicati, probabilmente non dovresti usare un elenco.

Answer 9

nel metodo add, perché non usare HashSet.add() per controllare i duplicati anziché HashSet.consist(). true restituirà false se nessun duplicato e <=> altrimenti.

Answer 10

In cima alla mia testa, gli elenchi consentono duplicati. È possibile implementare rapidamente un UniqueArrayList e sovrascrivere tutte le funzioni add / insert per verificare la presenza di contains() prima di chiamare i metodi ereditati. Per uso personale, puoi implementare solo il metodo <=> che usi e sovrascrivere gli altri per generare un'eccezione nel caso in cui i futuri programmatori provino a utilizzare l'elenco in un modo diverso.

Answer 11

Ho appena creato la mia UniqueList nella mia piccola libreria in questo modo:

package com.bprog.collections;//my own little set of useful utilities and classes

import java.util.HashSet;
import java.util.ArrayList;
import java.util.List;
/**
*
* @author Jonathan
*/
public class UniqueList {

private HashSet masterSet = new HashSet();
private ArrayList growableUniques;
private Object[] returnable;

public UniqueList() {
    growableUniques = new ArrayList();
}

public UniqueList(int size) {
    growableUniques = new ArrayList(size);
}

public void add(Object thing) {
    if (!masterSet.contains(thing)) {
        masterSet.add(thing);
        growableUniques.add(thing);
    }
}

/**
 * Casts to an ArrayList of unique values
 * @return 
 */
public List getList(){
    return growableUniques;
}

public Object get(int index) {
    return growableUniques.get(index);
}

public Object[] toObjectArray() {
    int size = growableUniques.size();
    returnable = new Object[size];
    for (int i = 0; i < size; i++) {
        returnable[i] = growableUniques.get(i);
    }
    return returnable;
    }
}

Ho una classe TestCollections che assomiglia a questa:

package com.bprog.collections;
import com.bprog.out.Out;
/**
*
* @author Jonathan
*/
public class TestCollections {
    public static void main(String[] args){
        UniqueList ul = new UniqueList();
        ul.add("Test");
        ul.add("Test");
        ul.add("Not a copy");
        ul.add("Test"); 
        //should only contain two things
        Object[] content = ul.toObjectArray();
        Out.pl("Array Content",content);
    }
}

Funziona bene. Tutto ciò che fa è aggiungere a un set se non lo ha già e c'è un Arraylist che è restituibile, così come un array di oggetti.