Любая реализация упорядоченного набора в Java?

Ответ 1

Взгляните на LinkedHashSet класс

Ответ 2

Каждый набор имеет итератор(). Обычный итератор HashSet довольно случайный, TreeSet делает это по порядку сортировки, итератор LinkedHashSet выполняет итерацию по порядку вставки.

Однако вы не можете заменить элемент в LinkedHashSet. Вы можете удалить его и добавить другой, но новый элемент не будет вместо оригинала. В LinkedHashMap вы можете заменить значение для существующего ключа, а затем значения будут по-прежнему в исходном порядке.

Кроме того, вы не можете вставить в определенную позицию.

Возможно, вам лучше использовать ArrayList с явной проверкой, чтобы избежать вставки дубликатов.

Ответ 3

Взгляните на стандартный Java API API. Рядом с LinkedHashMap есть LinkedHashSet. Но обратите внимание, что порядок в них - порядок вставки, а не естественный порядок элементов. И вы можете выполнять только итерацию в этом порядке, а не делать произвольный доступ (за исключением подсчета шагов итерации).

Существует также интерфейс SortedSet, реализованный TreeSet и ConcurrentSkipListSet. Оба позволяют итерацию в естественном порядке их элементов или Comparator, но не произвольный доступ или порядок вставки.

Для структуры данных, которая имеет как эффективный доступ по индексу, так и может эффективно реализовать установленный критерий, вам понадобится список пропуска, но в Java Standard API нет реализации с этой функциональностью, хотя я уверен, что легко найти ее в Интернете.

Ответ 4

TreeSet.

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

Ответ 5

Попробуйте использовать java.util.TreeSet, который реализует SortedSet.

Чтобы процитировать документ:

"Элементы упорядочиваются с использованием их естественного упорядочения или Компаратором, предоставленным в заданное время создания, в зависимости от того, какой конструктор используется"

Обратите внимание, что add, remove и contains имеет журнал затрат времени (n).

Если вы хотите получить доступ к содержимому набора в виде массива, вы можете его преобразовать:

YourType[] array = someSet.toArray(new YourType[yourSet.size()]); 

Этот массив будет отсортирован с теми же критериями, что и TreeSet (естественный или компаратор), и во многих случаях это будет иметь преимущество вместо выполнения массива Arrays.sort()

Ответ 6

treeset - это упорядоченный набор, но вы не можете получить доступ через индекс элементов, просто переходите или начинайте с начала/конца.

Ответ 7

Если мы говорим о недорогой реализации пропущенного списка, интересно, с точки зрения большого О, какова стоимость этой операции:

YourType [] array = someSet.toArray(новый YourType [yourSet.size()]);

Я имею в виду, что он всегда застревает в создании целого массива, поэтому это O (n):

java.util.Arrays#copyOf

Ответ 8

IndexedTreeSet из проекта indexed-tree-map предоставляет эту функциональность (упорядоченный/отсортированный набор с доступом к списку по индексу).

Ответ 9

Вы также можете получить некоторую полезность из двунаправленной карты, например BiMap из Google Guava

С помощью BiMap вы можете довольно эффективно сопоставить Integer (для случайного доступа к индексу) для любого другого типа объекта. BiMap являются взаимно однозначными, поэтому любое заданное целое имеет, самое большее, один связанный с ним элемент, и любой элемент имеет одно связанное целое число. Он умно подкрепляется двумя экземплярами HashTable, поэтому он использует почти вдвое больше памяти, но он намного эффективнее, чем пользовательский List для обработки, поскольку contains() (который вызывается, когда элемент добавляется для проверки, если он уже существует) - это операция с постоянным временем и параллельностью, такая как HashSet, тогда как реализация List медленнее. LOT медленнее.

Ответ 10

У меня была аналогичная проблема. Мне не нужен был упорядоченный набор, но больше список с быстрым 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(); }
    }
}