问题 Scala：为什么SortedMap的mapValues返回Map而不是SortedMap？

我是Scala的新手。我在用着 为SortedMap 在我的代码中，我想使用 mapValues 创建一个新的地图，对值进行一些转换。

而不是返回一个新的 为SortedMap， mapValues 函数返回一个新的地图，然后我必须转换为 为SortedMap。

例如

val my_map = SortedMap(1 -> "one", 0 -> "zero", 2 -> "two")
val new_map = my_map.mapValues(name => name.toUpperCase)
// returns scala.collection.immutable.Map[Int,java.lang.String] = Map(0 -> ZERO, 1 -> ONE, 2 -> TWO)
val sorted_new_map = SortedMap(new_map.toArray:_ *)

这看起来效率低下 - 最后一次转换可能会再次对键进行排序，或者至少验证它们是否已排序。

我可以使用正常地图对键和值都进行操作的函数，故意不改变转换函数中的键。由于执行起来，这看起来效率也很低地图可能假设转换可能会改变键的顺序（例如： my_map.map(tup => (-tup._1, tup._2)） - 所以它也可能“重新排序”它们。

是否有人熟悉内部实现地图和 为SortedMap，并告诉我，我的假设是否正确？编译器能否自动识别出密钥尚未重新排序？是否存在内部原因 mapValues 不应该退货 为SortedMap？有没有更好的方法来转换地图的值而不会失去键的顺序？

谢谢

9906

2017-09-26 21:00

起源

答案:

你偶然发现了Scala的一个棘手的功能 Map 实现。你缺少的是那个 mapValues 实际上并没有返回新的 Map：它返回一个 view 一个 Map。换句话说，它以这样的方式包装原始地图，即每当您访问它将计算的值时 .toUpperCase 在将值返回给您之前。

这种行为的好处是Scala不会为未访问的值计算函数，也不会花时间将所有数据复制到新的 Map。缺点是重新计算函数每次访问该值。所以你最终可能会这样做额外如果多次访问相同的值，则进行计算。

那么为什么呢 SortedMap 不归路了 SortedMap？因为它实际上正在返回 Map-wrapper。潜在的 Map，然后一个被包裹，仍然是 SortedMap，所以如果你要迭代，它仍然是按排序顺序。你和我都知道，但是类型检查器没有。看起来他们本可以用这样的方式写它，它仍然保持着 SortedMap 特质，但他们没有。

您可以在代码中看到它没有返回 SortedMap，但迭代行为仍将被排序：

// from MapLike
override def mapValues[C](f: B => C): Map[A, C] = new DefaultMap[A, C] {
  def iterator = for ((k, v) <- self.iterator) yield (k, f(v))
  ...

解决问题的方法与解决视图问题的解决方案相同：使用 .map{ case (k,v) => (k,f(v)) }，正如你在问题中提到的那样。

如果你真的想要这种便利方法，你可以做我做的事情，写下你自己的，更好的版本 mapValues：

class EnrichedWithMapVals[T, U, Repr <: GenTraversable[(T, U)]](self: GenTraversableLike[(T, U), Repr]) {
  /**
   * In a collection of pairs, map a function over the second item of each
   * pair.  Ensures that the map is computed at call-time, and not returned
   * as a view as 'Map.mapValues' would do.
   *
   * @param f   function to map over the second item of each pair
   * @return a collection of pairs
   */
  def mapVals[R, That](f: U => R)(implicit bf: CanBuildFrom[Repr, (T, R), That]) = {
    val b = bf(self.asInstanceOf[Repr])
    b.sizeHint(self.size)
    for ((k, v) <- self) b += k -> f(v)
    b.result
  }
}
implicit def enrichWithMapVals[T, U, Repr <: GenTraversable[(T, U)]](self: GenTraversableLike[(T, U), Repr]): EnrichedWithMapVals[T, U, Repr] =
  new EnrichedWithMapVals(self)

现在你打电话的时候 mapVals 在...上 SortedMap 你得到一个非观点 SortedMap：

scala> val m3 = m1.mapVals(_ + 1)
m3: SortedMap[String,Int] = Map(aardvark -> 2, cow -> 6, dog -> 10)

它实际上适用于任何对的集合，而不仅仅是 Map 实现：

scala> List(('a,1),('b,2),('c,3)).mapVals(_+1)
res8: List[(Symbol, Int)] = List(('a,2), ('b,3), ('c,4))

2017-09-26 21:08

这很酷 - 谢谢。我认为如果标准库做了这件事，它仍然会很好，因为（正如Oren建议的那样）它可能会相当高效。例如，基于树的映射可以只是从叶子向根复制树结构，在它去的时候替换值，而不是实际插入，对吧？ - AmigoNico

答案: