Есть ли индексируемый отсортированный список в пакете Java.util?

Я ищу структуру данных в пакете java.util. Мне нужно, чтобы он отвечал следующим требованиям:

  • Число элементов (теоретически) неограничено.
  • Элементы сортируются в порядке возрастания.
  • Вы можете получить n-й элемент (быстрый).
  • Вы можете удалить n-й элемент (быстрый).

Я ожидал найти индексный список пропусков, но я этого не сделал. У них есть какая-либо структура данных, которая соответствует требованиям, которые я изложил?

Ответы

Ответ 1

Существует не простая структура данных, которая соответствует всем вашим критериям.

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

Ответ 2

В стандартных библиотеках Java такого контейнера нет.

Когда мне нужна структура данных с этими свойствами, я использую реализацию List (обычно ArrayList, но это не имеет значения), и я делаю все вставки с помощью Collections.binarySearch.

Если бы мне пришлось инкапсулировать отсортированный список в качестве повторно используемого класса, я бы реализовал интерфейс List, делегируя все методы в стандартную реализацию List (он может даже передаваться в качестве параметра конструктору). Я бы выполнил каждый метод вставки (add, addAll, set, Iterator remove), выставив исключение (UnsupportedOperationException), чтобы никто не мог сломать свойство "всегда отсортировано". Наконец, я бы предоставил метод insertSorted, который использовал бы Collections.binarySearch для вставки.

Ответ 3

Этот вопрос очень похож на

Посмотрите мой ответ на этот вопрос.

В основном это предполагает следующее:

class SortedArrayList<T> extends ArrayList<T> {

    @SuppressWarnings("unchecked")
    public void insertSorted(T value) {
        add(value);
        Comparable<T> cmp = (Comparable<T>) value;
        for (int i = size()-1; i > 0 && cmp.compareTo(get(i-1)) < 0; i--) {
            T tmp = get(i);
            set(i, get(i-1));
            set(i-1, tmp);
        }
    }
}

Заметка о вашем первом требовании: "Число элементов неограничено".

Вы можете ограничить это чем-то вроде "Количество элементов не должно быть привязано менее чем 2 31 -1...", поскольку в противном случае вы исключаете все параметры, которые поддерживаемый массивом Java. (Вы можете уйти с произвольным количеством элементов, используя, например, LinkedList, но я не вижу, как вы могли бы быстро искать в этом.)

Ответ 4

TreeSet предоставляет вам функциональность естественной сортировки при добавлении элементов в список. Но если вам это не нужно, а Collections.sort() разрешено, вы можете использовать простой ArrayList.

Ответ 5

Рассмотрим List в сочетании с Collections.sort().

Ответ 6

Идя с тем, что указано в dwb с помощью List<T> и Collections.sort(), вы можете использовать ArrayList<T> как реализующий List<T> (и не синхронизируется как Vector<T>, если, конечно, вы не хотите, чтобы это накладные расходы). Вероятно, это ваш лучший выбор, потому что они (Sun) обычно проводят много исследований в этих областях (от того, что я видел в любом случае). Если вам нужно сортировать что-то другое, кроме "по умолчанию" (т.е. Вы не сортируете список целых чисел и т.д.), Тогда поставьте свой собственный компаратор.

EDIT: Единственное, что не соответствует вашим требованиям, - это быстрая съемка...

Ответ 7

Посмотрите PriorityQueue.

Если вам не нужны аналогичные элементы в структуре данных, тогда обычный TreeSet также соответствует вашим требованиям.