Hey Jeffrey! I'm still in San Jose after WWDC; I'll check out the thread and join the discussion as soon as I can. :-)
I'm definitely interested in bringing sorted collections to the standard library; indeed, large parts of BTree have been designed with an eye towards integrating it (or a rewritten version of it) into stdlib at some point.
However, this is not the right time to expand the stdlib; without a stable ABI, all apps need to include the entire library, so adding large new stuff into it is not yet a good idea.
There is also the fact that NSOrderedSet serves an entirely different purpose to BTree's SortedSet. (They used to be named similarly, but that was a mistake I quickly corrected.) NSOrderedSet is like an Array with a fast contains(_:) implementation, using hashable elements. SortedSet is very different; it's a set that stores elements in a predefined order based on their implementation of Comparable and that does not require elements to be Hashable.
Bridging OrderedSet into Swift is needed to better interface with existing Cocoa APIs such as Core Data.
Adding SortedSet (Map, etc.) to the stdlib is orthogonal to that; Cocoa has never had public collection implementations based on tree-based data structures.
(It is still a good idea to add these to stdlib, because these are often useful. And also to achieve feature parity with competing languages, of course.)
Sadly, in the talk, I used the name "OrderedSet" to refer to what is really a "SortedSet". Unfortunately, I can't fix the talk, but I did correct the naming in the book I just wrote about the subject: https://www.objc.io/books/optimizing-collections/
I'm in the process of reading your book I love the passion you have in this subject. I will disagree about your ABI argument, because I think since the ABI is not stable it's the best time to add your lib into it and on of the compiler job is to remove dead code. So at the end it should not take a lot a place in our binary. Give the CoreTeam a chance to decide if they want or not integrate your lib in the stblib...
I don't understand why do you say it's orthogonal to SortedSet for me if, NSSortedSet and your SortedSet provide the same set of feature it's the same. But I do understand that the compatibility with CoreData and with the ObjC version of NSOrderedSet can pose some issue...
My main thinking is just think that proposing a good library to the CoreTeam is not a bad idea. That might twist it or reject it or adopt it but I think in this conversation it could help.
To be clear, NSOrderedSet is an entirely different data structure than SortedSet. The two have different APIs, different requirements, and different performance tradeoffs. The Swiftified version of NSOrderedSet would not at all look like SortedSet.
I'm in contact with the standard library team. :-) Until the standard library is part of the operating system (rather than copied into every individual app), it is just not feasible to extend it with large new features like a B-tree implementation: every app would need to include a copy of the full BTree package, not just those that use it. ABI stability will enable the standard library to greatly expand beyond the current feature set, and evolve without recompilation -- just like Cocoa frameworks do. Once we have that, then it is time to propose including B-tree-based collections in the standard library.
I may end up working on speeding that up a bit. BTree needs to be updated for Swift 4 for the short term, but making the stdlib ABI stable is a really interesting project on its own.