Why is there no mutable TreeMap in Scala?

Question

Is it lack of time, some technical problem or is there a reason why it should not exist?

Answer 1

It's just a missing case that will presumably eventually be filled in. There is no reason not to do it, and in certain cases it would be considerably faster than the immutable tree (since modifications require log(n) object creations with an immutable tree and only 1 with a mutable tree).

---

Edit: and in fact it was filled in in 2.12.

Mutable TreeMap.

(There is a corresponding Set also.)

Answer 2

There may be performance reasons for a mutable TreeMap, but usually you can use an immutable map in the same way as you would a mutable one. You just have to assign it to a var rather than a val. It would be the same as for HashMap, which has mutable and immutable variants:

val mh = collection.mutable.HashMap[Int, Int]()
var ih = collection.immutable.HashMap[Int, Int]()
mh += (1 -> 2)
ih += (1 -> 2)
mh // scala.collection.mutable.HashMap[Int,Int] = Map(1 -> 2)
ih // scala.collection.immutable.HashMap[Int,Int] = Map(1 -> 2)

Answer 3

I assume that the reason is that having a mutable variant doesn't bring a big benefit. There are some cases mentioned in the other answers when a mutable map could be a bit more efficient, for example when replacing an already existing value: A mutable variant would save creation of new nodes, but the complexity would be still O(log n).

If you want to keep a shared reference to the map, you can use ImmutableMapAdaptor which wraps any immutable map into a mutable structure.

Answer 4

You'll also notice that TreeSet doesn't have a mutable equivalent either. It's because they share the common base class RedBlack, and the underlying data structure that keeps the Trees ordered by elements or keys is a red-black tree. I don't know too much about this data structure, but it's pretty complex (insertion and removal are pretty expensive compared to other Maps), so I assume that had something to do with a mutable variant not being included.

Basically, it's probably because the underlying data structure isn't readily mutable so TreeMap isn't. So, to answer your question, it's a technical problem. It can definitely be done though, there's just not much of a use case for it.

Answer 5

Meanwhile you can use the Java TreeMap, which is exactly what you need.

val m = new java.util.TreeMap[String, Int]()
m.put("aa", 2)
m.put("cc", 3)