Why is there no SortedList in Java?

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

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

Есть идеи, почему это так разработано?

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

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

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>.

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

2. Отсортируйте свой список с помощью Collections.sort()

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

Вы можете отсортировать свой список с помощью 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);

Sorting in concurrent environments

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

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

3. Завершите свой список с помощью java.util.PriorityQueue

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

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

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

Предостережение относительно 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, который выполняет сортировку каждый раз, когда вы добавляете новый элемент. Это может занять довольно много времени в зависимости от вашей реализации и бессмысленно, если только вы не хотите выполнять это в качестве упражнения по двум основным причинам:

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


2. Зачем изобретать велосипед? Вместо этого вы должны использовать 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 выдадут UnsupportedOperationExceptions.

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

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

Редактировать:

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

Наборы не содержат этой информации.

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

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

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

• List уже поддерживается упорядоченная коллекция и структура данных на основе индекса, деревья не являются структурами данных на основе индекса.


• Tree по определению не может содержать дубликатов.


• В List у нас могут быть дубликаты, поэтому их нет TreeList(т.е. нет SortedList).


• Список поддерживает элементы в порядке вставки. Поэтому, если мы хотим отсортировать список, мы должны использовать java.util.Collections.sort(). Указанный список сортируется в порядке возрастания в соответствии с естественным порядком расположения его элементов.