Существует ли реализация списка без дублирования?
-
06-07-2019 - |
Вопрос
Я знаю о SortedSet
, но в моем случае мне нужно что - то , что реализует List
, и не Set
.Итак, есть ли какая-то реализация там, в API или где-то еще?
Реализовать это самому не должно быть сложно, но я подумал, почему бы сначала не спросить людей здесь?
Решение
В стандартной библиотеке нет коллекции Java для этого. LinkedHashSet<E>
сохраняет порядок, аналогичный < => Однако, если вы обернете свой набор в List
, когда захотите использовать его как commons-collections4
, вы получите семантику, которую вы хотите.
В качестве альтернативы, Коллекции Commons (или SetUniqueList
, для общей версии ) имеет SetUniqueList<E>
, который делает то, что вы уже хотите: <=> / <=> .
Другие советы
Вот что я сделал, и это работает.
Предполагая, что у меня есть ArrayList
для работы, первым делом я создал новый LinkedHashMap
.
LinkedHashSet<E> hashSet = new LinkedHashSet<E>()
Затем я пытаюсь добавить свой новый элемент в LinkedHashSet
. Метод add не изменяет LinkedHasSet
и возвращает false, если новый элемент является дубликатом. Так что это становится условием, которое я могу проверить перед добавлением в addAll
. Р>
if (hashSet.add(E)) arrayList.add(E);
Это простой и элегантный способ предотвратить добавление дубликатов в список массивов. Если вы хотите, вы можете инкапсулировать его в метод add и переопределить его в классе, который расширяет <=>. Просто не забудьте разобраться с <=>, просматривая элементы и вызывая метод add. Р>
Итак, вот что я сделал в конце концов. Я надеюсь, что это помогает кому-то еще.
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);
}
}
}
Вы должны серьезно рассмотреть ответ Дхиллера:
<Ол>new ArrayList(set)
(или new LinkedList(set)
, как угодно). Я думаю, что у решения, которое вы опубликовали с помощью NoDuplicatesList
, есть некоторые проблемы, в основном с методом contains()
, плюс ваш класс не обрабатывает проверку на наличие дубликатов в коллекции, переданной в ваш метод addAll()
.
Почему бы не инкапсулировать набор со списком, сортируйте как:
new ArrayList( new LinkedHashSet() )
Это оставляет другую реализацию тому, кто является настоящим мастером коллекций; -)
Мне нужно было что-то подобное, поэтому я зашел в коллекции commons и использовал SetUniqueList, но когда я провел некоторый тест производительности, я обнаружил, что он кажется не оптимизированным по сравнению со случаем, когда я хочу использовать Set и получить массив с помощью метода Set.toArray(), SetUniqueTest потребовалось время 20: 1 для заполнения, а затем прохождения 100 000 строк по сравнению с другой реализацией, что является большой разницей, поэтому, если вы беспокоитесь о производительности, я рекомендую вам использовать Set и получить массив вместо использования SetUniqueList , если вам действительно не нужна логика SetUniqueList, тогда вам нужно проверить другие решения...
Основной метод тестирования кода:
public static void main(Строка[] аргументов) {
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
}
С Уважением Мохаммед Слим http://abusleem.net/blog
ПРИМЕЧАНИЕ. Он не учитывает реализацию 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));
}
}
документация для интерфейсов сбора гласит: р>
Set & # 8212; коллекция, которая не может содержать повторяющиеся элементы.
Список & # 8212; упорядоченная коллекция (иногда называемая последовательностью). Списки могут содержать повторяющиеся элементы.
Так что если вы не хотите дубликатов, вам, вероятно, не следует использовать список.
в методе add
, почему бы не использовать HashSet.add()
для проверки дубликатов вместо HashSet.consist()
.
true
вернет false
, если нет дубликатов, и <=> в противном случае.
В верхней части моей головы списки позволяют дублировать. Вы можете быстро реализовать UniqueArrayList
и переопределить все функции add
/ insert
, чтобы проверить наличие contains()
перед вызовом унаследованных методов. Для личного использования вы можете реализовать только метод <=>, который вы используете, и переопределить другие, чтобы вызвать исключение в случае, если будущие программисты попытаются использовать список по-другому.
Я только что создал собственный UniqueList в своей маленькой библиотеке, например:
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;
}
}
У меня есть класс TestCollections, который выглядит следующим образом:
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);
}
}
Работает нормально. Все, что он делает, это добавляет к набору, если у него его еще нет, и есть Arraylist, который можно вернуть, а также массив объектов.