有沒有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？

回答

相關問題