14

有没有办法在 O(1) 时间内将可变 Map 转换（包装）为不可变（也就是说，不是通过复制值，而是类似于在 JavaConversions 中所做的）

4

6 回答 6

6

正如 Thomas 所指出的，只读视图是 O(1)。但只读并不等同于不变性。

“ Fighting Bit Rot ”论文中很好地描述了差异：

所有集合类都保存在包 scala.collection 中。这个包有三个子包：mutable、immutable 和 generic。大多数集合以三种形式存在，具体取决于它们的可变性。

scala.collection.immutable 包中的集合保证对每个人都是不可变的。这意味着人们可以依赖这样一个事实，即随着时间的推移访问相同的集合值将始终产生具有相同元素的集合。已知包 scala.collection.mutable 中的集合具有一些更改集合的操作。

scala.collection 包中的集合可以是可变的或不可变的。例如，collection.Seq[T] 是 collection.immutable.Seq[T] 和 collection.mutable.Seq[T] 的超类。通常，包 scala 中的根集合。collection 定义了与不可变集合相同的接口，并且包 scala.collection.mutable 中的可变集合通常会在这个不可变接口中添加一些破坏性的修改操作。根集合和不可变集合之间的区别在于，不可变集合的用户可以保证没有人可以改变集合，而根集合的用户必须承担其他人的修改，即使他们自己不能进行任何修改。

也许这只是一个简单的向上转换。

scala> val mm = collection.mutable.Map(1 -> 2)
mm: scala.collection.mutable.Map[Int,Int] = Map(1 -> 2)

scala> val readOnly = mm : collection.Map[Int, Int]
readOnly: scala.collection.Map[Int,Int] = Map(1 -> 2)
于 2010-03-17T09:35:30.213 回答
5

可变地图有一个只读投影。

scala> collection.mutable.Map(1->2).readOnly
res0: scala.collection.Map[Int,Int] = ro-Map(1 -> 2)

正如oxbow_lakes 指出的那样，底层 Map 仍然是可变的，并且在将只读投影发布给客户端后可能会发生变化。在管理地图的代码中必须解决不变性的错觉。

于 2010-03-17T08:32:55.653 回答
3

你所要求的本质上是不安全的。您可以将其mutable.Map作为collection.Map不可变的传递，但使用此表单的“客户”不能确定他们的视图不会从他们下面改变。

于 2010-03-17T09:31:34.990 回答
3

原则上可以将“冻结”方法添加到可变数据结构中，以防止进一步的突变。这是进行包装的唯一甚至稍微安全的方法。（只有一点点，因为在那之后，当你试图改变它时，你必须抛出异常。）然而，Scala 的可变集合没有这种能力。update可以通过覆盖所有变异方法（ 、、、+=等）将其添加到例如 mutable.HashMap 中++=，但这将是一项相当大的工作。

于 2010-03-17T10:04:53.000 回答
2

Philipp Haller 在Capabilities for Uniqueness and Borrowing方面的工作与此有关。在通过类型系统强制执行“所有权”领域还有很多其他工作，但 Philipp 实际上为 Scala 编译器提供了一个可用的插件。

于 2010-03-18T13:28:42.130 回答
0

应该这样做，类似于ArraySeq.unsafeWrapArray.


class UnsafeWrappedMap[K, V](underlying: mutable.Map[K, V]) extends Map[K, V] with StrictOptimizedMapOps[K, V, Map, Map[K, V]] {
  def removed(key: K) = underlying.iterator.filter(_._1 != key).toMap

  def updated[V1 >: V](key: K, value: V1) = {
    underlying.iterator.map {
      case (`key`, _) => (key, value)
      case kv => kv
    }.toMap
  }

  def get(key: K) = underlying.get(key)

  def iterator = underlying.iterator
}

object UnsafeWrappedMap {
  def apply[K, V](underlying: mutable.Map[K, V]) = new UnsafeWrappedMap(underlying)
}

显然，在创建这个之后你不能触摸可变映射！

一个更雄心勃勃的解决方案可能是创建一个映射，一旦创建副本，就会设置一个内部标志，并且任何未来的突变都会导致可变实例在执行突变之前复制其内部状态。

于 2020-03-05T14:56:17.590 回答