Scala: Can I rely on the order of items in a Set?
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
SortedSet
trait which when you use only the Standard Scala API is always aTreeSet
. It guarantees the elements are ordered according to theircompareTo
method (see theOrdered
trat). 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.apply
method like in your first example)
All this applies to Java as well, Java has a TreeSet
, LinkedHashSet
and HashSet
and the corresponding interfaces SortedSet
, Comparable
and plain Set
.
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
will always return elements in the reverse order of insertion because it is backed by a List
, and the optimal way of adding elements to a List
is by prepending them.
Immutable data structures are problematic if you want first in, first out (a queue). You can get O(logn)
or amortized O(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 ListSet
will always return elements in last in, first out order (a stack). If that suffices, then go for it.