Я ищу структуру данных в пакете java.util. Мне нужно, чтобы он отвечал следующим требованиям:
Я ожидал найти индексируемый список пропуска, но не нашел. Есть ли у них какая-либо структура данных, отвечающая заявленным мною требованиям?
Не существует простой структуры данных, удовлетворяющей всем вашим критериям.
Единственный известный мне способ, который соответствует всем требованиям, — это индексируемый список пропуска. Тем не менее, я не знаю каких-либо доступных реализаций Java.
В стандартных библиотеках Java такого контейнера нет.
Когда мне нужна структура данных с этими свойствами, я использую List реализацию (обычно ArrayList, но это не имеет значения), и я делаю все вставки, используя Collections.binarySearch.
Если бы мне пришлось инкапсулировать отсортированный список в виде повторно используемого класса, я бы реализовал интерфейс List, делегировав все методы «стандартной» реализации List (его даже можно передать в качестве параметра конструктору). Я бы реализовал каждый метод вставки (добавить, добавить все, установить, удалить итератор), создав исключение (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);
}
}
}
Примечание к вашему первому требованию: "Количество элементов не ограничено":
Вы можете ограничить это чем-то вроде "Количество элементов не должно быть меньше 231-1...", поскольку в противном случае вы исключаете все варианты, которые поддерживаются Java-массив. (Вы могли бы обойтись произвольным количеством элементов, используя, например, LinkedList, но я не понимаю, как вы могли бы выполнять быстрый поиск в этом.)
Properties как хороший пример того, что нельзя делать!
- person barjak; 22.11.2010
insertSorted также находится в O (n), хотя, возможно, его можно было бы реализовать за O (log n) с использованием другой структуры данных.
- person aioobe; 22.11.2010
ArrayList. Например, если вы хотите, чтобы SortedList со свойством итератор никогда не терпел неудачу, то ваше решение нельзя будет использовать повторно. Вам придется переделать ту же работу, но на этот раз расширить CopyOnWriteArrayList вместо ArrayList. Если вы используете здесь композицию вместо наследования, то вы можете использовать любой бэкенд реализации, какой захотите (например, во время создания экземпляра). Это ошибка класса Properties: он расширяет почти устаревший класс Hashtable, и этот факт уже нельзя изменить.
- person barjak; 23.11.2010
TreeSet предоставляет вам функциональность естественной сортировки при добавлении элементов в список. Но если вам это не нужно и Collections.sort() разрешено, вы можете использовать простой ArrayList.
Рассмотрим List в сочетании с Collections.sort().
Следуя тому, что указано в dwb с List<T> и Collections.sort(), вы можете использовать ArrayList<T>, так как он реализует List<T> (и не синхронизируется, как Vector<T>, если, конечно, вы не хотите таких накладных расходов). Это, вероятно, ваш лучший выбор, потому что они (Sun) обычно проводят много исследований в этих областях (из того, что я видел во всяком случае). Если вам нужно сортировать по чему-то другому, кроме «по умолчанию» (т.е. вы не сортируете список целых чисел и т. д.), укажите свой собственный компаратор.
РЕДАКТИРОВАТЬ: Единственное, что не соответствует вашим требованиям, это быстрое удаление...
Посмотрите PriorityQueue.
Если вам не нужны подобные элементы в вашей структуре данных, то под ваши требования подойдет и обычный TreeSet.
