Thanks, I'd like to use your solution. 

PS: The performances of these two implementations are nearly the same. 
Benchmarks code:
```scala
  def timeTreemap(reps: Int) = repeat(reps) {
    val m = TreeMap(arr: _*)
    m.size
  }

  def timeTreemapEmpty(reps: Int) = repeat(reps) {
    val m = TreeMap.empty[String, ValueHolder] ++ arr
    m.size
  }
```
result: 
length         benchmark           ns
    10              Treemap         661
    10    TreemapEmpty         748
   100             Treemap     12727
   100   TreemapEmpty     13433
  1000            Treemap   234291
  1000  TreemapEmpty   236387
 10000           Treemap 3102890
 10000 TreemapEmpty 2991450