Java：如何从TreeMap条目中获取迭代器？

Question

在Java中，TreeMap<K,V>使用RB-tree存储条目，允许使用map.entrySet().iterator()进行顺序迭代，同时保证在log(N)时间内插入和查找。

TreeMap还提供了查找给定键的上限和下限的方法：map.floorEntry(k)、map.ceilingEntry()、map.lowerEntry(k)和map.higherEntry()。然而，这些的返回值是一个Map.Entry<K,V>实例，并不直接允许访问相邻的条目。我想访问给定键的假设条目的邻居。

是否有一种方法可以从TreeMap条目获取迭代器或者完成我正在尝试的操作？

由于更习惯于C++的std::map<K,V>类，我在这里感到困惑...

注意：我可以接受使用java.util之外的容器库的解决方案，只要它具有一些合理的时间复杂度保证的排序映射容器。

- Shadocko

Answer 1

你可以将返回的 Map.Entry<K, V> 的键作为参数传递给 tailMap(K fromKey) 或 headMap(K toKey)，并迭代结果。

- Eva

---

这几乎是我要找的；但是，考虑到我想获取给定键前后的两个条目，我将不得不调用两种方法，也就是说需要进行两次查找，这似乎浪费了 CPU 周期。 - Shadocko

好的，抱歉我误解了你的回答，你显然是指 map.tailMap(map.lowerEntry(k).getKey())。那样可以工作，但仍需要进行2次查找。 - Shadocko

另一个解决方案是为您的需求制作TreeMap的自定义迭代器，但这不是一项容易的任务。 - Eva