有没有Scala版本的NavigableMap？

在Java 1.6中，引入NavigableMap（和NavigableSet）接口并更新了TreeMap以实现新接口。除其他事项外，NavigableMap的是问这样的“问题有用的集合，其中元素是最接近X？（见this excellent blog post by François Sarradin的示例和讨论）。有没有Scala版本的NavigableMap？

我希望能找到在斯卡拉2.8的TreeMap中实现类似的东西，但唉，它似乎不是这样（至少，它不是很明显）是否有另一个类似于Java的NavigableMap的Scala类或特征？如果不是，是否有一些简单的Scala习惯用法可以使用实现类似的东西？

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

来源

2011-08-29 Jim Hurne

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

来源

2011-08-29 19:37:29

很明显，拉链如何帮助修改（复制）树，但不太清楚拉链将如何用于回答诸如“集合中的哪个元素最接近X？”等问题。我知道我们在这里主要谈论的是理论（因为拉链似乎主要是实验性的），但是你能描述一个拉链如何回答前面提到的问题吗？ –

@Jim拉链根本没有实验性。拉链有两种操作：检查/更新和导航。所以，如果你在X有一个拉链，它的导航操作自然会给你最接近的元素。 –

啊我现在看到了！谢谢。你链接到关于拉链的问题是什么给了我印象拉链是实验性的。很高兴听到他们随时可用。 –

Here's a thread on this topic

看来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 
}

基于对from和to在rangeImpl而言，它看起来像这可能是为O（log（n））的，但基于实际定时它的定义，它似乎对所有合理的线性增长n的值。

所以我不确定。

来源

2011-08-29 01:37:26 Owen

为什么不能，但函数往来和创建两个新的地图，这可能不是所需的。 –

有没有Scala版本的NavigableMap？

回答

相关问题