scala - ListMap 上的更新方法

Question

我使用 ListMap 因为我需要保持插入顺序不变。初始化之后好像就可以了。但当我打电话更新时，顺序就乱了。 1-这是为什么？ 2-是否有任何其他 MapLike 没有这个问题，如果没有，我应该如何更新 map 而不出现问题？

scala> import scala.collection.immutable.ListMap
import scala.collection.immutable.ListMap

scala> val a = ListMap(0 -> "A", 1 -> "B", 2 ->"C")
a: scala.collection.immutable.ListMap[Int,String] = Map(0 -> A, 1 -> B, 2 -> C)

scala> a.foreach(println)
(0,A)
(1,B)
(2,C)

scala> val b = a.updated(1, "D")
b: scala.collection.immutable.ListMap[Int,String] = Map(0 -> A, 2 -> C, 1 -> D)
scala> b.foreach(println)
(0,A)
(2,C)
(1,D)

Answer 1

我找不到任何具有所需属性的现有不可变集合。但它可以手动制作。

import scala.collection.immutable.{IntMap, Map, MapLike} 

class OrderedMap[K, +V] private[OrderedMap](backing: Map[K, V], val order: IntMap[K], coorder: Map[K, Int], extSize: Int)
  extends Map[K, V] with MapLike[K, V, OrderedMap[K, V]] {
  def +[B1 >: V](kv: (K, B1)): OrderedMap[K, B1] = {
    val (k, v) = kv
    if (backing contains k)
      new OrderedMap(backing + kv, order, coorder, extSize)
    else new OrderedMap(backing + kv, order + (extSize -> k), coorder + (k -> extSize), extSize + 1)
  }
  def get(key: K): Option[V] = backing.get(key)

  def iterator: Iterator[(K, V)] = for (key <- order.valuesIterator) yield (key, backing(key))

  def -(key: K): OrderedMap[K, V] = if (backing contains key) {
    val index = coorder(key)
    new OrderedMap(backing - key, order - index, coorder - key, extSize)
  } else this

  override def empty: OrderedMap[K, V] = OrderedMap.empty[K, V]
}

object OrderedMap {
  def empty[K, V] = new OrderedMap[K, V](Map.empty, IntMap.empty, Map.empty, 0)

  def apply[K, V](assocs: (K, V)*): OrderedMap[K, V] = assocs.foldLeft(empty[K, V])(_ + _)
}

这里order是保留的插入顺序映射(可能有“洞”)。高效处理元素删除所需的 coorder 特殊字段。 extSize 基本上是 order.lastkey + 1 但更简单

现在您可以验证

val a = OrderedMap(0 -> "A", 1 -> "B", 2 -> "C")
a.foreach(println)  
val b = a.updated(1, "D")
b.foreach(println)

打印

(0,A)
(1,B)
(2,C)

和

(0,A)
(1,D)
(2,C)