CODEWITHSUNDEEP
scaladictionary
Nikita Volkov
Nikita Volkov

Reputation: 43330

Is the ordering of members of a map, seeming to be by addition, reliable?

When I create an immutable map with a standard call to Map() or by concatenating the existing maps created that way, in all my tests I get that traversing its members provides them in the order of addition. That's exactly the way I need them to be sorted, but there's not a word in the documentation about the reliability of the ordering of the members of the map.

So I was wondering whether it is safe to expect the standard Map to return its items in the order of addition or I should look for some other implementations and which ones in that case.

Upvotes: 2

Views: 247

Answers (3)

Nikita Volkov
Nikita Volkov

Reputation: 43330

After digging I've found out that there exists an immutable ListMap that behaves exactly as I want it, but according to this table its performance is just awfull. So I wrote a custom immutable implementation that should perform effectively on all operations except removal, where it performs linearly. It does require a bit more memory as it's backed by a standard Map and a Queue, which itself utilizes a List twice, but in the current age it's not an issue, right.

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

Upvotes: 1

tgr
tgr

Reputation: 3608

There is no promise about the order of Map. There is an OrderedMap in scalas collection package. The values in that package are ordered by an implicit Ordering. As quickfix I recommend you to use a list of keys for the ordering of your Map.

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

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

Edit

You could implement your own Ordering and pass it to a SortedMap as well.

Edit #2

A simple example would be the following:

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)

The implicit Ordering is applied to the keys, so IntOrdering might be applied to a SortedMap[Int, Any].

Edit #3

A self ordering DataType like in my comment might look this way:

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

Now we need to change the Ordering:

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

I hope this is the way you expected my answer.

Upvotes: 1

Tomasz Nurkiewicz
Tomasz Nurkiewicz

Reputation: 340913

I don't think it's safe, the order is not preserved starting from 5 elements (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)

With bigger maps the order is completely "random", try Map((1 to 100) zip (1 to 100): _*).

Try LinkedHashMap for ordered entries and TreeMap to achieve sorted entries.

Upvotes: 5

Related Questions