Dictionary types around here require their elements/keys to be
Hashable, which makes node retrieval more efficient. Many other languages have this hash-ability requirement for their set and dictionary/map types. But I'm from an earlier age, where my first major introduction to these types was an earlier version of C++, where they used a comparability (i.e.
<) requirement instead of hashing. I miss those days and wrote a version of that kind of set in Swift; it's in a gist.
(I was going to make a post about the binary-search algorithm I'm using there before this post. But searching on these forums about earlier B.S. efforts has inspired me to tinker a little more before posting here specifically about that.)
A key point of the implementation is that it does not arrange storage as a tree of nodes. It uses a single block of memory, which I guess can be an advantage sometimes. It's also cute in that it is its own
Writing this has shown me another flaw in our protocol hierarchy. This type, along with
Dictionary, need the arbitrary-removal part of
RangeReplaceableCollection without the arbitrary-insertion part. That indicates a split to an intermediate protocol. (Yes, I know that adding non-leaf protocols to a hierarchy, even if done in a way that preserves source stability, still violates ABI stability. It has to wait until an ABI Version 2.) They all workaround by manually adding the removal methods of RRC without an associated protocol.
The elements are stored in a single block already sorted by
<, and insertions maintain that sort. That's why I needed a binary-search algorithm.
Due to the single block, I feel the best way to use the sorted-set is to first read from it more than you will alter it. And to do all the element adds/removals in the beginning of the program.
Since they don't include much explanation, am I using the quasi-secret optimization methods correctly? (These are the members after
count in the
Besides interest in copying the older C++ set design to Swift, the main interest (that made me write this now) is to solve a problem with the removing along arbitrary indices at once.
Edit: added link to multi-index removal thread.