Java：SortedSet“光标”式迭代器
我需要在排序集中向前和向后迭代。如果我使用 NavigableSet，我得到一个严格前向迭代器和一个严格后向迭代器（iterator() 和 descendingIterator()），但没有一个可以向前和向后移动。
NavigableSet.lower() 和 higher() 的时间复杂度是多少？我可以使用它们，但如果它们效率低下，我就不愿意这样做。
I need to iterate both forwards and backwards in a sorted set. If I use NavigableSet, I get a strictly-forward iterator and a strictly-backward iterator (iterator() and descendingIterator()) but none that can move forward and backward.
What's the time complexity of NavigableSet.lower() and higher() ? I can use those instead, but am reluctant to do so if they are inefficient.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
根据您的具体需求，您可以将排序集转换为列表（例如数组列表），并使用 列表迭代器用于遍历。它可以通过 next() 和 previous() 方法，可以自由混合。
Depending on your exact needs you could convert the sorted set to a list, say an array list, and use a list iterator for traversal. It can be used in both directions via the next() and previous() methods, which may be mixed freely.
NavigableSet 只有两种实现。假设您选择了 TreeSet，虽然我没有方便的源代码，但 Javadoc 说它基于 TreeMap 为 get/put/containsKey/remove 提供 O(log(n))。在最坏的情况下，这将执行一次 get 来查找我们正在查找的较低/较高值，再加上额外的搜索来获取下一个/上一个值，提供 O(2log(n)) = O(log(n)) 。
如果树实际上是一个列表，则搜索的最坏情况是 O(n)，但一般来说，O(高度)。
There are only two implementations of the NavigableSet. Saying you opted for the TreeSet, while I don't have the source handy, the Javadoc says that it is based on a TreeMap providing O(log(n)) for get/put/containsKey/remove. At worst this would perform one get to find the value of we're finding the lower/higher for, plus an additional search to get the next/previous value, providing O(2log(n)) = O(log(n)).
Trees are worst case O(n) for search in the event it is actually a list, but in general, O(height).