Если кто-то знаком с Objective-C, существует коллекция под названием NSOrderedSet, которая действует как Установить, и ее элементы могут быть доступны как Массив.
В Java есть что-то подобное?
Я слышал, что есть коллекция под названием LinkedHashMap, но я не нашел ничего подобного для набора.
Взгляните на LinkedHashSet класс
Каждый набор имеет итератор(). Обычный итератор HashSet довольно случайный, TreeSet делает это по порядку сортировки, итератор LinkedHashSet выполняет итерацию по порядку вставки.
Однако вы не можете заменить элемент в LinkedHashSet. Вы можете удалить его и добавить другой, но новый элемент не будет вместо оригинала. В LinkedHashMap вы можете заменить значение для существующего ключа, а затем значения будут по-прежнему в исходном порядке.
Кроме того, вы не можете вставить в определенную позицию.
Возможно, вам лучше использовать ArrayList с явной проверкой, чтобы избежать вставки дубликатов.
Взгляните на стандартный Java API API. Рядом с LinkedHashMap есть LinkedHashSet. Но обратите внимание, что порядок в них - порядок вставки, а не естественный порядок элементов. И вы можете выполнять только итерацию в этом порядке, а не делать произвольный доступ (за исключением подсчета шагов итерации).
Существует также интерфейс SortedSet, реализованный TreeSet и ConcurrentSkipListSet. Оба позволяют итерацию в естественном порядке их элементов или Comparator, но не произвольный доступ или порядок вставки.
Для структуры данных, которая имеет как эффективный доступ по индексу, так и может эффективно реализовать установленный критерий, вам понадобится список пропуска, но в Java Standard API нет реализации с этой функциональностью, хотя я уверен, что легко найти ее в Интернете.
TreeSet.
http://docs.oracle.com/javase/6/docs/api/java/util/TreeSet.html
Попробуйте использовать java.util.TreeSet, который реализует SortedSet.
Чтобы процитировать документ:
"Элементы упорядочиваются с использованием их естественного упорядочения или Компаратором, предоставленным в заданное время создания, в зависимости от того, какой конструктор используется"
Обратите внимание, что add, remove и contains имеет журнал затрат времени (n).
Если вы хотите получить доступ к содержимому набора в виде массива, вы можете его преобразовать:
YourType[] array = someSet.toArray(new YourType[yourSet.size()]);
Этот массив будет отсортирован с теми же критериями, что и TreeSet (естественный или компаратор), и во многих случаях это будет иметь преимущество вместо выполнения массива Arrays.sort()
treeset - это упорядоченный набор, но вы не можете получить доступ через индекс элементов, просто переходите или начинайте с начала/конца.
Если мы говорим о недорогой реализации пропущенного списка, интересно, с точки зрения большого О, какова стоимость этой операции:
YourType [] array = someSet.toArray(новый YourType [yourSet.size()]);
Я имею в виду, что он всегда застревает в создании целого массива, поэтому это O (n):
java.util.Arrays#copyOf
IndexedTreeSet из проекта indexed-tree-map предоставляет эту функциональность (упорядоченный/отсортированный набор с доступом к списку по индексу).
Вы также можете получить некоторую полезность из двунаправленной карты, например BiMap из Google Guava
С помощью BiMap вы можете довольно эффективно сопоставить Integer (для случайного доступа к индексу) для любого другого типа объекта. BiMap являются взаимно однозначными, поэтому любое заданное целое имеет, самое большее, один связанный с ним элемент, и любой элемент имеет одно связанное целое число. Он умно подкрепляется двумя экземплярами HashTable, поэтому он использует почти вдвое больше памяти, но он намного эффективнее, чем пользовательский List для обработки, поскольку contains() (который вызывается, когда элемент добавляется для проверки, если он уже существует) - это операция с постоянным временем и параллельностью, такая как HashSet, тогда как реализация List медленнее. LOT медленнее.
У меня была аналогичная проблема. Мне не нужен был упорядоченный набор, но больше список с быстрым indexOf/contains. Поскольку я ничего не обнаружил, я сам реализовал это. Здесь код, он реализует как Set, так и List, хотя не все операции с массовым списком выполняются так же быстро, как версии ArrayList.
отказ от ответственности: не проверен
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Set;
import java.util.Collection;
import java.util.Comparator;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
import static java.util.Objects.requireNonNull;
/**
* An ArrayList that keeps an index of its content so that contains()/indexOf() are fast. Duplicate entries are
* ignored as most other java Set do.
*/
public class IndexedArraySet<E> extends ArrayList<E> implements Set<E> {
public IndexedArraySet() { super(); }
public IndexedArraySet(Iterable<E> c) {
super();
addAll(c);
}
private HashMap<E, Integer> indexMap = new HashMap<>();
private void reindex() {
indexMap.clear();
int idx = 0;
for (E item: this) {
addToIndex(item, idx++);
}
}
private E addToIndex(E e, int idx) {
indexMap.putIfAbsent(requireNonNull(e), idx);
return e;
}
@Override
public boolean add(E e) {
if(indexMap.putIfAbsent(requireNonNull(e), size()) != null) return false;
super.add(e);
return true;
}
@Override
public boolean addAll(Collection<? extends E> c) {
return addAll((Iterable<? extends E>) c);
}
public boolean addAll(Iterable<? extends E> c) {
boolean rv = false;
for (E item: c) {
rv |= add(item);
}
return rv;
}
@Override
public boolean contains(Object e) {
return indexMap.containsKey(e);
}
@Override
public int indexOf(Object e) {
if (e == null) return -1;
Integer i = indexMap.get(e);
return (i == null) ? -1 : i;
}
@Override
public int lastIndexOf(Object e) {
return indexOf(e);
}
@Override @SuppressWarnings("unchecked")
public Object clone() {
IndexedArraySet clone = (IndexedArraySet) super.clone();
clone.indexMap = (HashMap) indexMap.clone();
return clone;
}
@Override
public void add(int idx, E e) {
if(indexMap.putIfAbsent(requireNonNull(e), -1) != null) return;
super.add(idx, e);
reindex();
}
@Override
public boolean remove(Object e) {
boolean rv;
try { rv = super.remove(e); }
finally { reindex(); }
return rv;
}
@Override
public void clear() {
super.clear();
indexMap.clear();
}
@Override
public boolean addAll(int idx, Collection<? extends E> c) {
boolean rv;
try {
for(E item : c) {
// check uniqueness
addToIndex(item, -1);
}
rv = super.addAll(idx, c);
} finally {
reindex();
}
return rv;
}
@Override
public boolean removeAll(Collection<?> c) {
boolean rv;
try { rv = super.removeAll(c); }
finally { reindex(); }
return rv;
}
@Override
public boolean retainAll(Collection<?> c) {
boolean rv;
try { rv = super.retainAll(c); }
finally { reindex(); }
return rv;
}
@Override
public boolean removeIf(Predicate<? super E> filter) {
boolean rv;
try { rv = super.removeIf(filter); }
finally { reindex(); }
return rv;
}
@Override
public void replaceAll(final UnaryOperator<E> operator) {
indexMap.clear();
try {
int duplicates = 0;
for (int i = 0; i < size(); i++) {
E newval = requireNonNull(operator.apply(this.get(i)));
if(indexMap.putIfAbsent(newval, i-duplicates) == null) {
super.set(i-duplicates, newval);
} else {
duplicates++;
}
}
removeRange(size()-duplicates, size());
} catch (Exception ex) {
// If there an exception the indexMap will be inconsistent
reindex();
throw ex;
}
}
@Override
public void sort(Comparator<? super E> c) {
try { super.sort(c); }
finally { reindex(); }
}
}