NavigableMap 有 Scala 版本吗？

Question

在 Java 1.6 中， NavigableMap （以及引入了 NavigableSet) 接口，并且TreeMap 已更新以实现新接口。除此之外，NavigableMap 对于提出诸如“集合中的哪个元素最接近 X？”之类的问题非常有用（请参阅 François Sarradin 的这篇优秀博文 提供了示例和讨论）。

我希望在 Scala 2.8 中找到类似的东西TreeMap 实现，但可惜，似乎并非如此（至少，不是很明显）。是否有另一个类似于 Java 的 NavigableMap 的 Scala 类或特征？如果没有，是否有一些简单的 Scala 习惯用法可以实现。 。

我意识到我可以使用 Java 的 TreeMap，但我想留在 Scala 集合框架中（如果只是为了简单起见）

Answer 1

在不可变集合上，具有反向引用使得集合不可能持久化。因此，人们使用拉链来浏览此类结构。 Anti-xml 有一个在处理 XML 时使用拉链的很好的示例。

Answer 2

这里有一个关于这个主题的帖子

看起来SortedMap 也许能够帮助您实现这一目标，但到目前为止我已经测试过，我不确定它是否是 O(log(n)) 搜索应该的方式：

def searchMap(m: SortedMap[Int,_], k: Int) = {
    val left  = m to(k) lastKey
    val right = m from(k) take(2) lastKey

    if (k - left < right - k)
        left
    else
        right
}

基于定义来自和到按照rangeImpl 看起来这可能是 O(log(n))，但基于实际计时，它似乎线性增长n 的所有合理值。

所以我不确定。