2

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

の順序についての約束はありませんMap。OrderedMapscalasコレクションパッケージがあります。そのパッケージの値は、暗黙のによって順序付けられますOrdering。クイックフィックスとして、マップの順序付けにキーのリストを使用することをお勧めします。

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

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

編集

独自Orderingに実装して、に渡すこともできます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)

暗黙の順序付けはキーに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 に答える
1

ListMap掘り下げてみると、思い通りに動作する不変が存在することがわかりましたが、この表によると、そのパフォーマンスはひどいものです。そこで、線形に実行される削除を除くすべての操作で効果的に実行されるカスタムの不変の実装を作成しました。Map標準とQueue、それ自体が2回使用する標準に裏打ちされているため、もう少しメモリが必要です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 に答える