2

当我通过标准调用Map()或通过连接以这种方式创建的现有地图来创建不可变地图时，在我的所有测试中，我发现遍历其成员会按添加顺序提供它们。这正是我需要对它们进行排序的方式，但文档中没有关于地图成员排序的可靠性的文字。

所以我想知道期望标准 Map 按添加顺序返回其项目是否安全，或者我应该寻找其他一些实现以及在这种情况下哪些实现。

4

3 回答 3

5

我认为这不安全，从 5 个元素（Scala 2.9.1）开始不保留顺序：

scala> Map(1 -> 1, 2 -> 2, 3 -> 3, 4 -> 4, 5 -> 5)
res9: scala.collection.immutable.Map[Int,Int] = 
  Map(5 -> 5, 1 -> 1, 2 -> 2, 3 -> 3, 4 -> 4)

对于更大的地图，顺序是完全“随机的”，试试Map((1 to 100) zip (1 to 100): _*).

尝试LinkedHashMap排序条目并TreeMap实现排序条目。

于 2012-05-21T07:01:28.200 回答
1

挖掘后，我发现存在一个不可变的行为，它的ListMap行为完全符合我的要求，但根据这张表，它的性能非常糟糕。所以我编写了一个自定义的不可变实现，它应该在除删除之外的所有操作上有效执行，它线性执行。它确实需要更多的内存，因为它由标准Map和 a支持Queue，它本身使用了List两次，但在当前时代这不是问题，对吧。

import collection.immutable.Queue

object OrderedMap {
  def apply[A, B](elems: (A, B)*) =
    new OrderedMap(Map(elems: _*), Queue(elems: _*))
}
class OrderedMap[A, B](
  map: Map[A, B] = Map[A, B](),
  protected val queue: Queue[(A, B)] = Queue()
) extends Map[A, B] {
  def get(key: A) =
    map.get(key)
  def iterator =
    queue.iterator
  def +[B1 >: B](kv: (A, B1)) =
    new OrderedMap(
      map + kv,
      queue enqueue kv
    )
  def -(key: A) =
    new OrderedMap(
      map - key,
      queue filter (_._1 != key)
    )
  override def hashCode() =
    queue.hashCode
  override def equals(that: Any) =
    that match {
      case that: OrderedMap[A, B] =>
        queue.equals(that.queue)
      case _ =>
        super.equals(that)
    }
}
于 2012-05-21T09:03:39.903 回答
1

没有关于订单的承诺Map。有一个OrderedMapin scalas 集合包。该包中的值按隐式排序Ordering。作为快速修复，我建议您使用键列表来排序您的地图。

var keyOrdering = List[Int]()
var unorderedMap = Map[Int, String]()

unorderedMap += (1 -> "one")
keyOrdering :+= 1

编辑

您可以实现自己的Ordering并将其传递给 a SortedMap。

编辑#2

一个简单的例子如下：

scala> import scala.collection.SortedMap
import scala.collection.SortedMap

scala> implicit object IntOrdering extends Ordering[Int]
     | def compare(a: Int, b: Int) = b - a
     | }
defined module IntOrdering

scala> var sm = SortedMap[Int, String]()
sm: scala.collection.SortedMap[Int,String] = Map()

scala> sm += (1 -> "one")

scala> sm += (2 -> "two")

scala> println(sm)
Map(2 -> two, 1 -> one)

隐式 Ordering 应用于键，因此IntOrdering可能应用于SortedMap[Int, Any].

编辑#3

像我的评论中这样的自排序 DataType 可能看起来像这样：

case class DataType[T](t: T, index: Int)
object DataType{
  private var index = -1
  def apply[T](t: T) = { index += 1 ; new DataType[T](t, index)
}

现在我们需要更改排序：

implicit object DataTypeOrdering extends Ordering[DataType[_]] {
  def compare(a: DataType[_], b: DataType[_]) = a.index - b.index
}

我希望这是您期望我回答的方式。

于 2012-05-21T07:14:37.067 回答