Scala矢量拼接(维持排序顺序)

Question

我需要维护一个排序的序列(可变或不可变 - 我不在乎),动态地将元素插入到它的中间(以保持它的排序)并同样删除它们(因此,通过索引随机访问是至关重要的).

我遇到的最好的事情是使用从2.11开始的Vector和scala.collections.Searching,然后:

var vector: Vector[Ordered]
... 
val ip = vector.search(element)

插入:

vector = (vector.take(ip.insertionPoint) :+ element) ++ vector.drop(ip.insertionPoint)

删除:

vector.patch(from = ip.insertionPoint, patch = Nil, replaced = 1)

对我来说看起来不优雅,我怀疑性能问题.有没有更好的办法？拼接序列对我来说似乎是一个非常基本的操作,但我找不到一个优雅的解决方案.

Answer 1

你应该用SortedSet.默认实现SortedSet是不可变的red-black tree.还有一个可变的实现.

SortedSet[Int]() + 5 + 3 + 4 + 7 + 1
// SortedSet[Int] = TreeSet(1, 3, 4, 5, 7)

Set不包含重复元素.如果您想要计算重复元素,可以将SortedMap[Key, Int]元素用作键并计为值.请参阅此答案以进行MultiSet仿真Map.