Почему в Java нет SortedList?

В Java есть интерфейсы SortedSet и SortedMap. Оба относятся к стандартной структуре коллекций Java и предоставляют упорядоченный способ доступа к элементам.

Однако, по моему мнению, в Java нет SortedList. Вы можете использовать java.util.Collections.sort() для сортировки списка.

Любая идея, почему он создан так?

Ответ 1

Итераторы списка гарантируют, в первую очередь, то, что вы получите элементы списка во внутреннем порядке списка (он же порядок вставки). Точнее, в том порядке, в котором вы вставили элементы, или о том, как вы манипулировали списком. Сортировка может рассматриваться как манипулирование структурой данных, и существует несколько способов сортировки списка.

Я закажу пути в порядке полезности, как лично вижу:

1. Попробуйте вместо этого использовать коллекции `Set` или `Bag`

ПРИМЕЧАНИЕ: я поставил эту опцию сверху, потому что это то, что вы обычно хотите делать в любом случае.

Сортированный набор автоматически сортирует коллекцию при вставке, что означает, что он выполняет сортировку при добавлении элементов в коллекцию. Это также означает, что вам не нужно сортировать вручную.

Кроме того, если вы уверены, что вам не нужно беспокоиться о (или иметь) дубликаты элементов, вы можете вместо этого использовать TreeSet<T>. Он реализует SortedSet и NavigableSet интерфейсы и работает, как вы, вероятно, ожидать из списка:

TreeSet<String> set = new TreeSet<String>();
set.add("lol");
set.add("cat");
// automatically sorts natural order when adding

for (String s : set) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

Если вы не хотите естественного упорядочения, вы можете использовать параметр конструктора, который принимает Comparator<T>.

В качестве альтернативы, вы можете использовать Multisets (также известный как Bags), то есть Set который позволяет дублировать элементы, и есть их сторонние реализации. В частности, из библиотек Guava есть TreeMultiset, который очень похож на TreeSet.

2. Сортируйте ваш список с `Collections.sort()`

Как упоминалось выше, сортировка List - это манипулирование структурой данных. Так что для ситуаций, когда вам нужен "один источник правды", который будет отсортирован различными способами, тогда сортировка вручную - это путь.

Вы можете отсортировать свой список с помощью метода java.util.Collections.sort(). Вот пример кода о том, как:

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

Collections.sort(strings);
for (String s : strings) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

Использование компараторов

Одно очевидное преимущество заключается в том, что вы можете использовать Comparator в методе sort. Java также предоставляет некоторые реализации для Comparator такие как Collator который полезен для строк сортировки, чувствительных к локали. Вот один пример:

Collator usCollator = Collator.getInstance(Locale.US);
usCollator.setStrength(Collator.PRIMARY); // ignores casing

Collections.sort(strings, usCollator);

Сортировка в параллельных средах

Учтите, однако, что использование метода sort неудобно в параллельных средах, поскольку экземпляром коллекции будет манипулировать, и вам следует рассмотреть возможность использования неизменяемых коллекций. Это то, что Guava предоставляет в классе Ordering и представляет собой простую однострочную строку:

List<string> sorted = Ordering.natural().sortedCopy(strings);

3. Оберните свой список с помощью `java.util.PriorityQueue`

Хотя в Java нет отсортированного списка, тем не менее есть отсортированная очередь, которая, вероятно, сработает для вас. Это класс java.util.PriorityQueue.

Нико Хааз в комментариях связался с соответствующим вопросом, который также отвечает на этот вопрос.

В отсортированной коллекции вы, скорее всего, не хотите манипулировать внутренней структурой данных, поэтому PriorityQueue не реализует интерфейс List (потому что это даст вам прямой доступ к его элементам).

Предупреждение об итераторе `PriorityQueue`

Класс PriorityQueue реализует интерфейсы Iterable<E> и Collection<E> поэтому его можно повторять как обычно. Однако итератор не гарантирует возвращение элементов в отсортированном порядке. Вместо этого (как указывает Альдерат в комментариях), вам нужно poll() очередь, пока она не опустеет.

Обратите внимание, что вы можете преобразовать список в приоритетную очередь через конструктор, который принимает любую коллекцию:

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

PriorityQueue<String> sortedStrings = new PriorityQueue(strings);
while(!sortedStrings.isEmpty()) {
    System.out.println(sortedStrings.poll());
}
// Prints out "cat" and "lol"

4. Напишите свой собственный класс `SortedList`

ПРИМЕЧАНИЕ. Вам не нужно этого делать.

Вы можете написать свой собственный класс List, который сортирует каждый раз, когда вы добавляете новый элемент. Это может привести к значительным вычислительным нагрузкам в зависимости от вашей реализации и будет бессмысленным, если только вы не захотите сделать это в качестве упражнения по двум основным причинам:

Это нарушает контракт, который имеет интерфейс List<E>, потому что методы add должны гарантировать, что элемент будет находиться в индексе, указанном пользователем.
Зачем изобретать велосипед? Вместо этого вы должны использовать TreeSet или Multisets, как указано в первом пункте выше.

Однако, если вы хотите сделать это в качестве упражнения, вот пример кода для начала работы, он использует абстрактный класс AbstractList:

public class SortedList<E> extends AbstractList<E> {

    private ArrayList<E> internalList = new ArrayList<E>();

    // Note that add(E e) in AbstractList is calling this one
    @Override 
    public void add(int position, E e) {
        internalList.add(e);
        Collections.sort(internalList, null);
    }

    @Override
    public E get(int i) {
        return internalList.get(i);
    }

