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

Question

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

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

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

Answer 1

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

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

Затем, чтобы добавить или удалить элемент, вы можете использовать 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);
    }
}