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

Question

Какая коллекция хранит данные в определенном порядке и может возвращать или устанавливать элементы в соответствии с индексом?Я знаю, что TreeSet реализует SortedSet, следовательно, хранит данные в соответствии с естественным упорядочением или некоторым объектом Comparator, предоставленным программистом.Но я не знаю, как получить или установить элементы в TreeSet, используя индекс.С другой стороны, ArrayList и некоторые другие структуры могут использоваться для извлечения или установки их элементов в соответствии с любым индексом.Но они не хранят элементы в отсортированном порядке.Есть ли способ иметь обе функции?

Answer 1

Вы можете просто использовать ArrayList и отсортировать его, используя Collections.sort.Если вам нужно вставить элементы, вы можете найти точку вставки, используя Collections.binarySearch, что дает вам сложность O (log n) для вставок (в отличие от O (n log n) для пересчета).ArrayList обеспечивает перегрузку add, которая принимает параметр позиции .

Answer 2

Взгляните на карту indexed-tree http://code.google.com/p/indexed-tree-map/ Я улучшил TreeMap для обеспечения доступа и поиска по индексу.Чтобы получить индекс вставки для несуществующего ключа, вы можете попробовать запустить последовательность put-entryIndex-remove.Хотя это может быть не очень эффективно для ваших требований.Моя реализация entryIndex основана на том, чтобы сначала найти запись, а затем вычислить ее индекс.Я посмотрю, можно ли его улучшить для несуществующих ключей.

Невозможно установить элементы по индексу в отсортированном наборе, не нарушив случайно порядок сортировки.Если вы имеете в виду «установка значений карты по индексу ключа», то снова вы можете использовать index-tree-map.Просто найдите ключ по индексу и используйте пут для перезаписи значения.

Answer 3

Заполните элементы в ArrayList и сортируйте их, вызывая Collections.sort ().