    @Override
    public int size() {
        return internalList.size();
    }

}

Обратите внимание, что если вы не переопределили нужные вам методы, то реализации по умолчанию из AbstractList будут генерировать UnsupportedOperationException.

Ответ 2

Поскольку концепция списка несовместима с понятием автоматически отсортированной коллекции. Точкой списка является то, что после вызова list.add(7, elem) вызов list.get(7) вернет elem. При автосортированном списке элемент может оказаться в произвольной позиции.

Ответ 3

Поскольку все списки уже "отсортированы" по порядку добавления элементов (упорядочение FIFO), вы можете "прибегнуть" к ним с другим порядком, включая естественный порядок элементов, используя java.util.Collections.sort().

РЕДАКТИРОВАТЬ:

Списки в качестве структур данных основаны на том, что интересно, это порядок, в котором элементы, в которые они были вставлены.

Наборы не имеют такой информации.

Если вы хотите заказать, добавив время, используйте List. Если вы хотите заказать по другим критериям, используйте SortedSet.

Ответ 4

Set и Map являются нелинейной структурой данных. Список представляет собой линейную структуру данных.

Древовидная структура данных SortedSet и SortedMap реализуют TreeSet и TreeMap соответственно, используя алгоритм реализации Red-Black tree. Таким образом, убедитесь, что нет дублированных элементов (или ключей в случае Map).

List уже поддерживает упорядоченную коллекцию и структуру данных на основе индекса, деревья не являются структурами данных на основе индекса.
Tree по определению не может содержать дубликаты.
В List мы можем иметь дубликаты, поэтому TreeList отсутствует (т.е. нет SortedList).
Список поддерживает элементы в порядке вставки. Поэтому, если мы хотим отсортировать список, мы должны использовать java.util.Collections.sort(). Он сортирует указанный список в порядке возрастания в соответствии с естественным порядком его элементов.

Ответ 5

JavaFX `SortedList`

Хотя это заняло некоторое время, Java 8 имеет отсортированный List. http://docs.oracle.com/javase/8/javafx/api/javafx/collections/transformation/SortedList.html

Как вы можете видеть в javadocs, это часть коллекций JavaFX, предназначенная для предоставления отсортированного представления в ObservableList.

Обновление: обратите внимание, что в Java 11 инструментарий JavaFX вышел за пределы JDK и теперь является отдельной библиотекой. JavaFX 11 доступен в виде загружаемого SDK или от MavenCentral. Смотрите https://openjfx.io

Ответ 6

Для любых новичков, начиная с апреля 2015 года, Android теперь имеет класс SortedList в библиотеке поддержки, разработанный специально для работы с RecyclerView. Здесь об этом сообщается сообщение в блоге.

Ответ 7

Другим моментом является временная сложность операций вставки. Для вставки списка ожидаются сложности O (1). Но это не может быть гарантировано с отсортированным списком.

И самое главное, что списки ничего не принимают о своих элементах. Например, вы можете создавать списки вещей, которые не реализуют equals или compare.

Ответ 8

Подумайте об этом так: интерфейс List имеет такие методы, как add(int index, E element), set(int index, E element). Контракт заключается в том, что после добавления элемента в положение X вы найдете его там, если вы не добавите или не удалите элементы перед ним.

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

Ответ 9

Первая строка в API списка говорит, что это упорядоченная коллекция (также известная как последовательность). Если вы отсортируете список, вы не сможете сохранить заказ, поэтому на Java не существует TreeList.
Поскольку API говорит, что Java List получил вдохновение из Sequence и видит свойства последовательности http://en.wikipedia.org/wiki/Sequence_(mathematics)

Это не означает, что вы не можете отсортировать список, но Java строго соответствует его определению и не предоставляет отсортированные версии списков по умолчанию.

Ответ 10

Рассмотрите возможность использования indexed-tree-map. Это расширенный JDK TreeSet, который обеспечивает доступ к элементу по индексу и поиск индекса элемента без итераций или скрытых базовых списков, которые поддерживают дерево. Алгоритм основан на обновлении веса изменяющихся узлов каждый раз, когда происходит изменение.

Ответ 11

В случае, если вы ищете способ сортировки элементов, но также можете эффективно обращаться к ним по индексу, вы можете сделать следующее:

Используйте список произвольного доступа для хранения (например, ArrayList)
Убедитесь, что он всегда отсортирован

Затем, чтобы добавить или удалить элемент, вы можете использовать Collections.binarySearch чтобы получить индекс вставки/удаления. Поскольку в вашем списке реализован произвольный доступ, вы можете эффективно изменить список с помощью определенного индекса.

Пример:

/**
 * @deprecated
 *      Only for demonstration purposes. Implementation is incomplete and does not 
 *      handle invalid arguments.
 */
@Deprecated
public class SortingList<E extends Comparable<E>> {
    private ArrayList<E> delegate;

    public SortingList() {
        delegate = new ArrayList<>();
    }

    public void add(E e) {
        int insertionIndex = Collections.binarySearch(delegate, e);

        // < 0 if element is not in the list, see Collections.binarySearch
        if (insertionIndex < 0) {
            insertionIndex = -(insertionIndex + 1);
        }
        else {
            // Insertion index is index of existing element, to add new element 
            // behind it increase index
            insertionIndex++;
        }

        delegate.add(insertionIndex, e);
    }

    public void remove(E e) {
        int index = Collections.binarySearch(delegate, e);
        delegate.remove(index);
    }

    public E get(int index) {
        return delegate.get(index);
    }
}