Scala:我可以依赖Set中的项目顺序吗？

Question

这是一个非常不可思议的惊喜:

scala> Set(1, 2, 3, 4, 5)       
res18: scala.collection.immutable.Set[Int] = Set(4, 5, 1, 2, 3)
scala> Set(1, 2, 3, 4, 5).toList
res25: List[Int] = List(5, 1, 2, 3, 4)

这个例子本身就表明了我的问题的"不"答案.那怎么样ListSet？

scala> import scala.collection.immutable.ListSet
scala> ListSet(1, 2, 3, 4, 5)
res21: scala.collection.immutable.ListSet[Int] = Set(1, 2, 3, 4, 5)

这个似乎工作,但我应该依靠这种行为？还有哪些其他数据结构适用于必须保留原始订单的唯一项目的不可变集合？

顺便说一下,我确实知道distict方法List.问题是,我想在接口级强制执行项目的唯一性(同时保留顺序),因此使用distinct会弄乱我的整洁设计.

编辑

ListSet 看起来也不太可靠:

scala> ListSet(1, 2, 3, 4, 5).toList
res28: List[Int] = List(5, 4, 3, 2, 1)

EDIT2

在我寻找完美设计时,我试过这个:

scala> class MyList[A](list: List[A]) { val values = list.distinct }
scala> implicit def toMyList[A](l: List[A]) = new MyList(l)
scala> implicit def fromMyList[A](l: MyList[A]) = l.values     

哪个实际有效:

scala> val l1: MyList[Int] = List(1, 2, 3)
scala> l1.values
res0: List[Int] = List(1, 2, 3)

scala> val l2: List[Int] = new MyList(List(1, 2, 3))
l2: List[Int] = List(1, 2, 3)

然而,问题在于我不想MyList在库外暴露.在覆盖时有没有办法进行隐式转换？例如:

trait T { def l: MyList[_] }
object O extends T { val l: MyList[_] = List(1, 2, 3) }
scala> O.l mkString(" ")  // Let's test the implicit conversion
res7: String = 1 2 3      

我想这样做:

object O extends T { val l = List(1, 2, 3) }  // Doesn't work

Answer 1

这取决于你正在使用的套装.如果您不知道您拥有哪个Set实现,那么答案很简单,不,您不能确定.在实践中,我经常遇到以下三种情况:

1. 我需要订购套装中的物品.为此我使用了混合SortedSet特征的类,当你只使用标准Scala API时,它总是一个TreeSet.它保证元素按照他们的compareTo方法排序(参见Orderedtrat).因为插入/检索的运行时现在是对数的,而不是(几乎)常量,就像HashSet(假设一个好的散列函数)一样,你会得到(非常)小的性能损失.

2. 您需要保留项目的插入顺序.然后你用LinkedHashSet.实际上和正常一样快HashSet,需要更多的存储空间来存储元素之间的附加链接.

3. 你不关心Set中的顺序.所以你使用了HashSet.(这是使用Set.apply第一个示例中的方法时的默认设置)

所有这一切都适用于Java的还有,Java有一个TreeSet,LinkedHashSet并HashSet与相应的接口SortedSet,Comparable和平原Set.

Answer 2

我相信你永远不应该依赖于集合中的顺序.没有语言.

除此之外,请看一下这个深入讨论这个问题的问题.

Answer 3

ListSet将始终以插入的相反顺序返回元素,因为它由a支持List,并且向元素添加元素的最佳方式List是通过预先添加它们.

如果你想先进先出(队列),不可变的数据结构是有问题的.您可以获得O(logn)或摊销O(1).鉴于显然需要构建集合然后从中生成迭代器(即,您将首先放置所有元素,然后您将删除所有元素),我没有看到任何方法来分摊它.

你可以依赖一个ListSet将始终返回的元素,先输出顺序(一个堆栈).如果这就足够了,那就去吧.