10

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

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

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

4

2 回答 2

2

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

于 2011-08-29T19:37:29.273 回答
1

这是有关此主题的线程

似乎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
}

根据rangeImplfrom的定义和to术语，它看起来可能是 O(log(n))，但根据实际计时，它似乎对所有可能的 n 值呈线性增长。

所以我不确定。

于 2011-08-29T01:37:26.630 回答