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?

Liter

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

Babs

Could you please explain why it needs log(n) rather n object creations with immutable tree ? I guess all the nodes will be created once it is modified. – Halla

@Bin, An advantage of immutable data structures is you can make use of "structural sharing" . Since only a part of the tree needs to change and the rest is identical to the original, the part that remains unchanged doesn't need to be recreated and you can just include a reference to the original. – Harelip

Answer 2

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)

Sidero

The Java one is lacking all the higher-order functions, so it isn't that interesting ... – Liter

import collection.JavaConverters._ followed by new java.util.TreeMap[String, Int]().asScala. You'll get SortedMap behavior and higher order functions, but not SortedMap functions. – Nassir

Neither TreeMaps or SortedMaps seem to be supported by JavaConverters? – Jadda

For info, the java TreeMap is "only" java, but it provides some methods (such as floorEntry) that the scala equivalent doesn't have. Very practical in some situations. – Claudianus

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.

Hyperplane

ImmutableMapAdaptor has been deprecated – Hunsinger

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.

Leeuwarden

HashSet in Java is a mutable red-black tree. There is nothing inherently immutable about red-black trees. – Aelber

@Craig no, they aren't inherently, but there are some reasons (I think they're mostly performance based) as to why you would not want to implement a mutable variant. – Leeuwarden

Answer 5

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)

Conversational

And not keep any references to the previous value of mh, ih. This is often a blocker for me. Sometimes, you really do want a shareable mutable structure... – Scoles

@Paul I think what you need here is ImmutableMapAdaptor. – Hyperplane