Thank you. To be fair I personally really don’t need the
OrderedSet then and I don’t see its shiny use-cases. What I really would wish for is something like a
SortedSet by your definition.
Thank you. To be fair I personally really don’t need the
C++'s bizarre nomenclature strikes again…
I believe the generic
std::set in C++ is in fact an ordered set (or in the vernacular of this thread, a sorted set, since the comparator is specified once for the set). It’s implemented as a red/black tree.
If you want a Swift-style set (that is, a hash table), I believe that’s
One thing I notice from code-kata sites is the frequent use of
std::multiset, which is an ordered collection that allows duplicate elements, implemented as a binary tree. (I can never see this name without my brain yelling “Leeloo Dallas multiset!”)
The naming in Obj-c always tripped me up too, perhaps Ordered and Sorted are too close and can be given something more dissimilar.
I do reach for OrderedSet from time to time, and I think many API’s can improve their semantics by using OrderedSet instead of Array. For example,
UIStackView is an array with a uniqueness guarantee according to the documentation, but this could be more clearly expressed if it returned an OrderedSet.
I’m familiar with SortedSets from Scala, implemented by class
TreeSet which is a red-black tree with ordering specified during initialization. If you leave out the ordering argument, the default ordering on the element type will be used.
The immutable variant looks like an array with uniqued elements that promises faster membership tests – without actually mentioning any performance guarantees.
But the mutable variant is where it gets hairy:
sortRange… From this I gather the elements are implicitly sorted in insertion order, but you can muck around like it’s an array.
A set and an array at the same time!?! I’m having a hard time estimating performance and memory characteristics of this novel (from CS POV) type. And because the documentation doesn’t say, I’ll assume it’s backed by an array and a tree that stores array indices? Membership test doing tree traversal with dual pointer chasing for each comparison? Or is this sorted array with binary search and insertion indices in a parallel array?
I see a clear need for a
SortedSet, thoroughly studied data structure with well known performance guarantees. In my opinion, merging
Array into single datastructure is quite strange. I’d prefer the collections in Swift standard library to evolve in modular and composable direction modeled after Scala’s Collections.
@Tony_Parker could please expand what you mean by complement here:
I’m really unclear on the requirements here…
Searching through a
SortedSet has different characteristics, for one.
OrderedSet is useful for maintaining… order. If you need to know when an item was first added in, this is useful. Creating lists of people involved in something might be an example. There isn’t a need to list someone twice, but maybe I want to know what order I added them to the list in.
Both ordered sets and sorted sets exist for JVM languages, Java, Scala, Kotlin, etc., in the form of LinkedHashSet and TreeSet and their derivatives respectively. Ordered sets, linked hash sets, are very common in JVM code. All the sets, not just LinkedHashSet and TreeSet, on the JVM require elements to be
Hashable to give fast performance (not a big deal on the JVM since objects are automatically
Hashable via their memory address).
As an example, i keep a list of observers in a custom OrderedSet-like struct. I want to ensure a single observer isn’t registered twice, but the order in which they registered has to be respected (or at the very minimum deterministic).
All I meant by complement was: we should provide a struct that has approximately the same features as the reference type, so that people can use this new struct in Swift most of the time. Somewhat like
I am open to several types (ordered and sorted) if we think that makes sense. I agree we should be more clear about performance guarantees than the existing
This new type doesn’t have to have 100% the same behavior as
NSOrderedSet. We can take this opportunity to improve the API, much like we did for many of the other value types we’ve introduced in Foundation. However, it would be weird if we introduce a
struct OrderedSet which is totally unrelated in concept to the reference type.
Hopefully that clarifies things a bit.
For now I think the best we can do is to have one implementation that is copied into both places. There are some practical considerations about why the overlay is part of the compiler and why swift-corelibs-foundation is a separate git repository.
Someday (I’m hoping after ABI stability is done), I hope to consolidate the projects so we can have just one repository.
Yes please! I find OrderedSets very useful.
A cache for example will use FIFO to drop an object when hitting a threshold (such as a count).
Another use case for me is keeping “Recent Searches” where duplicates don’t make sense and order is important.
I’ve asked about it at WWDC 17 (along with JSON parsing) and I’m excited to see these features get implemented.
If an element that is already in the ordered set is added again to the set will the element now be considered at the front of the ordered set?
The semantics of NSMutableOrderedSet (which I believe control the intended behavior of OrderedSet) follow the NSSet convention, in that adding an object equal to an object in the set does nothing:
Set behave the same and will teturn
false if you try to insert the same element.
If we’re buidling the “recent searches” UI element mentioned earlier and reordering the result based on recency, perhaps the
SortedSet type is more useful for this scenario?
It seems to me that building (or having the effects of) a “SortedSet” is pretty easy given an “OrderedSet”. But an “OrderedSet” type cannot be simulated with only a “Set” and “SortedSet”
I think this is the key question. By default, we should follow the convention of NSMutableOrderedSet (re-adding does nothing), but we should also have an option to override this behavior and move the element to the end.
func add(_ item : Element, reorderIfPresent : Bool = false)
Does that hold its own weight vs just:
// strawman syntax orderedSet.remove(item) orderedSet.append(item)
I don’t have a strong opinion, really, just asking. I suppose there’s a performance win with a single statement, but not sure if I grok all the use-cases for this situation.
That’s closer to splay semantics than existing
NSMutableOrderedSet. @QuinceyMorris is right in that
NSMutableOrderedSet is a set first, then an array only after the set membership test fails.
SortedSet isn’t quite appropriate for the ‘move the inserted item to the front’, because it requires the sort-predicate to globally manipulate the data structure which is not typical.
@palimondo - the idea of ordered set is very common when yielding results from
select distinct-style database queries - which is why CoreData uses them as heavily as they do. Yes they are ‘sorted’ in that there is a distinct order to them (whatever the
order by clause states for instance), but the predicate that orders them is far less important than the fact that they are distinct and in a specific order.
In fact, thinking about that seems to be the crux of the difference between the two kinds of sets. And gosh yes, we need better names than sorted vs ordered! :)
Looks like we’ve made some great progress in this thread. Does anyone want to volunteer to draw up a simple starting point of what an interface for
SortedSet might look like?