SortedMap中最近的键

Question

给定一个键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树的分裂是如何工作的,但是我猜它类似于树的O(log n)遍历/新元素的构造,然后是平衡,也可以是O(log n).然后你需要再次沿着新树下去以获得最后一把钥匙.遗憾的是,您无法在同一个go中检索该值.所以你必须再次下载以获取值.

另外,lastKey可能会抛出一个异常,并且没有返回的类似方法Option.

我在等待更正.

编辑和个人评论

std lib的SortedMap区域似乎有点被忽略了.我也错过了一个可变的SortedMap.通过消息来源,我注意到有一些重要的方法缺失(比如OP要求的那个或者我的答案中指出的那些)还有一些有不好的实现,比如TraversableLike定义的'last'通过完整的树从头到尾获取最后一个元素.

编辑2

现在我的问题已经重新制定了,我的答案已经不再有效了(不管怎么说,之前都没有).我认为你必须为LessOrEqual和greaterOrEqual做两次我要描述的事情.如果你找到相同的元素,你可以采取捷径.