맵 멤버의 순서가 추가되고 신뢰성이있는 것처럼 보입니까?

Question

Map()에 대한 표준 호출로 불변의 맵을 만들거나 이와 같이 작성된 기존 맵을 연결하여 모든 테스트에서 해당 멤버를 순회하면 추가 순서대로 제공됩니다. 그것이 꼭 필요한 정렬 방법이지만, 맵 멤버의 순서의 신뢰성에 대한 문서에는 단어가 없습니다.

표준 맵이 추가 순서로 항목을 반환 할 것이라고 기대하는 것이 안전한지, 아니면 다른 구현과 그 경우 어떤 것을 찾아야하는지 궁금합니다.

Answer 1

나는 그것이 안전하다고 생각하지 않는다, 순서는 5 개 요소 (스칼라 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을 시도하십시오.

Answer 2

Map의 주문에 대한 약속은 없습니다. scalas 컬렉션 패키지에는 OrderedMap이 있습니다. 해당 패키지의 값은 내재 된 Ordering에 의해 정렬됩니다. quickfix로 맵의 순서에 키 목록을 사용하는 것이 좋습니다.

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

내 댓글이 방법으로 보일 수 있습니다에 같은 자기 순서 데이터 형식 : I 희망

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

:

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) 
} 

지금 우리는 주문을 변경해야을 이것이 당신이 내 대답을 기대했던 방식입니다.

Answer 3

파기 한 후에 정확히 원하는대로 동작하는 불변의 ListMap이 있다는 것을 알았지 만 this table에 따르면 그 성능은 아주 끔찍합니다. 그래서 선형 적으로 수행하는 제거를 제외한 모든 작업에서 효과적으로 수행해야하는 사용자 지정 불변 구현을 작성했습니다. 그것은 표준 Map과 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) 
    } 
}