Java: SortedSet итератор в стиле курсора

Question

Мне нужно перебирать как вперед, так и назад в отсортированном наборе. Если я использую NavigableSet , я получаю итератор со строгой обратной связью и итератор со строгой обратной связью (iterator() и descendingIterator()), но ни один из них не может двигаться вперед и назад.

Какая временная сложность NavigableSet.lower() и higher()? Я могу использовать их вместо этого, но не хочу этого делать, если они неэффективны.

Answer 1

В зависимости от ваших конкретных потребностей вы можете преобразовать отсортированный набор в список, скажем, список массивов, и использовать итератор списка для обхода. Его можно использовать в обоих направлениях с помощью методов next () и previous () , которые можно смешивать свободно.

Answer 2

Существует только две реализации NavigableSet. Говоря, что вы выбрали TreeSet, хотя у меня нет удобного источника, Javadoc говорит, что он основан на TreeMap, обеспечивающем O (log (n)) для get / put / containsKey / remove . В худшем случае это даст один способ найти значение, которое мы находим ниже / выше, плюс дополнительный поиск, чтобы получить следующее / предыдущее значение, обеспечивая O (2log (n)) = O (log (n)) ,

Деревья - это наихудший случай O (n) для поиска, если это действительно список, но в общем случае O (высота).