scala - SortedMap 中最近的键

Question

给定一个 key k在 SortedMap 中，如何有效地找到最大的键 m小于或等于 k ，也是最小的键 n大于或等于 k .谢谢你。

Answer 1

查看 2.9.0 的源代码，下面的代码似乎是你能做的最好的

def getLessOrEqual[A,B](sm: SortedMap[A,B], bound: A): B = {
  val key = sm.to(x).lastKey
  sm(key)
}

我不确切知道 RedBlack 树的 split 是如何工作的，但我想这有点像树的 O(log n) 遍历/新元素的构造，然后是平衡，也可能是 O(log n)。然后您需要再次沿着新树向下走以获取最后一个 key 。不幸的是，您无法同时检索该值。所以你必须再次向下取值。
另外 lastKey可能会抛出异常，并且没有类似的方法返回 Option .
我在等待更正。
编辑和个人评论
std lib 的 SortedMap 区域似乎有点被忽视了。我还缺少一个可变的 SortedMap。通过查看来源，我注意到缺少一些重要的方法(例如 OP 要求的方法或我的答案中指出的方法)，并且有些方法的实现不好，例如由 TraversableLike 定义的“last”通过完整的树从头到尾得到最后一个元素。
编辑 2
现在问题被重新表述，我的答案不再有效(无论如何之前都不是)。我认为你必须为lessOrEqual 和greaterOrEqual 做我描述的事情两次。好吧，如果您找到相等的元素，则可以走捷径。