Scala:为什么 SortedMap 的 mapValues 返回的是 Map 而不是 SortedMap？

Question

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

而不是返回一个新的 SortedMap ，mapValues 函数返回一个新的 Map，然后我必须将其转换为 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:_ *)

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

我可以使用对键和值都进行操作的法线贴图函数，并且故意不更改转换函数中的键。这看起来也效率低下，因为 Map 的实现可能假设转换可能会改变键的顺序(例如: my_map.map(tup => (-tup._1, tup._2) ) - 所以它也可能“重新排序”它们。

有谁熟悉 Map 和 SortedMap 的内部实现吗？ ，并且可以告诉我我的假设是否正确？编译器可以自动识别键没有被重新排序吗？ mapValues 不应返回 SortedMap 是否有内部原因？有没有更好的方法来转换 map 的值而不丢失键的顺序？

谢谢

Answer 1

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

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

那为什么SortedMap不返回 SortedMap ?因为它实际上返回了 Map -包装。标的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))
  ...

您的问题的解决方案与解决 View 问题的解决方案相同:使用 .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你得到一个非 View 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))