Existe uma implementação de lista não-duplicado lá fora?

Question

Eu sei sobre SortedSet , mas no meu caso eu preciso de algo que implementa List, e não Set. Então, há uma implementação lá fora, na API ou em outro lugar?

Não deve ser difícil de implementar a mim mesmo, mas eu percebi por que não pedir às pessoas aqui primeiro?

Answer 1

Não há coleta de Java na biblioteca padrão para fazer isso. LinkedHashSet<E> conservas encomendar semelhante a um List, embora , por isso, se você quebrar o seu conjunto em um List quando você quiser usá-lo como um List você terá a semântica que você deseja.

Como alternativa, o Commons Collections (ou commons-collections4, para a versão genérica) tem um List que faz o que você já quer: SetUniqueList / SetUniqueList<E> .

Answer 2

Aqui está o que eu fiz e ele funciona.

Supondo que eu tenho um ArrayList ao trabalho com a primeira coisa que fiz foi criado um novo LinkedHashMap.

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

Então eu tentar adicionar o meu novo elemento ao LinkedHashSet. O método add não altera a LinkedHasSet e retorna false se o novo elemento é uma duplicata. Então isso se torna uma condição que eu possa testar antes de adicionar à ArrayList.

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

Esta é uma maneira simples e elegante para evitar duplicações de ser adicionado a uma lista de matriz. Se você quiser, pode encapsular-lo e substituir o método add em uma classe que estende a ArrayList. Basta lembrar que lidar com addAll por looping através dos elementos e chamar o método add.

Answer 3

Então aqui está o que eu fiz eventualmente. Espero que isso ajude alguém.

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

Você deve considerar seriamente a resposta de dhiller:

1. Em vez de se preocupar com a adição de seus objetos para uma duplicata menos List, adicioná-los a um Set (qualquer implementação), que vai pelo filtro natureza as duplicatas.
2. Quando você precisa chamar o método que requer uma lista, envolvê-la em um new ArrayList(set) (ou um new LinkedList(set), qualquer que seja).

Eu acho que a solução que você postou com o NoDuplicatesList tem alguns problemas, principalmente com o método contains(), além de sua classe não manipula a verificação de duplicatas na coleção passada para o seu método addAll().

Answer 5

Por que não encapsular um conjunto com uma lista, classificar como:

new ArrayList( new LinkedHashSet() )

Isso deixa o outro de implementação para alguém que é um verdadeiro mestre de coleções; -)

Answer 6

Eu precisava de algo assim, então eu fui para as coleções commons e usou o SetUniqueList, mas quando eu corri alguns testes de desempenho, eu achei que ele não parece otimizada em comparação com o caso, se eu quiser usar um conjunto e obter um matriz usando o método Set.toArray (), o SetUniqueTest levou 20: 1 tempo para preencher e depois transversal 100.000 Cordas comparando ao outro implementaion, que é uma grande diferença negócio, então se você se preocupar com o desempenho, eu recomendo que você use Definir e obter uma matriz em vez de usar o SetUniqueList, a menos que você realmente precisa a lógica do SetUniqueList, então você precisa verificar outras soluções ...

O principal método código de teste:

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

}

Saudações Mohammed Sleem http://abusleem.net/blog

Answer 7

NOTA:. Não é preciso subList implementação em conta

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

O documentação para interfaces de coleta diz:

Set -. Uma coleção que não pode conter elementos duplicados
Lista - uma coleção ordenada (às vezes chamado de uma seqüência). As listas podem conter elementos duplicados.

Então, se você não quer duplicatas, você provavelmente não deveria usar uma lista.

Answer 9

no método add, por que não usar HashSet.add() para verificar duplicatas em vez de HashSet.consist(). HashSet.add() voltará true se nenhum duplicado e false contrário.

Answer 10

Em cima da minha cabeça, listas permite duplicatas. Você pode rapidamente implementar um UniqueArrayList e substituir todas as funções do add / insert para verificar se há contains() antes de chamar os métodos herdados. Para uso pessoal, você só poderia implementar o método add que você usa, e substituir os outros para lançar uma exceção no caso programadores futuros tentar usar a lista de uma maneira diferente.

Answer 11

Eu apenas fiz o meu próprio UniqueList na minha própria pequena biblioteca como esta:

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;
    }
}

Eu tenho uma classe TestCollections parecida com esta:

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);
    }
}

funciona bem. Tudo que faz é adiciona a um conjunto se não tê-lo já e há um ArrayList que é reembolsável, bem como uma matriz de objeto.