Seq for fast random access and fast growth in Scala

Question

What would be the best Scala collection (in 2.8+), mutable or immutable, for the following scenario:

• Sequentially ordered, so I can access items by position (a Seq)
• Need to insert items frequently, so the collection must be able to grow without too much penalty
• Random access, frequently need to remove and insert items at arbitrary indexes in the collection

Currently I seem to be getting good performance with the mutable ArrayBuffer, but is there anything better? Is there an immutable alternative that would do as well? Thanks in advance.

Answer 1

Mutable: ArrayBuffer
Immutable: Vector

Answer 2

Vector. IndSeq from scalaz should be even better.

Answer 3

If you insert items at random positions more than log(N)/N of the time that you access them, then you should probably use immutable.TreeSet as all operations are O(log(N)). If you mostly do accesses or add to the (far) end, ArrayBuffer and Vector work well.