Я ищу структуру данных в пакете java.util. Мне нужно, чтобы он отвечал следующим требованиям:
Я ожидал найти индексный список пропусков, но я этого не сделал. У них есть какая-либо структура данных, которая соответствует требованиям, которые я изложил?
Существует не простая структура данных, которая соответствует всем вашим критериям.
Единственное, что я знаю, который выполняет их все, будет индексный список пропусков. Тем не менее, я не знаю никаких доступных Java-реализаций.
В стандартных библиотеках Java такого контейнера нет.
Когда мне нужна структура данных с этими свойствами, я использую реализацию List (обычно ArrayList, но это не имеет значения), и я делаю все вставки с помощью Collections.binarySearch.
Если бы мне пришлось инкапсулировать отсортированный список в качестве повторно используемого класса, я бы реализовал интерфейс List, делегируя все методы в стандартную реализацию List (он может даже передаваться в качестве параметра конструктору). Я бы выполнил каждый метод вставки (add, addAll, set, Iterator remove), выставив исключение (UnsupportedOperationException), чтобы никто не мог сломать свойство "всегда отсортировано". Наконец, я бы предоставил метод insertSorted, который использовал бы Collections.binarySearch для вставки.
Этот вопрос очень похож на
Посмотрите мой ответ на этот вопрос.
В основном это предполагает следующее:
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, но я не вижу, как вы могли бы быстро искать в этом.)
TreeSet предоставляет вам функциональность естественной сортировки при добавлении элементов в список.
Но если вам это не нужно, а Collections.sort() разрешено, вы можете использовать простой ArrayList.
Рассмотрим List в сочетании с Collections.sort().
Идя с тем, что указано в dwb с помощью List<T> и Collections.sort(), вы можете использовать ArrayList<T> как реализующий List<T> (и не синхронизируется как Vector<T>, если, конечно, вы не хотите, чтобы это накладные расходы). Вероятно, это ваш лучший выбор, потому что они (Sun) обычно проводят много исследований в этих областях (от того, что я видел в любом случае). Если вам нужно сортировать что-то другое, кроме "по умолчанию" (т.е. Вы не сортируете список целых чисел и т.д.), Тогда поставьте свой собственный компаратор.
EDIT: Единственное, что не соответствует вашим требованиям, - это быстрая съемка...
Посмотрите PriorityQueue.
Если вам не нужны аналогичные элементы в структуре данных, тогда обычный TreeSet также соответствует вашим требованиям.