Scala：我可以依赖集合中项目的顺序吗？
这是一个相当令人不快的惊喜：
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)
这似乎有效，但我应该依赖这种行为吗？ 还有什么其他数据结构适合于必须保留原始顺序的唯一项的不可变集合？
顺便说一句，我确实知道 List 中的 distict 方法。问题是，我想在界面级别强制项目的唯一性（同时保留顺序），因此使用 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)
但是，问题是我不想公开 < code>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
This was quite an unplesant surprise:
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)
The example by itself suggest a "no" answer to my question. Then what about 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)
This one seems to work, but should I rely on this behavior?
What other data structure is suitable for an immutable collection of unique items, where the original order must be preserved?
By the way, I do know about distict method in List. The problem is, I want to enforce uniqueness of items (while preserving the order) at interface level, so using distinct would mess up my neat design..
EDIT
ListSet doesn't seem very reliable either:
scala> ListSet(1, 2, 3, 4, 5).toList
res28: List[Int] = List(5, 4, 3, 2, 1)
EDIT2
In my search for a perfect design I tried this:
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
Which actually works:
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)
The problem, however, is that I do not want to expose MyList outside the library. Is there any way to have the implicit conversion when overriding? For example:
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
I'd like to do it like this:
object O extends T { val l = List(1, 2, 3) } // Doesn't work
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这取决于您使用的套件。如果您不知道您拥有哪个 Set 实现，那么答案很简单，不，您无法确定。在实践中我通常会遇到以下三种情况：
我需要订购Set中的项目。为此，我在
SortedSet特征中使用混合类，当您仅使用标准 Scala API 时，该特征始终是TreeSet。它保证元素根据其compareTo方法进行排序（请参阅Orderedtrat）。由于插入/检索的运行时间现在是对数的，而不是像HashSet（假设有一个好的哈希函数）那样（几乎）恒定，因此排序会带来（非常）小的性能损失。您需要保留项目插入的顺序。然后使用
LinkedHashSet。实际上与普通的HashSet一样快，需要更多的存储空间来存储元素之间的附加链接。你不关心集合中的顺序。所以你使用
HashSet。 （这是使用Set.apply方法（如第一个示例中所示）时的默认设置）所有这些也适用于 Java，Java 有
TreeSet、LinkedHashSet< /code> 和HashSet以及相应的接口SortedSet、Comparable和 plainSet。That depends on the Set you are using. If you do not know which Set implementation you have, then the answer is simply, no you cannot be sure. In practice I usually encounter the following three cases:
I need the items in the Set to be ordered. For this I use classes mixing in the
SortedSettrait which when you use only the Standard Scala API is always aTreeSet. It guarantees the elements are ordered according to theircompareTomethod (see theOrderedtrat). You get a (very) small performance penalty for the sorting as the runtime of inserts/retrievals is now logarithmic, not (almost) constant like with theHashSet(assuming a good hash function).You need to preserve the order in which the items are inserted. Then you use the
LinkedHashSet. Practically as fast as the normalHashSet, needs a little more storage space for the additional links between elements.You do not care about order in the Set. So you use a
HashSet. (That is the default when using theSet.applymethod like in your first example)All this applies to Java as well, Java has a
TreeSet,LinkedHashSetandHashSetand the corresponding interfacesSortedSet,Comparableand plainSet.我相信你永远不应该依赖集合中的顺序。没有语言。
除此之外，看看这个问题，它深入讨论了这一点。
It is my belief that you should never rely on the order in a set. In no language.
Apart from that, have a look at this question which talks about this in depth.
ListSet将始终以与插入相反的顺序返回元素，因为它由List支持，并且是向List添加元素的最佳方式是通过将它们放在前面。如果您想要先进先出（队列），不可变数据结构是有问题的。您可以获得
O(logn)或摊销O(1)。鉴于显然需要构建集合，然后从中生成迭代器（即，您将首先放置所有元素，然后删除所有元素），我看不到任何方法来摊销它。您可以相信
ListSet将始终按照后进先出的顺序（堆栈）返回元素。如果这就足够了，那就去吧。ListSetwill always return elements in the reverse order of insertion because it is backed by aList, and the optimal way of adding elements to aListis by prepending them.Immutable data structures are problematic if you want first in, first out (a queue). You can get
O(logn)or amortizedO(1). Given the apparent need to build the set and then produce an iterator out of it (ie, you'll first put all elements, then you'll remove all elements), I don't see any way to amortize it.You can rely that a
ListSetwill always return elements in last in, first out order (a stack). If that suffices, then go for it.