Swift Collections 1.1
This feature release adds a number of new data structure implementations, along with minor changes to existing constructs.
[…]
Heapimplements a min-max heap, backed by a native array.BitSetandBitArrayare two alternate representations of a bitmap type, backed by dynamically allocated storage.TreeSetandTreeDictionaryare hashed collections implementing Compressed Hash-Array Mapped Prefix Trees (CHAMP). They provide similar API asSet/Dictionaryin the Standard Library, but as persistent data structures, supporting incremental mutations of shared instances and efficient structural diffing.
Michael Steindorfer has written a paper and thesis about CHAMP.
Previously:
Update (2024-02-21): Majid Jabrayilov:
Dictionary and Set types that Swift language provides us store values in a single flat hash table that you copy on every write or mutation. The Swift Collection package introduces TreeDictionary and TreeSet types implementing Compressed Hash-Array Mapped Prefix Trees. In other words, TreeDictionary and TreeSet types hold values in the tree-based structure, allowing the efficient updating of only the needed branches.
[…]
The TreeDictionary is still a struct, but the implementation uses the UnsafeMutablePointer type to access memory and mutate it directly without copying on write. Another benefit of the TreeDictionary and TreeSet types is the optimized way to compare because of their tree-based nature. Usually, they handle this operation in a constant time.
