Każda implementacja uporządkowanego zestawu w Javie?

Jeśli ktoś jest zaznajomiony z Objective-C, istnieje kolekcja o nazwie, NSOrderedSetktóra działa jako Set, a jej elementy mogą być dostępne jako elementy Array .

Czy jest coś takiego w Javie?

Słyszałem, że jest taka kolekcja LinkedHashMap, ale nie znalazłem nic podobnego do zestawu.

Spójrz na klasę LinkedHashSet

Z dokumentu Java :

Implementacja tabeli skrótów i połączonych list interfejsu Set z przewidywalną kolejnością iteracji . Ta implementacja różni się od HashSet tym, że utrzymuje podwójnie połączoną listę obejmującą wszystkie jej wpisy. Ta połączona lista definiuje kolejność iteracji, czyli kolejność, w jakiej elementy zostały wstawione do zestawu (kolejność wstawiania) . Pamiętaj, że ponowne wstawienie elementu do zestawu nie ma wpływu na kolejność wstawiania . (Element e jest ponownie wstawiany do zbioru s, jeśli s.add (e) zostanie wywołane, gdy s.contains (e) zwróci wartość true bezpośrednio przed wywołaniem).

Każdy zestaw ma iterator (). Iterator normalnego zestawu HashSet jest dość losowy, TreeSet robi to według kolejności sortowania, a iterator LinkedHashSet wykonuje iterację według kolejności wstawiania.

Nie możesz jednak zamienić elementu w LinkedHashSet. Możesz usunąć jeden i dodać kolejny, ale nowy element nie będzie w miejscu oryginału. W LinkedHashMap możesz zastąpić wartość istniejącego klucza, a wtedy wartości nadal będą w oryginalnej kolejności.

Nie możesz też wstawić w określonej pozycji.

Może lepiej użyć ArrayList z jawnym sprawdzeniem, aby uniknąć wstawiania duplikatów.

Zapoznaj się z dokumentacją dotyczącą standardowego interfejsu API języka Java . Tuż obok LinkedHashMapznajduje się plik LinkedHashSet. Pamiętaj jednak, że kolejność w nich jest kolejnością wstawiania, a nie naturalną kolejnością elementów. I możesz tylko iterować w tej kolejności, a nie wykonywać dostępu losowego (z wyjątkiem liczenia kroków iteracji).

Istnieje również interfejs SortedSetzaimplementowany przez TreeSeti ConcurrentSkipListSet. Oba pozwalają na iterację w naturalnej kolejności ich elementów lub Comparator, ale nie losowy dostęp lub kolejność wstawiania.

W przypadku struktury danych, która ma zarówno wydajny dostęp według indeksu, jak i może efektywnie zaimplementować ustawione kryterium, potrzebna byłaby lista pomijania , ale nie ma implementacji z tą funkcją w Java Standard API, chociaż jestem pewien, że łatwo ją znaleźć w Internecie.

Spróbuj użyć java.util.TreeSettego narzędzia SortedSet.

Cytując dokument:

„Elementy są porządkowane przy użyciu ich naturalnego porządku lub przez komparator dostarczony w określonym czasie tworzenia, w zależności od używanego konstruktora”

Należy pamiętać, że dodawanie, usuwanie i zawiera ma dziennik kosztów czasu (n).

Jeśli chcesz uzyskać dostęp do zawartości zestawu jako tablicy, możesz ją przekonwertować, wykonując:

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

Ta tablica zostanie posortowana według tych samych kryteriów co zestaw TreeSet (naturalne lub przez komparator), aw wielu przypadkach będzie to miało przewagę zamiast wykonywania Arrays.sort ()

TreeSet zostało zamówione.

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

zestaw drzew jest uporządkowanym zestawem, ale nie możesz uzyskać dostępu przez indeks elementów, po prostu wykonaj iterację lub przejdź do początku / końca.

Jeśli mówimy o niedrogim wykonaniu skip-list, to zastanawiam się w kontekście dużego O, jaki jest koszt tej operacji:

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

Mam na myśli to, że zawsze utknie w tworzeniu całej tablicy, więc jest O (n):

java.util.Arrays#copyOf

IndexedTreeSet z projektu mapy indeksowanego drzewa zapewnia tę funkcjonalność (uporządkowany / posortowany zestaw z dostępem podobnym do listy według indeksu).

Możesz także uzyskać narzędzie z mapy dwukierunkowej, takiej jak BiMapz Google Guava

Za pomocą a BiMapmożna całkiem efektywnie odwzorować liczbę całkowitą (dla losowego dostępu do indeksu) na dowolny inny typ obiektu. BiMaps są jeden do jednego, więc z każdą podaną liczbą całkowitą jest powiązany co najwyżej jeden element, a każdy element ma przypisaną jedną liczbę całkowitą. Jest sprytnie podparty dwoma HashTableinstancjami, więc zużywa prawie dwukrotnie więcej pamięci, ale jest o wiele bardziej wydajny niż niestandardowe, Listjeśli chodzi o przetwarzanie, ponieważ contains()(wywoływane, gdy element jest dodawany w celu sprawdzenia, czy już istnieje) jest czasem stałym i operacje przyjazne dla równoległości, takie jak HashSet's, podczas gdy Listimplementacja jest DUŻO wolniejsza.

Miałem podobny problem. Nie potrzebowałem zamówionego zestawu, ale raczej listy z szybkim indexOf/ contains. Ponieważ nic tam nie znalazłem, sam sobie wdrożyłem. Oto kod, implementuje oba Seti Listchociaż nie wszystkie operacje na listach zbiorczych są tak szybkie jak ArrayListwersje.

zastrzeżenie: nie testowano

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's 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's an exception the indexMap will be inconsistent
            reindex();
            throw ex;
        }

    }

    @Override
    public void sort(Comparator<? super E> c) {
        try { super.sort(c); }
        finally { reindex(); }
    }
}