CODEWITHSUNDEEP
listscaladictionarytolist
Pinxaton
Pinxaton

Reputation: 457

Lists and map orderings

In Scala, if we have List[(Char, Int)] ordered by the first element of each pair, does converting to a map via toMap preserve the ordering?

If so, does converting the resulting map back to list via toList preserve ordering?

Upvotes: 1

Views: 1755

Answers (2)

elm
elm

Reputation: 20435

As aforementioned, Map and Set have no ordering. Yet consider TreeMap which preserves ordering over its keys; for instance

val a = List(('z', 1), ('a', 4), ('b', 4))
a: List[(Char, Int)] = List((z,1), (a,4), (b,4))

val b = collection.immutable.TreeMap(a:_*)
b: scala.collection.immutable.TreeMap[Char,Int] = Map(a -> 4, b -> 4, z -> 1)

Update

Note that

for ( (k,v) <- b ) yield k
res: scala.collection.immutable.Iterable[Char] = List(a, b, z)

Upvotes: 1

Kulu Limpa
Kulu Limpa

Reputation: 3541

No, Map (and Set) are not ordered. You can check this using Scala's interactive interpreter (REPL): 

scala> val elems = List('a'->1, 'b'->2, 'c'->3, 'd'->4, 'e'->5)
elems: List[(Char, Int)] = List((a,1), (b,2), (c,3), (d,4), (e,5))

scala> elems.toMap.toList
res8: List[(Char, Int)] = List((e,5), (a,1), (b,2), (c,3), (d,4))

However, scala.collection does provide a SortedMap, which might be what you are looking for, though I haven't used this implementation yet.

Edit: Actually, there's an even more fundamental problem with this conversion: Because you cannot have duplicate keys in a map, you are not just losing guarantees on the ordering, but also, your list may have less elements after the conversion. Consider this: 

scala> val elems = List('a'->1, 'a'->2)
elems: List[(Char, Int)] = List((a,1), (a,2))

scala> elems.toMap.toList
res9: List[(Char, Int)] = List((a,2))

Upvotes: 5

Related Questions